C++ layout объекта, содержащего контейнеры

Question

Как человек, у которого много опыта работы на ассемблере и старые привычки проигрывать, я недавно сделал проект на C++, используя множество функций, которые C++ 03 и C++ 11 должны (в основном, классы контейнеров, в том числе некоторые из Boost). Это было удивительно легко - и я старался везде, где мог, чтобы упростить работу над преждевременной оптимизацией. Когда мы переходим к анализу кода и тестированию производительности, я уверен, что некоторые из старых рук будут иметь аневризмы, не видя точно, как манипулируют каждым байтом, поэтому я хочу иметь некоторые дополнительные боеприпасы.

Я определил класс, члены экземпляра которого содержат несколько векторов и карт. Не «указатели на» векторы и карты. И я понял, что у меня нет ни малейшего представления о том, как много смежных пространств занимают мои объекты, или о том, что может повлиять на производительность для частой очистки и повторного заполнения этих контейнеров.

Как выглядит такой объект, когда-то созданный экземпляр?

Answer 1

Формально нет никаких ограничений на реализацию , кроме указанных в стандарте, в отношении интерфейса и сложности . Практически большинство, если не все версии , происходят из одной и той же базы кода и довольно похожи на .

Основная реализация вектора - это три указателя. Фактическая память для объектов в векторе динамически выделена. В зависимости от того, как вектор «вырос», динамическая область может содержать дополнительную память; три указателя указывают на начало начала памяти, байт после последнего байта в настоящее время используется , а байт после последнего выделенного байта. Возможно, наиболее важным аспектом реализации является то, что он разделяет выделение и инициализацию: вектор будет в во многих случаях выделять больше памяти, чем необходимо, без , строя в нем объекты и будет строить объекты при необходимости , Кроме того, когда вы удаляете объекты или очищаете вектор , он не освобождает память; он уничтожит только объекты и изменит указатель на конец используемой памяти , чтобы отразить это. Позже, когда вы вставляете объекты, вам не потребуется выделение .

Когда вы добавляете объекты за пределы выделенного пространства, вектор выделит новую большую площадь; скопируйте объекты в , затем уничтожьте объекты в старом пространстве и удалите их. Из-за ограничений сложности вектор должен расти в области экспоненциально, умножая размер на некоторую фиксированную константу (1,5 и 2 являются наиболее распространенными факторами), а не на , увеличивая ее на некоторую фиксированную сумму. В результате, если вы вырастите вектор пустым, используя push_back, не будет слишком много перераспределений и копий; Другим результатом является то, что если вы вырастите вектор из пустого, он может в конечном итоге использовать почти в два раза больше, чем .Эти проблемы можно избежать, если вы используете с использованием std::vector<>::reserve().

Что касается карты, ограничения сложности и тот факт, что он должен быть заказан, означает, что необходимо использовать какое-то сбалансированное дерево. Во всех реализациях, которые я знаю, это классическое дерево красного цвета: : каждая запись выделяется отдельно, в узле , который содержит два или три указателя плюс возможно логическое значение в в дополнение к данным.

Я могу добавить, что вышеизложенное относится к оптимизированным версиям контейнеров . В обычных реализациях, когда они не оптимизированы, добавит дополнительные указатели, чтобы связать все итераторы с контейнером , чтобы они могли быть отмечены, когда в контейнере будет что-то недействительное, и чтобы они могли выполнять проверку границ .

И наконец: эти классы являются шаблонами, поэтому на практике у вас есть доступ к источникам, и вы можете посмотреть на них. (Вопросы, как безопасности исключение иногда делают реализации менее прямо вперед, чем мы могли бы, но реализация с г ++ или VC++ не так уж трудно понять.)

Answer 2

Вектор - это обертка для массива. Класс vector содержит указатель на непрерывный блок памяти и как-то знает его размер. Когда вы очищаете вектор, он обычно сохраняет свой старый буфер (зависящий от реализации), так что при следующем повторном использовании его меньше. Если вы измените размер вектора над его текущим размером буфера, ему придется выделить новый. Эффективное использование и очистка одних и тех же векторов для хранения объектов. (std::string аналогичен). Если вы хотите точно узнать, сколько векторов выделили в своем буфере, вызовите функцию capacity и умножьте ее на размер типа элемента. Вы можете вызвать функцию reserve, чтобы вручную увеличить размер буфера, ожидая, что вектор примет больше элементов в ближайшее время.

