conteneur avec empilement et allocation dynamique

Existe-t-il un conteneur qui utilise un tampon local pour un petit nombre d'éléments et utilise une allocation de segment uniquement lorsque le nombre d'éléments dépasse une certaine limite? Semblable à ce que font la plupart des implémentations std::string.conteneur avec empilement et allocation dynamique

fond

Le récipient est utilisé dans ce qui suit (simplifié) contexte:

Foo foo;      // some data 
vector<HandlerPtr> tagged; // receives "tagged" items 

// first pass: over all items in someList 
for each(HandlerPtr h in someList) 
{ 
    h->HandleFoo(foo);   // foo may become tagged or untagged here 
    if (foo.Tagged()) 
    tagged.push_back(h); 
} 
for(auto itr=tagged.rbegin(); itr!=tagged.end(); ++itr) 
{ 
    // ... 
}

Cette partie A du code haute fréquence d'appel, mais le marquage d'un élément est assez rare, le nombre des articles dans someContainer est généralement faible mais non lié. Je ne peux pas utiliser facilement un tampon "plus global" préalloué. L'objectif est d'éviter l'allocation fréquente.

Appel Fréquence

commun: aucun élément devient marqué. std :: vector is fine
Commun: seulement un des rares articles a été étiqueté. provoque l'allocation haute fréquence je veux éviter
Très rare, mais il doit être pris en charge: somelist se développe lors de la première passe, le nombre d'éléments non prévisibles, mais encore faible

Source

2010-12-10 peterchen

Voulez-vous utiliser des allocations statiques ou de pile? Pour l'allocation de pile, voir http://stackoverflow.com/questions/354442/looking-for-c-stl-like-vector-class-but-using-stack-storage – nimrodm

@nimrodn: l'allocation de pile est probablement une meilleure description de ce que Je veux (titre fixe). c'est-à-dire un nombre limité d'éléments qui peuvent être stockés dans l'instance de conteneur (sans allocation supplémentaire), et l'utilisation de l'allocation de tas si cela n'est pas suffisant. – peterchen

'std :: vector' n'alloue aucune mémoire avant l'insertion d'au moins un élément. –

Il n'y a pas de conteneur standard qui garantit ce genre de comportement . Toutefois, si vous en êtes capable, vous pouvez créer une classe d'allocation compatible STL personnalisée qui utilise un petit tampon de pile pour de petites allocations et n'effectue une allocation de tas que lorsque la taille d'allocation demandée dépasse la taille du tampon de pile. Vous pouvez ajouter votre classe d'allocateurs personnalisée en tant que second paramètre de modèle pour std::vector<T, Alloc>.

Pour plus d'informations sur la création d'un allocateur personnalisé, vous devez lire this article.

Source

2010-12-10 07:37:04

Vous pouvez aussi essayer .reserve() en ajoutant une quantité d'espace dans le vecteur qui est petit, mais "assez" la plupart du temps. Cela évitera potentiellement des réaffectations si la politique de votre vecteur doit commencer à une taille de 1 et utiliser la même politique de redimensionnement quelle que soit la taille actuelle. –

@Karl: Un scénario courant est que le conteneur restera vide. La réservation sera mauvaise pour cela, car elle allouera toujours de la mémoire dynamique. – visitor

en C++ 0x qui est certainement la solution, mais si je me souviens bien, les Allocateurs C++ 03 ne devraient pas conserver l'état qui n'est pas partagé entre toutes les instances des Allocators (par exemple, tout autre allocateur du même type pourrait être destroy/deallocate, même si les deux instances sont complètement indépendantes). En pratique, je pense que cela devrait fonctionner :) –

Bien que cela ne soit pas garanti, la plupart std::string mettra en œuvre les Small String Optimization, ce qui est juste que (avec VC de 10 jusqu'à 8 ou 16 personnages sont thusly stockés)

Je ne l'ai pas vu vectors le faire, et Je me suis toujours demandé pourquoi, mais la prochaine norme C++ facilitera cela avec std::aligned_storage et alignof. De cette façon, nous serons en mesure d'obtenir une mémoire brute correctement alignée et de construire des conteneurs avec un certain nombre par défaut de mémoire "pile".

Source

2010-12-10 08:35:33

La taille d'un vecteur n'est normalement pas supérieure à la taille de trois pointeurs. Quelle quantité de données pourrait contenir dans cet espace, étant donné que vous devrez également stocker certaines données d'entretien? – visitor

@visitor: Je suppose que cela dépend si vous utilisez les bits les plus élevés des pointeurs pour conserver ces données :) Mais je serais personnellement prêt à avoir une classe buffier 'vector'. Le coût de la copie du «vecteur» est très différent du coût de la copie de trois pointeurs, car il implique une allocation dynamique (donc un appel à 'allocate') et la copie en profondeur des données existantes. Par conséquent, j'ai cru comprendre qu'il serait moins coûteux de réserver simplement de l'espace supplémentaire. 'vecteur ' par exemple. Cependant, je ne connais pas un tel conteneur, mais je vais probablement l'essayer à la maison, bien qu'il soit toujours difficile d'égaler l'efficacité du STL. –

@Mattieu: * difficile à égaler * - exactement, en particulier la combinaison efficacité + flexibilité. Il est facile de sortir quelque chose pour mon cas particulier, mais cela viendrait avec tellement de limites que ça ne serait pas drôle. – peterchen

conteneur avec empilement et allocation dynamique

Répondre

Questions connexes