Как выглядит std :: vector в памяти? - PullRequest
Новая
       46

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

0 голосов
/ 14 сентября 2018

Я читал, что 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 является смежным контейнером и почему его элементы перемещаются? Может быть, он хранит их вместе, но перемещает их все вместе, когда требуется больше места?

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

Ответы [ 5 ]

0 голосов
/ 14 сентября 2018

С точки зрения фактической структуры, 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"
      ;
}
0 голосов
/ 14 сентября 2018

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

Именно так оно и работает, и поэтому добавление элементов действительно делает недействительными все итераторы, а также ячейки памяти, когда происходит перераспределение¹. Это верно не только с 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) работает, но, возможно, дорого¹), а также эффективное объединение / объединение нескольких векторных экземпляров.

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

0 голосов
/ 14 сентября 2018

std::vector непрерывный контейнер означает именно то, что, по вашему мнению, означает.

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

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

0 голосов
/ 14 сентября 2018

Это выглядит примерно так (извините, мой шедевр MS Paint):

vector memory layout

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

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

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

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

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

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

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

0 голосов
/ 14 сентября 2018

Ответ

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

Так было всегда, а не с 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 = Крышка n + Крышка n / 2 ) в варианте MSVC .

growing std::vector

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

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

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

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

...