Как std::vector реализует управление изменением количества элементов: использует ли он функцию realloc() или связанный список?
Спасибо.
Как std::vector реализует управление изменением количества элементов: использует ли он функцию realloc() или связанный список?
Спасибо.
Он использует распределитель, который был передан ему в качестве второго параметра шаблона. Вот так тогда. Скажем, он находится в 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()
, ссылки и итераторы к его элементам остаются действительными.Одно из жестких правил векторов заключается в том, что данные будут храниться в одном непрерывном блоке памяти.
Таким образом, вы знаете, что теоретически можете сделать это:
const Widget* pWidgetArrayBegin = &(vecWidget[0]);
Затем вы можете передать pWidgetArrayBegin функциям, которым нужен массив в качестве параметра.
Единственным исключением является специализация std::vector‹bool›. На самом деле это вовсе не булы, но это уже другая история.
Таким образом, std::vector перераспределит память и не будет использовать связанный список.
Это означает, что вы можете выстрелить себе в ногу, выполнив следующие действия:
Widget* pInteresting = &(vecWidget.back());
vecWidget.push_back(anotherWidget);
Насколько вам известно, вызов push_back мог заставить вектор сместить свое содержимое в совершенно новый блок памяти, сделав pInteresting недействительным.
Память, управляемая std::vector
, гарантированно будет непрерывной, так что вы можете рассматривать &vec[0]
как указатель на начало динамического массива.
Учитывая это, то, как он на самом деле управляет своими перераспределениями, зависит от реализации.
std::vector хранит данные в смежных блоках памяти.
Предположим, мы объявляем вектор как
std::vector intvect;
Итак, изначально будет создана память из x элементов. Здесь x зависит от реализации.
Если пользователь вставляет более x элементов, новый блок памяти будет создан из 2x (удвоенного размера) элементов, и исходный вектор будет скопирован в этот блок памяти.
Вот почему всегда рекомендуется резервировать память для вектора, вызывая резервную функцию.
intvect.reserve(100);
чтобы избежать удаления и копирования векторных данных.