Как выглядит std :: vector в памяти?

Ответ

Это одно смежное хранилище (1d массив).
Каждый раз, когда он исчерпывает свою емкость, он перераспределяется, и сохраненные объекты перемещаются в новое более крупное место — вот почему вы наблюдаете изменение адресов хранимых объектов.

Так было всегда, а не с C++17,

TL; DR

Склад растет геометрически обеспечить требование амортизируемого O(1) push_back(), Коэффициент роста составляет 2 (Крышка_{п + 1} = Сар_N + Крышка_N) в большинстве реализаций стандартной библиотеки C ++ (НКУ, лязг, STLPort) и 1,5 (Крышка_{п + 1} = Сар_N + Крышка_N / 2) в MSVC вариант.

Если вы предварительно выделите его с vector::reserve(N) и достаточно большой Nтогда адреса сохраненных объектов не будут меняться при добавлении новых.

В большинстве практических приложений обычно стоит предварительно выделить его как минимум для 32 элементов, чтобы пропустить первые несколько перераспределений, следующих вскоре после друг друга (0 → 1 → 2 → 4 → 8 → 16).

Иногда также целесообразно замедлить его, переключиться на арифметическую политику роста (Крышка_{п + 1} = Сар_N + Const) или полностью остановитесь после некоторого достаточно большого размера, чтобы приложение не тратило или не увеличивало объем памяти.

Наконец, в некоторых практических приложениях, таких как хранилища объектов на основе столбцов, возможно, стоит полностью отказаться от идеи непрерывного хранения в пользу сегментированного (то же, что и std::deque делает, но с гораздо большими кусками). Таким образом, данные могут храниться достаточно хорошо локализованными для запросов как по столбцам, так и по строкам (хотя для этого также может потребоваться некоторая помощь со стороны распределителя памяти).

std::vector Быть непрерывным контейнером означает именно то, что вы думаете, что это значит.

Тем не менее, многие операции над вектором могут переместить всю эту часть памяти.

Один общий случай — когда вы добавляете элемент к нему, вектор должен расти, он может перераспределять и копировать все элементы в другой непрерывный фрагмент памяти.

Так что же это означает, что std :: vector является смежным контейнером и почему его элементы перемещаются? Может быть, он хранит их вместе, но перемещает их все вместе, когда требуется больше места?

Именно так это работает и почему добавление элементов действительно делает недействительными все итераторы, а также места в памяти, когда происходит перераспределениеation. Это верно не только с C ++ 17, но и с тех пор.

У этого подхода есть пара преимуществ:

• Это очень удобно для кэша и, следовательно, эффективно.
• data() Этот метод можно использовать для передачи базовой необработанной памяти в API, которые работают с необработанными указателями.
• Стоимость выделения новой памяти при push_back, reserve или же resize сводиться к постоянному времени, так как геометрический рост амортизируется с течением времени (каждый раз push_back называется емкость удваивается в libc ++ и libstdc ++, и ок. рост в 1,5 раза в MSVC).
• Он учитывает наиболее ограниченную категорию итераторов, то есть итераторы с произвольным доступом, потому что классическая арифметика указателей хорошо работает, когда данные сохраняются непрерывно.
• Переместить конструкцию векторного экземпляра из другого очень дешево.

Эти последствия можно считать недостатком такой схемы памяти:

• Все итераторы и указатели на элементы становятся недействительными при модификациях вектора, которые подразумевают перераспределение. Это может привести к незначительным ошибкам, например, когда стирание элементов при переборе элементов вектора.
• Операции как push_front (как std::list или же std::deque предоставить) не предоставляются (insert(vec.begin(), element) работает, но возможно дорого¹), а также эффективное слияние / объединение нескольких векторных экземпляров.

¹ Спасибо @ FrançoisAndrieux за указание на это.

С точки зрения фактической структуры, std::vector выглядит примерно так в памяти:

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

Соответствующий фрагмент кода из libc++ реализация, используемая LLVM

Печать необработанного содержимого памяти std::vector:
(Не делайте этого, если вы не знаете, что делаете!)

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