Как реализован C++ std::vector?
Я использую std::vector много, и недавно я задал себе этот вопрос: "Как это std::vector реализованы?"
У меня было две альтернативы:
1) Связанный список, а затем заставляет API чувствовать себя как произвольный доступ (т.е. перегрузка operator[]).
2) Использование newнапример, Foo* temp = new Foo[20]Я думаю, что они делают что-то подобное, но тогда возникает еще один вопрос. Всегда ли они выделяют максимум (uint32_t) хранилище для произвольного доступа? (Это неэффективно с точки зрения памяти.)
Или я должен знать что-то еще?
9 ответов
Это реализовано с использованием базового массива.
Невозможно реализовать std::vector<T> со связанным списком, потому что стандарт гарантирует, что элементы в списке будут храниться в непрерывной памяти.
Я считаю, что это третий вариант. Это не может просто использовать new T[n] потому что тогда ему на самом деле придется построить столько объектов, сколько он выделит. Например
std::vector<Foo> v;
v.reserve(10);
Если ваша реализация просто закончилась new Foo[10] тогда вы бы просто создали 10 экземпляров Foo.
Вместо этого он использует свой распределитель для выделения и освобождения необработанной памяти (без создания объектов) и по мере необходимости (например, когда вы на самом деле push_back объекты) помещает экземпляры, созданные путем копирования, в правильные области памяти в своем резерве с помощью размещения new и удаляет их с явными вызовами деструктора (то, что вы должны делать только в сочетании с размещением new). Класс allocator предоставляет следующие методы для того, что, как я предполагаю, используют реализации вектора
void construct(pointer p, const_reference val);
Returns:
new((void *)p) T(val)
void destroy(pointer p);
Returns:
((T*)p)->~T()
("Возвращение", вероятно, должно читаться как "эффект" или аналогичный.)
Подробнее о размещении новых
Они используют динамически размещенный массив, который восстанавливается по мере необходимости. Необходимо использовать что-то вроде массива, чтобы элементы были смежными в памяти, что гарантировано стандартом.
Между прочим, одним из распространенных способов перераспределения массива является удвоение размера по мере необходимости. Это так, что если вы вставляете n только предметы O(log n) отрастания выполняются и не более O(n) пространство потрачено впустую.
Вы можете прочитать одну реализацию для себя в SGI (где STL был изначально задуман).
Нет единственного способа, которым это реализовано. Разные реализации могут быть разными, при условии сохранения семантики и удовлетворения требований.
В любой момент времени должен существовать массив примитивов T, чтобы удовлетворить требования смежности. Однако то, как оно распределяется, увеличивается, сокращается и освобождается, зависит от разработчика.
Вы можете прочитать реализацию для себя, это прямо в файле заголовка.
Я могу сказать вам, что никакие реализации не используют связанные списки. Они не соответствуют требованиям стандарта.
Раздел 23.2.4, of1 стандарта требует, чтобы арифметика для указателей на вектор работала так же, как и для указателей на массив.
Элементы вектора хранятся непрерывно, а это означает, что если v является вектором, где T - некоторый тип, отличный от bool, то он подчиняется тождеству &v[n] == &v[0] + n для всех 0 <= n
Это гарантирует, что хранилище находится в массиве. Конечно, если вы измените размер массива, чтобы он стал больше, он может быть перемещен в память.
Педагогическая (и, следовательно, упрощенная) версия контейнера под названием "Vec" обсуждается в главе 11 замечательной (вводной) книги "Ускоренный C++". То, что они описывают, является урезанной версией std::vector, но я думаю, что все же стоит отметить, что:
1) они реализуют свой шаблонный класс в терминах массива,
2) они обсуждают push_back с точки зрения хитрости (упомянутой выше): выделять больше памяти, чем необходимо, и возвращаться для большего, когда они заканчиваются, и
3) они используют распределитель <T> для управления памятью. Оператор new в этом контексте недостаточно гибок, так как он выделяет и инициализирует память.
Я повторяю, однако, что это не означает, что реальные реализации там такие простые. Но поскольку "Ускоренный C++" довольно широко распространен, заинтересованные могут найти в соответствующей главе один из способов создания, копирования, назначения и уничтожения вектороподобных объектов.
РЕДАКТИРОВАТЬ: В связанной заметке, я только что нашел следующий пост в блоге Херба Саттера, в котором он комментирует более раннюю запись в блоге Эндрю Кенига, касающуюся того, следует ли беспокоиться о соприкосновении векторных элементов в памяти: гарантированно будут смежными.
Я считаю, что STL использует опцию № 2 (или что-то подобное), потому что std::vector<> гарантированно хранит элементы в смежной памяти.
Если вы ищете структуру памяти, в которой не нужно использовать непрерывную память, посмотрите на std::deque.
В любой приличной реализации вообще нет реального массива (если он есть, вы не можете использовать в нем ни один объект без конструктора по умолчанию), а только необработанная память, которая выделяется. Он распределяется таким образом, который обычно дублирует каждый раз, когда вам нужно его расширить.
Затем вектор использует выделенное место для вызова конструкторов класса в правильном месте, как только каждый слот фактически используется.
Когда есть расширение, оно будет пытаться перераспределить на месте (но это немного глупо и обычно не работает, подумайте о сжатии кучи в Windows 98), но, как правило, в конечном итоге происходит полное выделение и копирование.
Стандартный вектор stl всегда все вместе, но не все реализации работают так (я знаю, написав некоторые из них). Вероятно, ни один из них не является точно связанным списком.
Из того, что я прочитал в книгах, а также из функциональности резерва и требования, чтобы элементы векторов были смежными, я думаю, что это может быть возможным способом реализации Vector.
1) Элементы векторов должны быть смежными, поддерживать O(1) произвольного доступа, а векторы должны быть совместимы с массивами C. Это просто означает, что нет связанных списков.
2) Когда вы вызываете резерв, он резервирует дополнительную память. Но резерв звонит
new T[newSize]
зарезервировать больше памяти. В противном случае он вызовет конструктор по умолчанию. Как объяснил uncleben всякий раз, когда резерв вызывается, векторный класс просто выделяет больше неинициализированной памяти с помощью своего распределителя (если требуется) и копирует новые объекты в эту память, используя размещение new(если выделено больше памяти)
3) Изначально вектор имеет некоторую емкость по умолчанию. для которого выделяется неинициализированная память при создании векторного объекта
4) копия push_back создает объект в первом доступном месте. Если требуется, больше памяти должно быть выделено аналогично резервному.