Как выглядит std :: vector в памяти? - программирование
Подтвердить что ты не робот

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

Я читал, что std::vector должен быть смежным. Я понимаю, что его элементы должны храниться вместе, а не распространяться по памяти. Я просто принял этот факт и использовал эти знания, например, используя метод data() чтобы получить базовую непрерывную часть памяти.

Однако я столкнулся с ситуацией, когда векторная память ведет себя странным образом:

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

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

Я пытался проверять содержимое на каждом шагу:

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

Результат выглядит примерно так:

1

some random number
2

some random number
some random number
3

Так кажется, что когда я push_back() в векторе numbers, его старые элементы меняют свое местоположение.

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

Edit: Является ли std::vector смежным только с С++ 17? (Просто чтобы оставить комментарии к моему предыдущему утверждению актуальными для будущих читателей.)

4b9b3361

ОТВЕТЫ

Ответ 1

Это примерно похоже на это (извините мой шедевр MS Paint):

vector memory layout

Стандартный экземпляр std::vector который у вас есть в стеке, представляет собой небольшой объект, содержащий указатель на буфер, выделенный для кучи, плюс некоторые дополнительные переменные для отслеживания размера и емкости вектора.

Так кажется, что когда я push_back() в векторе numbers, его старые элементы меняют свое местоположение.

Буфер, выделенный для кучи, имеет фиксированную емкость. Когда вы дойдете до конца буфера, новый буфер будет выделен где-то еще в куче, и все предыдущие элементы будут перемещены в новый. Поэтому их адреса будут меняться.

Может быть, они хранят их вместе, но перемещают их все вместе, когда требуется больше места?

Грубо, да. Итератор и стабильность адресов элементов гарантируются с помощью std::vector только если перераспределение не происходит.

Я знаю, что std::vector является смежным контейнером только с С++ 17

Макет памяти std::vector не изменился с момента его первого появления в стандарте. ContiguousContainer - это всего лишь "концепция", которая была добавлена для дифференциации смежных контейнеров от других во время компиляции.

Ответ 2

Ответ

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

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

TL; DR

Хранилище растет геометрически, чтобы обеспечить требование амортизированного O(1) push_back(). Фактор роста равен 2 ( Cap n + 1= Cap n + Cap n) в большинстве реализаций стандартной библиотеки C++ (GCC, Clang, STLPort) и 1.5 ( Cap n + 1= Cap n + Cap n/2) в варианте MSVC.

growing std::vector

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

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

Также иногда бывает целесообразно замедлить его, перейти к политике арифметического роста ( Cap n + 1= Cap n + Const) или полностью прекратить работу после достаточно большого размера, чтобы приложение не тратилось или не выросло из памяти.

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

Ответ 3

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

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

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

Ответ 4

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

Это точно, как это работает и почему добавление элементов действительно делает недействительными все итераторы, а также места памяти при перераспределении. Это не только актуально с С++ 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 за указание на это.

Ответ 5

С точки зрения фактической структуры 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 size         = " << vec.myvec.end - vec.myvec.begin << "\n"
      << "vec 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"
      ;
}