c++ - ¿Cómo se ve std:: vector en la memoria?

memory contiguous

Question

Leí que std::vector debería ser contiguo. Mi entendimiento es que sus elementos deben almacenarse juntos, no extendidos por toda la memoria. Simplemente acepté el hecho y utilicé este conocimiento cuando, por ejemplo, utilizaba su método data() para obtener la parte de memoria contigua subyacente.

Sin embargo, me encontré con una situación en la que la memoria del vector se comporta de una manera extraña:

std::vector<int> numbers;
std::vector<int*> ptr_numbers;
for (int i = 0; i < 8; i++) {
    numbers.push_back(i);
    ptr_numbers.push_back(&numbers.back());
}

Esperaba que esto me diera un vector de algunos números y un vector de punteros a estos números. Sin embargo, al enumerar los contenidos de los punteros de ptr_numbers , hay números diferentes y aparentemente aleatorios, como si ptr_numbers accediendo a partes incorrectas de la memoria.

He intentado comprobar el contenido a cada paso:

for (int i = 0; i < 8; i++) {
    numbers.push_back(i);
    ptr_numbers.push_back(&numbers.back());
    for (auto ptr_number : ptr_numbers)
       std::cout << *ptr_number << std::endl;
    std::cout << std::endl;
}

El resultado se ve más o menos así:

1

some random number
2

some random number
some random number
3

Así que parece que cuando push_back() al vector de numbers , sus elementos más antiguos cambian su ubicación.

Entonces, ¿qué significa exactamente que std::vector es un contenedor contiguo y por qué se mueven sus elementos? Tal vez los almacene juntos, pero los mueve todos juntos, cuando se necesita más espacio?

Edición: ¿Es std::vector contiguo solo desde C ++ 17? (Solo para mantener los comentarios en mi reclamo anterior relevantes para futuros lectores).

Answer 1

Entonces, ¿qué significa exactamente que std :: vector es un contenedor contiguo y por qué se mueven sus elementos? Tal vez los almacene juntos, pero los mueve todos juntos, cuando se necesita más espacio?

Así es exactamente cómo funciona y por qué los elementos anexos invalidan todos los iteradores y las ubicaciones de memoria cuando se realiza una reasignación. Esto no solo es válido desde C ++ 17, ha sido así desde entonces.

Hay un par de beneficios de este enfoque:

• Es muy caché y por lo tanto eficiente.
• El método data() se puede usar para pasar la memoria en bruto subyacente a las API que funcionan con punteros en bruto.
• El costo de asignar nueva memoria en push_back , reserve o resize reduce a un tiempo constante, a medida que el crecimiento geométrico se amortiza con el tiempo (cada vez que push_back se llama la capacidad se dobla en libc ++ y libstdc ++, y aproximadamente los crecimientos por un factor de 1.5 in MSVC).
• Permite la categoría de iteradores más restringidos, es decir, iteradores de acceso aleatorio, porque la aritmética de punteros clásica funciona bien cuando los datos se almacenan de forma contigua.
• Mover la construcción de una instancia vectorial de otra es muy barato.

Estas implicaciones pueden considerarse la desventaja de tal diseño de memoria:

• Todos los iteradores y los punteros a los elementos se invalidan en las modificaciones del vector que implican una reasignación. Esto puede llevar a errores sutiles cuando, por ejemplo, borra elementos mientras se repite sobre los elementos de un vector.
• No se proporcionan operaciones como push_front (como std::list o std::deque proveen) ( insert(vec.begin(), element) funciona, pero es posiblemente caro), así como la combinación / empalme eficiente de múltiples instancias vectoriales .

¹ Gracias a @ FrançoisAndrieux por señalarlo.

Answer 2

La respuesta

Es un único almacenamiento contiguo (una matriz 1d). Cada vez que se queda sin capacidad, se reasigna y los objetos almacenados se mueven al nuevo lugar más grande, es por eso que observa que las direcciones de los objetos almacenados cambian.

Siempre ha sido así, no desde C++17 .

TL; DR

El almacenamiento está creciendo geométricamente para garantizar el requisito de O(1) push_back() amortizado. El factor de crecimiento es 2 ( Cap _{n + 1} = Cap _n + Cap _n ) en la mayoría de las implementaciones de la Biblioteca estándar de C ++ ( GCC , Clang , STLPort ) y 1.5 ( Cap _{n + 1} = Cap _n + Cap _n / 2 ) en el Variante de MSVC .

Si lo asigna previamente con vector::reserve(N) y vector::reserve(N) suficientemente grande, las direcciones de los objetos almacenados no cambiarán cuando agregue otros nuevos.

En la mayoría de las aplicaciones prácticas, por lo general vale la pena asignarlo previamente a al menos 32 elementos para omitir las primeras reasignaciones poco después de la otra (0 → 1 → 2 → 4 → 8 → 16).

A veces también es práctico reducir la velocidad, cambiar a la política de crecimiento aritmético ( Cap _{n + 1} = Cap _n + Const ) o detenerse por completo después de un tamaño bastante grande para garantizar que la aplicación no se desperdicie ni se agote en la memoria.

Por último, en algunas aplicaciones prácticas, como los almacenes de objetos basados ​​en columnas, puede valer la pena renunciar a la idea de almacenamiento contiguo completamente a favor de uno segmentado (igual que lo hace std::deque pero con std::deque mucho más grandes). De esta manera, los datos se pueden almacenar razonablemente bien localizados para consultas por columna y por fila (aunque esto también puede necesitar algo de ayuda del asignador de memoria).

Answer 3

En términos de la estructura real, un std::vector parece a esto en la memoria:

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)
};

Fragmento de código relevante de la implementación de libc++ tal como lo utiliza LLVM

Imprimiendo los contenidos de memoria en bruto de un std::vector :
(¡No hagas esto si no sabes lo que estás haciendo!)

#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"
      ;
}

Answer 4

Se ve aproximadamente como esto (disculpe mi obra maestra de MS Paint):

La instancia std::vector que tiene en la pila es un objeto pequeño que contiene un puntero a un búfer asignado en el montón, más algunas variables adicionales para realizar un seguimiento del tamaño y la capacidad del vector.

Así que parece que cuando push_back() al vector de numbers , sus elementos más antiguos cambian su ubicación.

El búfer asignado al montón tiene una capacidad fija. Cuando llegue al final del búfer, se asignará un nuevo búfer en otro lugar del montón y todos los elementos anteriores se moverán al nuevo. Por lo tanto, sus direcciones cambiarán.

Tal vez los almacene juntos, pero los mueve todos juntos, cuando se necesita más espacio?

A grandes rasgos, sí. La estabilidad de los elementos del iterador y la dirección está garantizada con std::vector solo si no se realiza una reasignación.

Soy consciente de que std::vector es un contenedor contiguo solo desde C ++ 17

El diseño de la memoria de std::vector no ha cambiado desde su primera aparición en el estándar. ContiguousContainer es solo un "concepto" que se agregó para diferenciar contenedores contiguos de otros en tiempo de compilación.

Answer 5

std::vector es un contenedor contiguo que significa exactamente lo que crees que significa.

Sin embargo, muchas operaciones en un vector pueden reubicar toda esa memoria.

Un caso común es que al agregarle un elemento, el vector debe crecer, se puede reasignar y copiar todos los elementos en otra memoria contigua.