Как управляется динамическая память в std :: vector? - PullRequest
Новая
       34

Как управляется динамическая память в std :: vector?

2 голосов
/ 23 марта 2009

Как std :: vector реализует управление изменяющимся числом элементов: использует ли она функцию realloc () или использует связанный список?

Спасибо.

Ответы [ 4 ]

11 голосов
/ 23 марта 2009

Он использует распределитель, который был ему задан в качестве второго параметра шаблона. Как тогда. Скажем, он находится в push_back, пусть t будет объектом, который нужно нажать: 

...
if(_size == _capacity) { // size is never greater than capacity
    // reallocate
    T * _begin1 = alloc.allocate(_capacity * 2, 0);
    size_type _capacity1 = _capacity * 2;

    // copy construct items (copy over from old location).
    for(size_type i=0; i<_size; i++)
        alloc.construct(_begin1 + i, *(_begin + i));
    alloc.construct(_begin1 + _size, t);

    // destruct old ones. dtors are not allowed to throw here. 
    // if they do, behavior is undefined (17.4.3.6/2)
    for(size_type i=0;i<_size; i++)
        alloc.destroy(_begin + i);
    alloc.deallocate(_begin, _capacity);

    // set new stuff, after everything worked out nicely
    _begin = _begin1;
    _capacity = _capacity1;
} else { // size less than capacity
    // tell the allocator to allocate an object at the right
    // memory place previously allocated
    alloc.construct(_begin + _size, t);
}
_size++; // now, we have one more item in us
...

Что-то в этом роде. Распределитель будет заботиться о выделении памяти. Он разделяет шаги по выделению памяти и построению объекта в этой памяти, поэтому он может предварительно выделять память, но еще не вызывать конструкторы. Во время перераспределения вектор должен заботиться об исключениях, создаваемых конструкторами копирования, что несколько усложняет ситуацию. Выше приведен только фрагмент псевдокода, а не реальный код, который, вероятно, содержит много ошибок. Если размер становится больше емкости, он просит распределителя выделить новый больший блок памяти, если нет, то он просто создает в ранее выделенном пространстве.

Точная семантика этого зависит от распределителя. Если это стандартный распределитель, то конструкция будет делать 

new ((void*)(_start + n)) T(t); // known as "placement new"

И распределитель allocate просто получит память от ::operator new. destroy назовет деструктор 

(_start + n)->~T();

Все, что абстрагируется за распределителем, а вектор просто использует его. Распределитель стека или пула может работать совершенно иначе. Некоторые ключевые моменты о vector, которые важны

  • После вызова reserve(N) в ваш вектор можно вставить до N элементов без риска перераспределения. До тех пор, пока size() <= capacity(), ссылки и итераторы на его элементы остаются действительными.
  • Векторное хранилище является смежным. Вы можете рассматривать & v [0] как буфер, содержащий столько элементов, сколько у вас есть в вашем векторе.
7 голосов
/ 23 марта 2009

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

Таким образом, вы знаете, что теоретически вы можете сделать это: 

const Widget* pWidgetArrayBegin = &(vecWidget[0]);

Затем можно передать pWidgetArrayBegin в функции, которые хотят получить массив в качестве параметра.

Единственным исключением является специализация std :: vector . На самом деле это совсем не bools, но это другая история.

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

Это означает, что вы можете выстрелить себе в ногу, выполнив следующее: 

Widget* pInteresting = &(vecWidget.back());
vecWidget.push_back(anotherWidget);

Как вы знаете, вызов push_back мог заставить вектор сместить свое содержимое в совершенно новый блок памяти, аннулировав pInteresting .

1 голос
/ 23 марта 2009

std :: векторные данные, хранящиеся в смежных блоках памяти.

Предположим, мы объявили вектор как

std :: vector intvect;

Итак, изначально будет создана память из x элементов. Здесь x зависит от реализации.

Если пользователь вставляет более x элементов, то будет создан новый блок памяти из 2x (удвоенного размера) элементов, и начальный вектор будет скопирован в этот блок памяти.

Именно поэтому всегда рекомендуется резервировать память для вектора, вызывая функцию резерва. функция.

intvect.reserve (100);

во избежание удаления и копирования векторных данных.

1 голос
/ 23 марта 2009

Память, управляемая std::vector, гарантированно будет непрерывной, так что вы можете рассматривать &vec[0] как указатель на начало динамического массива.

Учитывая это, то, как он фактически управляет перераспределением, зависит от реализации.

...