Карты сложнее, поэтому я не знаю. Но если вам нужен ассоциативный контейнер, вам придется использовать что-то сложное в C тоже, верно?

Answer 3

В основном, vector это просто указатель на массив, наряду с его способностью (всего выделено памяти) и размер (фактически используемые элементы):

struct vector { 
    Item* elements; 
    size_t capacity; 
    size_t size; 
}; 

Конечно, благодаря инкапсуляции все это хорошо и пользователи никогда не смогут обрабатывать детали gory (перераспределение, вызов конструкторов/деструкторов при необходимости и т. д.) напрямую.

Что касается ваших вопросов производительности в отношении очистки, это зависит, как вы очищаете вектор:

• Swapping его с временным пустым вектором (обычная идиома) будет удалить старый массив: std::vector<int>().swap(myVector);
• Использование clear() или resize(0) удалит все элементы и сохранит выделенную память и емкость без изменений.

Если вы обеспокоены эффективностью, ИМХО главное, чтобы рассмотреть, чтобы позвонить reserve() заранее (если возможно), чтобы предварительно выделить массив и избежать ненужных перераспределений и копии (или двигаются с C + +11). При добавлении большого количества элементов в вектор это может иметь большое значение (как мы все знаем, динамическое распределение очень дорого, поэтому его уменьшение может дать большой прирост производительности).

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

---

Что касается карт, то они, как правило, реализованы с использованием красно-черные деревья. Но стандарт не предусматривает этого, он дает только функциональные и сложные требования, поэтому любая другая структура данных, соответствующая законопроекту, хороша. Должен признаться, я не знаю, как реализованы RB-деревья, но я предполагаю, что, опять же, карта содержит хотя бы указатель и размер.

И, конечно, каждый тип контейнера отличается (например, неупорядоченные карты обычно являются хеш-таблицами).

Answer 4

map является бинарное дерево (некоторого многообразия, я считаю, что это обычно красно-черное дерево), поэтому сам map возможно только содержит указатель и некоторые служебные данные (например, количество элементов).

Как и в любом другом двоичном дереве, каждый узел будет содержать два или три указателя (два для «левых» & правых «узлов» и, возможно, один на предыдущий узел, чтобы избежать необходимости пересекать все дерево, чтобы найти, где предыдущий узел (ы)).

В общем случае vector не должен быть заметно медленнее обычного массива и, конечно же, не хуже вашей собственной реализации массива переменных размеров с использованием указателей.

Answer 5

Просто хотел бы добавить к ответам других несколько вещей, которые, как мне кажется, важны.

Во-первых, по умолчанию (в реализациях, которые я видел) sizeof(std::vector<T>) является постоянным и состоит из трех указателей. Ниже приводится выдержка из GCC 4.7.2 заголовка STL, соответствующие части:

template<typename _Tp, typename _Alloc> 
struct _Vector_base 
{ 
... 
struct _Vector_impl : public _Tp_alloc_type 
{ 
    pointer _M_start; 
    pointer _M_finish; 
    pointer _M_end_of_storage; 
    ... 
}; 
... 
_Vector_impl _M_impl; 
... 
}; 

template<typename _Tp, typename _Alloc = std::allocator<_Tp> > 
class vector : protected _Vector_base<_Tp, _Alloc> 
{ 
... 
}; 

Вот где три указателя берутся. По-моему, их имена ясны. Но есть и базовый класс - распределитель. Который берет меня к моему второму пункту.

Во-вторых, std::vector< T, Allocator = std::allocator<T>> принимает второй параметр шаблона, который является классом, который обрабатывает операции с памятью. Благодаря функциям этого класса вектор управления памятью. Существует распределитель STL по умолчанию std::allocator<T>>. Он не имеет данных, только функции, такие как allocate, destroy и т. Д. Он основывает свою обработку памяти на new/delete. Но вы можете написать свой собственный распределитель и поставить его на std::vector в качестве второго параметра шаблона. Он должен соответствовать определенным правилам, таким как функции, которые он предоставляет и т. Д., Но как управление памятью осуществляется внутри - это зависит от вас, если оно не нарушает логику std::vector. Он может ввести некоторые данные-члены, которые добавят к sizeof(std::vector) через наследование выше. Он также дает вам «контроль над каждым битом».