J'ai remarqué que la STD :: Mise en œuvre de la carte de Visual Studio (2010) attribue un nouveau bloc de mémoire unique pour chaque nœud dans son arbre noir. C'est-à-dire que pour chaque élément de la carte, un nouveau bloc de mémoire brute sera attribué via Cela semble un peu gaspillé pour moi: ne serait-il pas plus logique d'allouer les nœuds en blocs de "(petit) n", tout comme STD :: Les implémentations vectorielles sur-allocation sur la croissance?
Je voudrais donc que les points suivants clarifiés:
Opérateur New ... MALLOC avec le schéma d'allocation par défaut du STD :: Plan de la mise en œuvre de Visual Studio STL .
5 Réponses :
Je suis tout à fait certain que je n'ai jamais vu de mise en œuvre de Certes, la plupart des allocateurs personnalisés sont écrits pour mieux traiter avec l'attribution d'un grand nombre de petits blocs. Vous pouvez probablement rendre la vaste la majorité de cette optimisation inutile en écrivant std :: map qui a tenté de coalser plusieurs nœuds dans un seul bloc d'allocation. Au moins juste à droite, je ne peux pas penser à une raison pour laquelle il ne pouvait pas travailler, mais je pense que la plupart des implémentations le verraient aussi inutiles et laissent optimiser l'allocation de mémoire à l'allocateur au lieu de s'inquiéter beaucoup dans la carte elle-même.
carte (et, bien sûr, définir , multiiset , et multimap ) pour simplement utiliser des allocations plus grandes à la place. OTOH, étant donné que les allocateurs d'optimiser les petites allocations de blocs sont facilement / communs / largement disponibles, il n'y a probablement pas beaucoup de motivation pour modifier la carte de la mise en œuvre de cette voie.
Je pense que la seule chose que vous ne pouvez pas faire est d'invalider les itérateurs, que vous pourriez avoir à faire si vous devez réaffecter votre stockage. Cela dit, j'ai vu des implémentations à l'aide d'une maquette unique d'objets emballés dans l'interface STD :: Carte. Cela a été fait pour une certaine raison, bien sûr.
En réalité, ce que vous pouvez faire est d'instancier votre STD :: Carte avec votre allocator personnalisé, qui trouvera une mémoire pour de nouveaux nœuds de manière spéciale et non gaspillée.
Si vous parlez de USTL , le Créateur estime que les garanties de complexité sont facultatives et ne comprennent pas la sémantique d'invalidation! C'est simplement une bibliothèque horrible. Chaque conteneur est mis en œuvre sur un vecteur: la liste hérite du vecteur et DEQUE est une macro pour la liste ! Vous ne pouvez pas écrire correctement STD :: Carte à l'aide d'un tableau unique de tri.
Si vous ne parlez pas d'USTL, où l'avez-vous vu d'autre?
Il y avait une mise en œuvre dans une entreprise que j'ai travaillé il y a quelques années. Mais je me souviens que j'ai vu quelque chose de similaire ailleurs, peut-être que c'était USTL, je ne suis pas sûr.
Lorsque vous insérez des éléments dans une carte, il est garanti que les itérateurs existants ne seront pas invalidés. Par conséquent, si vous insérez un élément "B" entre deux nœuds A et C qui devaient être contigus et à l'intérieur de la même zone allouée de tas, vous ne pouvez pas les mélanger pour faire de la place, et B devra être mis ailleurs. Je ne vois aucun problème particulier avec cela, sauf que la gestion de ces complexités va gonfler la mise en œuvre. Si vous effacez des éléments, les itérateurs ne peuvent pas être invalidés non plus, ce qui implique toute allocation de mémoire doit être suspendue jusqu'à ce que tous les nœuds ne soient effacés. Vous auriez probablement besoin d'un freeliste au sein de chaque "nœud gonflé" / vecteur / tout-quoi-you-veux-t-il - en double surpliquant efficacement au moins certaines des opérations de consommation de temps qui ne font actuellement que pour vous.
Serait-il aider à allouer un seul gros bloc dans un cas où aucun ou seul peu de nœuds sont effacés? Dans ce cas, il semble que vous puissiez faire sans freeliste et juste incrémenter un pointeur dans le bloc.
@Alexandre: Seulement si les blocs sont toujours triés (et rappelez-vous, vous ne pouvez pas résoudre ce problème car vous ne pouvez pas déplacer des éléments), peu de nœuds effacées et aucun inserts «B B» n'est-il idéal pour itérer l'incrément de pointeur. Cela peut arriver si la carte est peuplée par des inserts dans l'ordre, mais semble sans hésiter. "B" Insère entre "A" contiguë existant et "B" signifie soit la recherche d'un B ailleurs dans le bloc, ou insérant un lien vers un autre bloc à ce moment-là. Le suivi soit douloureux.
Je pense que vous confondez le schéma d'allocation de mémoire (allocation de piscine) et la couche de présentation (arbre noir rouge). Il n'est pas nécessaire de mélanger les nœuds dans la mémoire lorsque vous insérez un nouveau nœud, vous devez simplement mettre à jour quelques pointes.
@Matthieu: J'ai du mal à voir comment j'aurais peut-être confondu. Re "pas besoin de shuffle nœuds" - J'ai très clairement dit que nous ne pouvons pas mélanger les nœuds sans rupture de STD :: Les garanties de validité d'itérateur existantes de la carte. C'est avec cette contrainte que j'explore comment la structure de l'arborescence peut être créée ou implicite: il ne sert à rien d'avoir des blocs plus importants si nous allocions des nœuds indépendants pour l'arborescence, nous devons donc explorer les éléments de suivi à l'intérieur des listes de blocs allouées. option. Si vous ajoutez que nous voulions de l'espace pour un «sous-arbre» de pointeurs dans et sous le bloc, je suis d'accord ...
Je parlais de cette partie de votre réponse "Par conséquent, si vous insérez un élément" B "entre deux nœuds A et C qui devaient être contigus et dans la même zone allouée de tas, vous ne pouvez pas les mélanger pour faire de la place et B devra être mis ailleurs. " Il n'est pas nécessaire de mélanger un ou C en mémoire, l'OP n'a pas demandé à A, B et C d'être placé de manière contiguë, vous pouvez simplement mettre B dans un autre bloc (Schéma d'allocation de mémoire), puis mettre à jour les indicateurs A et C inclure B dans l'arborescence (couche d'arbre noir). Je suis d'accord sur la partie de gestion du poste.
Votre affirmation est correcte pour la plupart des implémentations de STD :: Carte.
À ma connaissance, il n'y a rien dans la norme empêchant une carte d'utiliser un schéma d'allocation tel que vous décrivez. Cependant, vous pouvez obtenir ce que vous décrivez avec un allocator personnalisé - mais obligeant ce système sur toutes les cartes pourraient être inutiles. Parce que la carte n'a pas une connaissance priori de la manière dont il sera utilisé, certains modèles d'utilisation pourraient empêcher les localisations de blocs principalement inutilisés. Par exemple, disons que des blocs ont été alloués à 4 nœuds à la fois, mais une carte particulière est remplie de 40 nœuds, puis 30 nœuds effacées, laissant un pire cas d'un nœud gauche par bloc, car la carte ne peut pas invalider les pointeurs / références / les itérateurs à ce sujet. dernier nœud.
Cela semble un peu gaspillé pour moi. N'aurait-il pas plus logique d'allouer les nœuds en blocs de "(petit) n", comme STD :: Les implémentations vectorielles sur-allocation sur la croissance
Fait intéressant, je le vois d'une manière complètement différente. Je trouve que cela est approprié et il ne gasage pas de mémoire. Au moins avec des allocateurs de défault STL sous Windows (MS VS 2008), HP-UX (GCC avec STLORT) et Linux (GCC sans stlport). Ce qui est important, c'est que ces allocateurs se soucient de la fragmentation de la mémoire et il semble qu'ils puissent gérer cette question plutôt bien. Par exemple, recherchez
tas de fragmentation bas sous Windows ou SBA (petit allocateur de bloc) sur HP-UX. Je veux dire que l'affectation fréquente et la suppression de la mémoire uniquement pour un nœud à la fois ne doit pas avoir à résulter de la fragmentation de la mémoire. J'ai testéstd :: map moi-même dans l'un de mes programmes et cela ne causa aucune fragmentation de mémoire avec ces allocateurs.
mon assertion sur la valeur par défaut Schéma d'allocation réellement correct?
J'ai Mme VisualStudio 2008 et son STD :: La carte se comporte de la même manière. Sur HP-UX, j'utilise GCC avec et sans stlport et il semble que leurs cartes STL ont la même approche de l'affectation de la mémoire pour les nœuds dans le
std :: map .
Y a-t-il quelque chose dans le STD Empêcher une STD :: Mise en œuvre de la carte de mettre ses nœuds en blocs de mémoire au lieu d'attribution d'une nouvelle Bloc de mémoire (via son allocator) Pour chaque nœud?
Commencez par le réglage d'un allocator par défaut sur votre plate-forme si cela est possible. Il est utile ici de citer le Douglas Lea qui est un auteur de dl-malloc
... d'abord j'ai écrit un certain nombre de Allocators à usage spécial en C ++, Normalement en surcharge de l'opérateur Nouveau pour diverses classes. ...
Cependant, j'ai vite compris que le bâtiment un allocator spécial pour chaque nouvelle classe qui a eu tendance à être dynamiquement alloué et fortement utilisé n'était pas un bonne stratégie lors de la construction de types de Support de programmation à usage général classes que j'écris à l'époque. (De 1986 à 1991, j'étais le Auteur principal de Libg ++, le GNU C ++ bibliothèque.) Une solution plus large était nécessaire - écrire un allocator qui était assez bon sous la normale C ++ et C charges afin que les programmeurs ne soient pas tenté d'écrire un but spécial allocators sauf sous très spéciale conditions.
ou comme une idée un peu plus difficile, vous pouvez même essayer de tester votre application avec un allocator HOARD. Je veux dire simplement tester votre application et voir s'il existe un avantage comme pour la performance ou la fragmentation.
Comme alternative, pour de petites cartes / jeu, vous voudrez peut-être utiliser
loki :: associvecteur , qui implémente l'interface d'unmappe (mais pas ses conditions d'invalidation) sur un < Code> Vecteur pour de meilleures performances.