Как векторный реализован в C++
Я думаю, как я могу реализовать станд.:: вектор с нуля.
Как это изменяет размер вектора?
перевыделение только, кажется, работает на простой stucts или является мной неправильно?
7 ответов
это простой шаблонный класс, который является оболочкой для собственного массива. Он не использует malloc / realloc . Вместо этого он использует переданный распределитель (по умолчанию это std :: allocator ).
Изменение размера выполняется путем выделения нового массива и создания копии каждого элемента в новом массиве из старого (таким образом, это безопасно для объектов, не относящихся к POD). Чтобы избежать частого распределения, они часто следуют нелинейной модели роста.
ОБНОВЛЕНИЕ: в C ++ 11 элементы будут перемещены вместо созданной копии, если это возможно для сохраненного типа.
В дополнение к этому, он должен будет сохранить текущий «размер» и «емкость». Размер - это количество элементов в векторе. Емкость - это сколько может быть в векторе.
Итак, в качестве отправной точки вектор должен выглядеть примерно так:
template <class T, class A = std::allocator<T> >
class vector {
public:
// public member functions
private:
T* data_;
typename A::size_type capacity_;
typename A::size_type size_;
A allocator_;
};
Другой распространенной реализацией является сохранение указателей на различные части массива. Это немного удешевляет end () (который больше не требует добавления) за счет чуть более дорогого вызова size () (который теперь требует вычитания) . В этом случае это могло бы выглядеть так:
template <class T, class A = std::allocator<T> >
class vector {
public:
// public member functions
private:
T* data_; // points to first element
T* end_capacity_; // points to one past internal storage
T* end_; // points to one past last element
A allocator_;
};
Я считаю, что библиотека gcc libstdc ++ использует второй подход, но оба подхода одинаково действительны и соответствуют друг другу.
ПРИМЕЧАНИЕ: Это игнорирует обычную оптимизацию, когда для распределителя используется оптимизация пустого базового класса. Я думаю, что это качество деталей реализации, а не вопрос правильности.
Он выделяет новый массив и копирует все заново. Так что расширять его довольно неэффективно, если вам приходится делать это часто. Используйте резерв (), если вам нужно использовать push_back ().
Из Википедии, как нельзя более подходящий ответ.
Типичная реализация вектора состоит, внутри, из указателя на динамически выделяемый массив,[2] и, возможно, членов данных, содержащих емкость и размер вектора. Размер вектора относится к фактическое количество элементов, в то время как емкость относится к размеру внутреннего массива. При вставке новых элементов, если новый размер вектора становится больше, чем его емкость, происходит перераспределение происходит.[2][4] Это обычно приводит к тому, что вектор выделяет новую область хранения, перемещение ранее хранившихся элементов в новую область и освобождает старую область. Поскольку адреса элементов меняются во время этого процесса, любые ссылки или итераторы на элементы в векторе становятся недействительными.[5] Использование недействительной приводит к неопределенному поведению
Вот так: https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_vector.h
(официальное зеркало gcc на github)
Вам нужно определить, что вы подразумеваете под «простыми старыми структурами.«
realloc сам по себе создает только блок неинициализированной памяти. Он не выполняет выделение объектов. Для структур C этого достаточно, но для C ++ этого нет.
Это не значит, что вы не можете использовать realloc. Но если бы вы использовали его (обратите внимание, что вы не будете повторно реализовывать std :: vector именно в этом случае!), вам потребуется:
- Убедитесь, что вы постоянно используете
malloc / realloc / freeво всем вашем классе. - Используйте «размещение
new» для инициализации объектов в вашем фрагменте памяти. - Явно вызывайте деструкторы для очистки объектов перед освобождением вашего фрагмента памяти.
На самом деле это очень похоже на то, что вектор делает в моей реализации (GCC / glib), за исключением того, что он использует низкоуровневые процедуры C ++ :: operator new и :: operator delete ] для управления необработанной памятью вместо malloc и free, перезаписывает процедуру перераспределения с использованием этих примитивов и делегирует все это поведение объекту распределителя, который может b e заменен специальной реализацией.
Так как вектор является шаблоном, вам действительно нужно иметь его источник, чтобы посмотреть, если вам нужна ссылка - если вы можете преодолеть преобладание подчеркивания, его не должно быть слишком сложно читать. Если вы используете Unix-сервер и используете GCC, попробуйте найти / usr / include / c ++ / version / vector или около того.
realloc работает только с кучей памяти. В C++ вы обычно хотите использовать свободное хранилище.
Изменение размера вектора требует выделения нового участка пространства и копирования существующих данных в новое пространство (таким образом, требуется, чтобы элементы, помещенные в вектор, могли быть скопированы).
Обратите внимание, что не использует new [] - он также использует переданный аллокатор, но он необходим для выделения raw памяти, а не массива объектов, как это делает new []. Затем вам нужно использовать placement new для создания объектов на месте. [Edit: well, you could technically use new char[size], and use that as raw memory, but I can't quite imagine anyone writing a allocator like that.]
When current allocation is exhausted and a new block of memory needs to be allocated, the size must be increased by a constant factor compared to the old size to meet the requirement for amortized constant complexity for push_back. Хотя многие веб-сайты (и подобные им) называют это удвоением размера, фактор около 1,5-1,6 обычно работает лучше. В частности, это повышает шансы повторного использования освобожденных блоков для будущих распределений.