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

Question

Ma question est simple: les éléments std :: vector sont-ils garantis contigus? Dans un mot, puis-je utiliser le pointeur sur le premier élément d'un std :: vector en tant que C-array?

Si ma mémoire est bonne, le standard C ++ ne donnait pas une telle garantie. Cependant, les exigences de 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'
    }
}
 

Answer 1

Ce qui a été raté à partir de C++98 standard correct mais a ajouté plus tard dans le cadre d'une TR. La prochaine C++0x norme de cours contiennent comme une obligation.

De n2798 (projet de C++0x):

23.2.6 modèle de Classe vecteur [vecteur]

1 Un vecteur est un conteneur de séquence qui prend en charge des itérateurs à accès aléatoire. En outre, il prend en charge (après amortissement) constante de temps d'insérer et effacer des opérations, à la fin, insérer et effacer dans le moyen de prendre le temps linéaire. De stockage la gestion est gérée automatiquement, si les conseils peuvent être donnés pour améliorer l'efficacité. Les éléments d'une vecteur sont stockés de manière contiguë, ce qui signifie que si v est un vecteur où T est un type autre de bool, puis il obéit à l'identité &v[n] == &v[0] + n pour tout 0 <= n < v. size().

Answer 2

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

Le commentaire que je voulais ajouter est que si vous effectuez une insertion ou une suppression sur le vecteur, ce qui pourrait provoquer la réaffectation de la mémoire du vecteur, tous les pointeurs et itérateurs enregistrés seront alors invalidés.

Answer 3

La norme n'est en fait garantie qu'un vector est continu dans la mémoire et que, &a[0] peut être transmis à un C fonction qui attend un tableau.

L'exception à cette règle est - vector<bool> qui n'utilise qu'un seul bit par bool ainsi, bien qu'il ne continue de mémoire, il ne peut pas être utilisé comme un bool* (ce qui est largement considéré comme un faux optimisation et une erreur).

BTW, pourquoi ne pas utiliser des itérateurs? C'est ce qu'ils sont pour.

Answer 4

Voir: Est-il prudent de supposer que le stockage de vecteur STL est toujours contigu?

Answer 5

Comme d'autres l'ont déjà dit, vector utilise en interne une ligne de tableau d'objets. Les pointeurs dans ce tableau doivent être considérées comme nulles chaque fois que des non-const fonction membre est appelé IIRC.

Cependant, il existe une exception!!

vector<bool> spécialisé est mise en œuvre conçus pour économiser de l'espace, de sorte que chaque bool n'utilise qu'un seul bit. Le tableau sous-jacent n'est pas une ligne de tableau de bool et de la matrice de l'arithmétique sur vector<bool> pas du tout vector<T> serait.

(Je suppose que c'est aussi possible que cela peut être vrai de toute spécialisation de vecteur, puisque l'on peut toujours mettre en œuvre un nouveau. Toutefois, std::vector<bool> est le seul, err, la norme de la spécialisation sur lesquels simple arithmétique des pointeurs ne fonctionnera pas.)