Comment la classe de vecteurs C++ est-elle implémentée pour permettre le redimensionnement dynamique des tableaux?Comment la classe de vecteurs C++ est-elle implémentée pour permettre le redimensionnement dynamique des tableaux?
Est-ce fait à travers une implémentation de type liste-liée? Est-ce qu'un nouveau tableau est créé à partir de zéro chaque fois qu'un élément est ajouté ou supprimé?
Merci, R
comportement typique: interne, un std::vector comporte une matrice contiguë de longueur capacity. À tout moment, seuls les éléments size sont réellement utilisés. Si à tout moment size dépassait capacity (disons que vous appelez beaucoup push_back()), un nouveau tableau interne plus grand est alloué (capacity pourrait doubler, par exemple). Ensuite, tous les éléments de l'ancien tableau sont copiés dans le nouveau, et les anciens éléments et tableau sont supprimés.
Super! Merci tout le monde! – Russel
Les détails dépendent de la mise en œuvre mais le bloc de mémoire alloué par le vecteur est garanti être continu.
GCC utilise le coefficient 2.0 lors de la réallocation de la mémoire, MSVC utilise le coefficient 1.5.
il y avait une discussion il y a quelque temps sur C++. Lang.moderated concernant le coefficient optimal, avec la participation notable d'Alexandrescu, et je pense qu'ils ont déduit qu'il était 'alpha' (racine positive de' x^2 = x + 1') –
La plupart des implémentations utilisent un tableau simple et doublent la capacité chaque fois que le tableau est plein. Cela implique de copier les éléments existants dans un nouveau bloc de mémoire, mais cela est compensé par le fait que vous n'aurez plus à le faire pendant un certain temps. (A l'aide d'une telle technique, les ajouts d'éléments s'exécutent en temps constant amorti.)
Notez également que l'implémentation de la liste chaînée, bien qu'attrayante, ne remplit pas l'exigence 'std :: vector', qui est la disposition contiguë dans la mémoire . * –