Comment la mémoire dynamique est-elle gérée dans std :: vector?

Question

Comment std :: vector implémente la gestion du nombre d'éléments changeants: Utilise-t-il la fonction realloc() ou utilise-t-il une liste chaînée?

Merci.

Answer 1

Il utilise l'allocateur qui a été donné comme le deuxième paramètre de modèle. Comme ça alors. Dites-le est en push_back, laissez t l'objet d'être poussé:

... 
if(_size == _capacity) { // size is never greater than capacity 
    // reallocate 
    T * _begin1 = alloc.allocate(_capacity * 2, 0); 
    size_type _capacity1 = _capacity * 2; 

    // copy construct items (copy over from old location). 
    for(size_type i=0; i<_size; i++) 
     alloc.construct(_begin1 + i, *(_begin + i)); 
    alloc.construct(_begin1 + _size, t); 

    // destruct old ones. dtors are not allowed to throw here. 
    // if they do, behavior is undefined (17.4.3.6/2) 
    for(size_type i=0;i<_size; i++) 
     alloc.destroy(_begin + i); 
    alloc.deallocate(_begin, _capacity); 

    // set new stuff, after everything worked out nicely 
    _begin = _begin1; 
    _capacity = _capacity1; 
} else { // size less than capacity 
    // tell the allocator to allocate an object at the right 
    // memory place previously allocated 
    alloc.construct(_begin + _size, t); 
} 
_size++; // now, we have one more item in us 
... 

Quelque chose comme ça. L'allocateur se souciera de l'allocation de la mémoire.Il conserve les étapes d'allocation de la mémoire et de construction de l'objet dans cette mémoire, de sorte qu'il peut préallouer la mémoire, mais pas encore appeler les constructeurs. Lors de la réaffectation, le vecteur doit veiller à ce que les exceptions soient levées par les constructeurs de copie, ce qui complique quelque peu le problème. Ce qui précède est juste un extrait de code pseudo - pas de code réel et contient probablement beaucoup de bugs. Si la taille dépasse la capacité, il demande à l'allocateur d'allouer un nouveau plus grand bloc de mémoire, sinon il construit juste à l'espace précédemment alloué.

La sémantique exacte de ceci dépend de l'allocateur. Si elle est l'allocateur standard, la construction fera

new ((void*)(_start + n)) T(t); // known as "placement new" 

Et allocate allocate obtiendrez juste la mémoire de ::operator new. destroy appelleraient le destructor

(_start + n)->~T(); 

Tout ce qui est derrière le Abstraite allocateur et le vecteur juste utilise. Une pile ou un allocateur de mise en commun peut fonctionner complètement différemment. Quelques points clés sur vector qui sont importants

• Après un appel à reserve(N), vous pouvez avoir jusqu'à N éléments insérés dans votre vecteur sans risquer une réaffectation. Jusque-là, c'est aussi long que size() <= capacity(), les références et itérateurs aux éléments de celui-ci restent valables.
• Le stockage de vecteur est contigu. Vous pouvez traiter & v [0] comme un tampon contenant autant d'éléments que vous avez actuellement dans votre vecteur.

Answer 2

La mémoire gérée par std::vector est garantie comme continue, de sorte que vous pouvez traiter &vec[0] comme un pointeur vers le début d'un tableau dynamique.

Compte tenu de cela, comment il gère en fait il est réaffectations est spécifique de mise en œuvre.

Answer 3

Une des règles strictes et rapide des vecteurs est que les données seront stockées dans un bloc contigu de mémoire.

De cette façon, vous savez que vous pouvez théoriquement faire:

const Widget* pWidgetArrayBegin = &(vecWidget[0]); 

Vous pouvez ensuite passer pWidgetArrayBegin en fonctions qui veulent un tableau en tant que paramètre.

La seule exception à cette règle est la spécialisation std :: vector <bool>. Ce n'est pas du tout un bêtis, mais c'est une autre histoire.

Ainsi, le std :: vecteur réaffectera la mémoire, et n'utilisera une liste chaînée.

Cela signifie que vous pouvez vous tirer dans le pied en faisant cela:

Widget* pInteresting = &(vecWidget.back()); 
vecWidget.push_back(anotherWidget); 

Pour tout ce que vous savez, l'appel push_back aurait provoqué le vecteur de transférer son contenu à un bloc entièrement nouveau de la mémoire, invalidant pInteresting.

Answer 4

std :: données stockées vectorielles dans des blocs de mémoire contigus.

Supposons que nous déclarons un vecteur

std :: vecteur intvect; Donc, initialement, une mémoire d'éléments x sera créée. Ici, x dépend de l'implémentation.

Si l'utilisateur insère plus de x éléments qu'un nouveau bloc de mémoire sera créé de 2x (deux fois la taille) des éléments et le vecteur initial est copié dans ce bloc de mémoire.

C'est pourquoi il est toujours recommandé de réserver la mémoire pour le vecteur en appelant la réserve fonction.

intvect.reserve (100);

afin d'éviter la suppression et la copie de données vectorielles.