Как реализован векторный класс C ++ для динамического изменения размеров массивов?

Question

Как реализован векторный класс C ++, позволяющий динамически изменять размер массивов?

Осуществляется ли это через реализацию типа связанного списка?Новый массив создается с нуля каждый раз, когда элемент добавляется или убирается?

Спасибо, R

Answer 1

Типичное поведение: внутренне, std::vector имеет непрерывный массив длины capacity. В любой данный момент только size элементы фактически используются. Если в любой момент size превысит capacity (допустим, вы много раз звонили push_back()), выделяется новый, больший внутренний массив (скажем, capacity может удвоиться). Затем все элементы из старого массива копируются в новый, а старые элементы и массив удаляются.

Answer 2

Большинство реализаций используют простой массив и удваивают емкость всякий раз, когда массив заполняется.Это включает в себя копирование существующих элементов в новый блок памяти, но это компенсируется тем фактом, что вам не придется делать это снова в течение некоторого времени.(Используя такую ​​технику, добавления элементов выполняются с амортизированным постоянным временем.)

Answer 3

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

GCC использует коэффициент 2.0 при перераспределении памяти, MSVC использует коэффициент 1,5.