A quoi ressemble std::vector en mémoire?

La Réponse

c'est un stockage contigu simple (un tableau 1d). Chaque fois qu'il est à court de capacité, il est réattribué et les objets stockés sont déplacés vers le nouvel endroit plus grand - c'est pourquoi vous observez les adresses des objets stockés changer.

Il a toujours été de cette façon, et non pas depuis C++17.

TL; DR

Le stockage est en croissance géométriquement pour s'assurer que l'exigence de l'amorti O(1)push_back(). Croissance le facteur est de 2 ( Cap _n+1 = Cap _n + Cap _n) dans la plupart des implémentations de la bibliothèque Standard C++ (GCC, Clang, STLPort) et de 1,5 ( Cap _n+1 = Cap _n + Cap _n / 2) MSVC variante.

Si vous pré-allouer par vector::reserve(N) et suffisamment grand N, alors les adresses des objets stockés ne changera pas lorsque vous ajoutez de nouveaux.

dans la plupart des applications pratiques, il vaut généralement la peine de pré-affecter à au moins 32 éléments pour sauter les premières réaffectations peu de temps après l'Autre (0→1→2→4→8→16).

il est également parfois pratique de le ralentir, passer à la Politique de croissance arithmétique ( Cap _n+1 = Cap _n + Const), ou s'arrêter complètement après une certaine taille raisonnablement grande pour s'assurer que l'application ne gaspille pas ou ne sort pas de la mémoire.

enfin, dans certaines applications pratiques, comme les dépôts d'objets basés sur des colonnes, il peut être intéressant de renoncer à l'idée de stockage contigu complètement en faveur d'un stockage segmenté (identique à ce que std::deque mais avec des morceaux beaucoup plus grands). De cette façon, les données peuvent être stockées raisonnablement bien localisé pour les requêtes par colonne et par ligne (bien que cela puisse nécessiter de l'aide de l'allocateur mémoire).

std::vector être un conteneur contigu signifie exactement ce que vous pensez qu'il signifie.

cependant, de nombreuses opérations sur un vecteur peuvent re-localiser ce morceau entier de mémoire.

un cas commun est quand vous ajoutez un élément à elle, le vecteur doit croître, il peut réattribuer et copier tous les éléments à un autre morceau contigu de mémoire.

alors qu'est-ce que cela signifie exactement, que std::vector est un conteneur contigu et pourquoi ses éléments se déplacent-ils? Est-ce qu'il peut les stocker ensemble, mais les déplace tous ensemble, quand plus d'espace est nécessaire?

c'est exactement comme ça que ça marche et pourquoi ajouter des éléments invalide en effet tous les itérateurs ainsi que les emplacements de mémoire quand une réallocation a lieu1. Ce n'est pas seulement valable depuis C++17, il a été le cas depuis.

il y a un quelques avantages de cette approche:

• il est très facile à mettre en cache et donc efficace.
• data() la méthode peut être utilisée pour passer la mémoire brute sous-jacente aux API qui fonctionnent avec des pointeurs bruts.
• Le coût d'allocation de mémoire sur push_back,reserve ou resize se réduisent à temps constant, que la croissance géométrique amortit au fil du temps (à chaque fois push_back est appelé la capacité est doublée en libc++ et libstdc++, et environ. excroissances par un facteur de 1,5 dans MSVC).
• il permet la catégorie d'itérateurs la plus restreinte, c'est-à-dire les itérateurs à accès aléatoire, parce que l'arithmétique Classique des pointeurs fonctionne bien lorsque les données sont stockées de façon contiguë.
• déplacer la construction d'une instance vectorielle à partir d'une autre est très bon marché.

Ces implications peuvent être considérés comme l'inconvénient d'une telle disposition de la mémoire:

• tous les itérateurs et les pointeurs vers les éléments sont invalidés modifications du vecteur impliquant une réallocation. Cela peut conduire à des bugs subtils lors de l'effacement d'éléments lors de l'itération des éléments d'un vecteur.
• Activités push_front (std::list ou std::deque provide) ne sont pas fournis (insert(vec.begin(), element) fonctionne, mais est peut-être expensive1), ainsi que la fusion efficace/épissage des instances vectorielles multiples.

1 Merci à @FrançoisAndrieux de le souligner.

en termes de structure réelle, un std::vector ressemble à quelque chose comme ceci en mémoire:

struct vector {    // Simple C struct as example (T is the type supplied by the template)
  T *begin;        // vector::begin() probably returns this value
  T *end;          // vector::end() probably returns this value
  T *end_capacity; // First non-valid address
  // Allocator state might be stored here (most allocators are stateless)
};

extrait de code pertinent de la libc++ mise en œuvre utilisées par LLVM

imprimer le contenu de la mémoire brute d'un std::vector:

(Ne le faites pas si vous ne savez pas ce que vous faites!)

#include <iostream>
#include <vector>

struct vector {
    int *begin;
    int *end;
    int *end_capacity;
};

int main() {
    union vecunion {
        std::vector<int> stdvec;
        vector           myvec;
        ~vecunion() { /* do nothing */ }
    } vec = { std::vector<int>() };
    union veciterator {
        std::vector<int>::iterator stditer;
        int                       *myiter;
        ~veciterator() { /* do nothing */ }
    };

    vec.stdvec.push_back(1); // Add something so we don't have an empty vector

    std::cout
      << "vec.begin          = " << vec.myvec.begin << "\n"
      << "vec.end            = " << vec.myvec.end << "\n"
      << "vec.end_capacity   = " << vec.myvec.end_capacity << "\n"
      << "vec's size         = " << vec.myvec.end - vec.myvec.begin << "\n"
      << "vec's capacity     = " << vec.myvec.end_capacity - vec.myvec.begin << "\n"
      << "vector::begin()    = " << (veciterator { vec.stdvec.begin() }).myiter << "\n"
      << "vector::end()      = " << (veciterator { vec.stdvec.end()   }).myiter << "\n"
      << "vector::size()     = " << vec.stdvec.size() << "\n"
      << "vector::capacity() = " << vec.stdvec.capacity() << "\n"
      ;
}