Les éléments std :: vector sont-ils garantis contigus?

111

Ma question est simple: les éléments std :: vector sont-ils garantis contigus? Dans l'ordre, puis-je utiliser le pointeur vers le premier élément d'un std :: vector comme tableau C?

Si ma mémoire est bonne, le standard C ++ ne faisait pas une telle garantie. Cependant, les exigences std :: vector étaient telles qu'il était pratiquement impossible de les satisfaire si les éléments n'étaient pas contigus.

Quelqu'un peut-il clarifier cela?

Exemple:

std::vector<int> values;
// ... fill up values

if( !values.empty() )
{
    int *array = &values[0];
    for( int i = 0; i < values.size(); ++i )
    {
        int v = array[i];
        // do something with 'v'
    }
}
Martin Côté
la source
Je sais que tu as des problèmes si tu mutes à l' valuesintérieur de ce ifbloc. Cependant, je ne connais pas la réponse à votre question, alors je laisse juste un commentaire. :)
Greg D
@Greg: Quel problème - pouvez-vous élaborer un peu?
Reunanen
Je suppose qu'il voulait dire que pousser de nouvelles valeurs peut déclencher une "réallocation" qui rendrait le tableau invalide.
Martin Cote
Les appels qui mutent values, en particulier qui modifient sa taille (par exemple, push_back()), peuvent provoquer une réallocation du vecteur sous-jacent qui invalide le pointeur copié array. C'est le même principe que d'utiliser un vector :: iterator au lieu d'un pointeur dans le vecteur. :)
Greg D
1
Ouais, j'ai mis les `` s autour des valeurs pour essayer de préciser que je parlais de la classe elle-même, pas des valeurs qu'elle contient. :) Nomination malheureuse et tout ça. Je ne pense pas que ce soit vraiment un problème dans le cas général où cette question est pertinente - pourquoi quelqu'un attraperait-il un pointeur vers la mémoire, puis commencerait-il à se débarrasser du vecteur au lieu d'utiliser le pointeur? Niaiserie.
Greg D

Réponses:

118

Cela a été omis de la norme C ++ 98 proprement dite, mais ajouté plus tard dans le cadre d'un TR. Le prochain standard C ++ 0x en contiendra bien sûr une exigence.

À partir de n2798 (brouillon de C ++ 0x):

23.2.6 Vecteur de modèle de classe [vecteur]

1 Un vecteur est un conteneur de séquence qui prend en charge les itérateurs à accès aléatoire. De plus, il prend en charge les opérations d'insertion et d'effacement à temps constant (amorti) à la fin; insérer et effacer au milieu prend un temps linéaire. La gestion du stockage est gérée automatiquement, bien que des conseils puissent être donnés pour améliorer l'efficacité. Les éléments d'un vecteur sont stockés de manière contiguë, ce qui signifie que si v est un vecteur où T est un type autre que booléen, alors il obéit à l'identité & v [n] == & v [0] + n pour tout 0 <= n <v .Taille().

dirkgently
la source
3
Ceci est également indiqué dans l'ISO 14882, 2e édition: Section 23.2.4 [lib.vector]: "Les éléments d'un vecteur sont stockés de manière contiguë, ce qui signifie que si v est un vecteur <T, Allocator> où T est un type autre que booléen, alors il obéit à l'identité & v [n] == & v [0] + n pour tout 0 <= n <v.size (). "
Mike Caron
4
so s, TR, TC, :) En fait, C ++ 03 est aussi appelé C ++ 98-TC1 (corrigendum technique) d'après ce que j'ai lu
Johannes Schaub - litb
2
Qu'en est-il des vecteurs de vecteurs? Les vecteurs internes sont juste après les vecteurs internes du dernier groupe?
huseyin tugrul buyukisik
1
@huseyin tugrul buyukisik avez-vous appris la réponse à cela? Je me demande aussi comment cela fonctionne
David Doria
1
@huseyin tugrul buyukisik C'est bien sûr vrai, mais ce sont les instances des suivantes std::vectorqui sont contiguës. Par exemple , .: dans std::vector<std::vector<int>> vles éléments v[0], v[1]... sont stockés ensuite dans la mémoire, mais l'élément v[0].back()et v[1].front()ne sont pas garantis d'être.
jarzec
27

Comme d'autres réponses l'ont souligné, le contenu d'un vecteur est garanti continu (à l'exception de l'étrangeté de bool).

Le commentaire que je voulais ajouter, c'est que si vous effectuez une insertion ou une suppression sur le vecteur, ce qui pourrait provoquer la réallocation du vecteur dans sa mémoire, alors vous invaliderez tous vos pointeurs et itérateurs enregistrés.

Bill Lynch
la source
1
Les éléments seraient toujours stockés dans un bloc de mémoire contigu, ce serait juste à un endroit différent. La question portait spécifiquement sur la contiguïté.
Dima
2
Mais les pointeurs et itérateurs existants seraient invalidés.
Bill Lynch
Bon point. Vous devriez mettre cela dans votre réponse pour clarifier ce que vous voulez dire.
Dima
réponse la plus utile à moi
CoffeDeveloper
Maintenant, je sais pourquoi mon programme était en segfault hier, quand je l'ai parcouru en double boucle en supprimant certains éléments :) Merci!
user2891462
9

La norme garantit en fait que a vectorest continu en mémoire et qu'il &a[0]peut être passé à une Cfonction qui attend un tableau.

