Как реализуется вектор в С++

Ответ 1

это простой шаблонный класс, который обертывает собственный массив. Он не использует malloc/realloc. Вместо этого он использует переданный распределитель (который по умолчанию равен std::allocator).

Изменение размера выполняется путем выделения нового массива и копирования, создающего каждый элемент в новом массиве из старого (таким образом, он безопасен для объектов, отличных от POD). Чтобы избежать частых выделений, часто они следуют за нелинейным шаблоном роста.

UPDATE: в С++ 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 libstdС++ делает это, оба подхода одинаково верны и соответствуют.

Конечно, вы также можете использовать PIMPL idiom, чтобы сделать обмен намного проще за счет дополнительной косвенности во время доступа. Но это вопрос предпочтения.

Ответ 2

Изменение размера вектора требует выделения нового фрагмента пространства и копирования существующих данных в новое пространство (таким образом, требование копирования элементов, помещенных в вектор).

Обратите внимание, что он не использует new [] либо - он использует передатчик, который передал, но требует выделения необработанной памяти, а не массива таких объектов, как new []. Затем вам нужно использовать placement new для создания объектов на месте. [Edit: ну, вы можете технически использовать new char[size] и использовать это как необработанную память, но я не могу себе представить, чтобы кто-нибудь писал такой распределитель.]

Когда текущее распределение исчерпано и требуется выделение нового блока памяти, размер должен быть увеличен на постоянный коэффициент по сравнению со старым размером, чтобы соответствовать требованию амортизированной постоянной сложности для push_back. Хотя многие веб-сайты (и такие) называют это удвоение размера, коэффициент от 1,5 до 1,6 обычно работает лучше. В частности, это в целом повышает вероятность повторного использования освобожденных блоков для будущих распределений.

Ответ 3

Он выделяет новый массив и копирует все. Таким образом, его расширение довольно неэффективно, если вам приходится часто это делать. Используйте reserve(), если вам нужно использовать push_back().

Ответ 4

Из Wikipedia, как хороший ответ, как любой.

Типичная векторная реализация состоит, изнутри, указателя на динамически выделенный массив, [2] и, возможно, элементы данных, содержащие емкость и размер вектора. Размер вектора относится к фактическое количество элементов, тогда как емкость относится к размеру внутреннего массива. Когда новые элементы вставлены, если новый размер вектора становится больше его емкости, перераспределения имеет место. [2] [4] Это обычно приводит к тому, что вектор выделяет новый область хранения, переместить ранее сохраненные элементы в новый регион хранения и освободить старый регион. Потому что адреса элементы изменяются во время этого процесса, любые ссылки или итераторы элементы в векторе становятся недействительными [5]. Использование недействительных ссылка вызывает поведение undefined

Ответ 5

Вот так: https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_vector.h

(официальное gcc-зеркало на github)

Ответ 6

Вам нужно определить, что вы подразумеваете под "простыми старыми структурами".

realloc сам по себе создает только блок неинициализированной памяти. Он не выделяет объекты. Для C-структур это достаточно, но для С++ это не так.

Чтобы не сказать, что вы не можете использовать realloc. Но если бы вы его использовали (обратите внимание, что вы не будете переопределять std::vector именно в этом случае!), Вам нужно:

• Убедитесь, что вы последовательно используете malloc/realloc/free во всем классе.
• Используйте "размещение new" для инициализации объектов в блоке памяти.
• Явно вызовите деструкторы для очистки объектов перед освобождением фрагмента памяти.

Это фактически очень близко к тому, что делает вектор в моей реализации (GCC/glib), за исключением того, что он использует низкоуровневые подпрограммы С++ ::operator new и ::operator delete для управления необработанной памятью вместо malloc и free, переписывает подпрограммой realloc с использованием этих примитивов и делегирует все это поведение объекту-распределителю, который может быть заменен пользовательской реализацией.

Поскольку вектор является шаблоном, на самом деле у вас должен быть источник, на который вы хотите посмотреть, хотите ли вы ссылки - если вы можете преодолеть преобладание символов подчеркивания, его не следует читать слишком сложно. Если вы используете коробку Unix с помощью GCC, попробуйте найти /usr/include/c++/version/vector или около того.

Ответ 7

realloc работает только в памяти кучи. В С++ вы обычно хотите использовать бесплатный магазин.