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

Question

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

Спасибо.

Answer 1

Он использует распределитель, который был предоставлен ему в качестве второго параметра шаблона. Так вот. Скажем, в 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] в качестве буфера, содержащего столько элементов, которые у вас есть в вашем векторе.

Answer 2

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

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

Answer 3

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

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

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

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

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

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

Это означает, что вы можете снимать себя в ногу, делая это:

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

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

Answer 4

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

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

станд :: вектор intvect;

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

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

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

intvect.reserve (100);

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