L'exception à cette règle est vector<bool> qu'elle n'utilise qu'un bit par bit bool, bien qu'elle ait une mémoire continue, elle ne peut pas être utilisée comme un bool*(ceci est largement considéré comme une fausse optimisation et une erreur).

BTW, pourquoi n'utilisez-vous pas d'itérateurs? C'est à ça qu'ils servent.

Motti
la source
1
> BTW, pourquoi n'utilisez-vous pas d'itérateurs? C'est à ça qu'ils servent. Peut-être a-t-il lu le nouvel article d'Alexanrescu sur le sujet: boostcon.com/site-media/var/sphene/sphwiki/attachment/2009/05/…
Nemanja Trifunovic
Merci pour le lien, je vais y aller à ma liste de lecture (j'essaye de ne pas rater les articles d'Alexandresu)
Motti
Mwahaha, tout le monde semble parler de cette présentation ces jours-ci. Regardez, la discussion est encore chaude à ce sujet: groups.google.com/group/comp.lang.c++.moderated/browse_thread/…
Johannes Schaub - litb
Si vous le lisez attentivement, l'article d'Alexandrescu ne dit pas vraiment "N'utilisez pas d'itérateurs en C ++", il dit "Check out D". L'approche qu'il décrit dans cet article est étonnamment similaire à tous les langages et cadres existants qui ont absorbé l'héritage fonctionnel (List, Scheme, Haskell) et je doute sérieusement qu'une autre syntaxe basée sur C soit un point de départ idéal pour une meilleure gestion des listes. L'année dernière, j'ai brièvement essayé de le persuader de tourner ses talents considérables vers l'amélioration d'un langage déjà établi comme C # à la place, mais je ne crains aucun succès! :)
Daniel Earwicker
6

Comme d'autres l'ont déjà dit, vector utilise en interne un tableau contigu d'objets. Les pointeurs dans ce tableau doivent être traités comme non valides chaque fois qu'une fonction membre non-const est appelée IIRC.

Cependant, il existe une exception!!

vector<bool>a une implémentation spécialisée conçue pour économiser de l'espace, de sorte que chaque booléen n'utilise qu'un seul bit. Le tableau sous-jacent n'est pas un tableau contigu d'arithmétique booléenne et de tableau sur vector<bool>ne fonctionne pas comme le vector<T>ferait.

(Je suppose qu'il est également possible que cela soit vrai pour toute spécialisation de vecteur, puisque nous pouvons toujours en implémenter une nouvelle. Cependant, std::vector<bool>c'est la seule spécialisation standard erronée sur laquelle l'arithmétique de pointeur simple ne fonctionnera pas.)

Wuggy
la source
L'utilisateur n'est pas autorisé à se spécialiser std::vectoret tous les autres vecteurs doivent utiliser le stockage contigu. Par conséquent, std::vector<bool>c'est (heureusement) le seul vecteur standard qui soit bizarre. (Je suis fermement d'avis que cette spécialisation devrait être déconseillée et remplacée par exemple par a std::dynamic_bitsetavec à peu près les mêmes fonctionnalités. Ce n'est pas une mauvaise structure de données, ce n'est tout simplement pas un vecteur.)
Arne Vogel
3

J'ai trouvé ce fil parce que j'ai un cas d'utilisation où les vecteurs utilisant une mémoire contiguë sont un avantage.

J'apprends à utiliser des objets de tampon de sommet dans OpenGL. J'ai créé une classe wrapper pour contenir la logique du tampon, donc tout ce que j'ai à faire est de passer un tableau de flotteurs et quelques valeurs de configuration pour créer le tampon. Je veux pouvoir générer un tampon à partir d'une fonction basée sur l'entrée de l'utilisateur, donc la longueur n'est pas connue au moment de la compilation. Faire quelque chose comme ça serait la solution la plus simple:

void generate(std::vector<float> v)
{
  float f = generate_next_float();
  v.push_back(f);
}

Maintenant, je peux passer les flotteurs du vecteur sous forme de tableau aux fonctions liées au tampon d'OpenGL. Cela supprime également le besoin de sizeof pour déterminer la longueur du tableau.

C'est bien mieux que d'allouer un énorme tableau pour stocker les flotteurs et d'espérer que je l'ai fait assez grand, ou de créer mon propre tableau dynamique avec un stockage contigu.

Personne
la source
2
cette fonction n'a aucun sens pour moi. voulez-vous passer une référence ou un pointeur vers vplutôt que vers vlui-même? car le passage vseul entraînera une copie à l'intérieur de la fonction, qui cessera d'exister après la fin de la fonction. Ainsi, vous poussez quelque chose sur le vecteur uniquement pour supprimer le vecteur lorsque la fonction se termine.
johnbakers
1

cplusplus.com:

Les conteneurs vectoriels sont implémentés sous forme de tableaux dynamiques; Tout comme les tableaux réguliers, les conteneurs vectoriels ont leurs éléments stockés dans des emplacements de stockage contigus, ce qui signifie que leurs éléments sont accessibles non seulement à l'aide d'itérateurs, mais également en utilisant des décalages sur des pointeurs réguliers vers des éléments.

Igor Oks
la source
1

Oui, les éléments d'un std :: vector sont garantis contigus.

Benoît
la source
Droite. J'imagine que j'en utilise trop :)
Benoît