Comment est implémenté C ++ std :: vector?

Question

J'ai été en utilisant std::vector beaucoup, et récemment je me suis posé cette question: "Comment est - std::vector mis en œuvre?"

J'avais deux solutions:

1) liste Liée, et puis prendre l'API envie d'accès aléatoire (c'est à dire la surcharge operator[]).

2) à l'Aide d' new, par exemple, Foo* temp = new Foo[20]: je crois qu'ils font quelque chose comme cela, mais alors, il soulève une question de plus. Font-ils toujours allouer un maximum (uint32_t) de stockage pour donner accès aléatoire? (Ceci est inefficace en termes de mémoire.)

Ou est-il autre chose que je devrais être au courant?

Answer 1

Il est implémenté à l'aide d'un tableau sous-jacent.

Il n'est pas possible d'implémenter un std::vector<T> avec une liste liée car la norme garantit que les éléments de la liste seront conservés dans la mémoire contiguë.

Answer 2

Je crois que c'est la troisième option. Il ne peut pas utiliser new T[n] car alors il aurait en fait à construire autant d'objets qu'il alloue. E. g

std::vector<Foo> v;
v.reserve(10);

Si votre application tout simplement fini par faire new Foo[10] ensuite vous avez juste construit 10 instances de Foo.

Au lieu de cela, elle utilise son allocateur d'allouer et de libérer de la mémoire brute (sans la construction des objets), et en tant que de besoin (par exemple, lorsque vous avez réellement push_back objets) lieux copier-construit dans les instances de corriger les emplacements de la mémoire dans la réserve à l'aide de placement de nouvelles et les supprime avec des appels explicites à le destructeur (quelque chose que vous auriez seulement en combinaison avec la mise en place de nouvelles). L'allocateur de classe fournit des méthodes suivantes pour que j'imagine du vecteur implémentations utilisent

 void construct(pointer p, const_reference val);

  Returns:
    new((void *)p) T(val)

  void destroy(pointer p);

  Returns:
    ((T*)p)->~T()

(Les "retours" devrait se lire "effet" ou similaire).

Plus sur le placement de nouveaux

Answer 3

Ils utilisent un tableau alloué dynamiquement qui est repoussé en tant que de besoin. Il est nécessaire d'utiliser quelque chose comme un tableau afin que les éléments sont contigus en mémoire, qui est garanti par la norme.

D'ailleurs, une façon courante de la repousse d'un tableau est de doubler la taille au besoin. C'est ainsi que si vous insérez n articles, tout au plus, O(log n) regrowths sont effectuées et à la plupart des O(n) de l'espace est gaspillé.

Vous pouvez lire une mise en œuvre par vous-même au SGI (où TSL a été conçu à l'origine).

Answer 4

Il n'y a pas qu'une seule façon, il est mis en œuvre. Différentes implémentations peuvent être différents, aussi longtemps que la conservation de la sémantique et de satisfaire aux exigences.

À un moment donné, il y a une primitive de matrice de T pour satisfaire aux exigences de la contiguïté. Cependant, la façon dont il est attribué, augmenté, diminué, et libérée à l'est jusqu'à l'implémenteur.

Vous pouvez lire la mise en œuvre par vous-même, c'est juste là, dans le fichier d'en-tête.

Je peux vous dire qu' aucun des implémentations utiliser les listes chaînées. Ils ne sont pas compatibles avec les exigences de la norme.

Answer 5

L'article 23.2.4, les numéros 1 de la norme exige que l'arithmétique sur les pointeurs en un vecteur de travail de la même manière qu'avec les pointeurs dans un tableau.

Les éléments d'un vecteur sont stockées de manière contiguë, ce qui signifie que si v est un vecteur où T est certains type autre que le type bool, puis il obéit à l'identité &v[n] == &v[0] + n pour tous 0 <= n < v. size().

Cela garantit que le stockage dans un tableau. Bien sûr, si vous redimensionner le tableau sera plus grand, il peut être déplacé dans la mémoire.