Контейнеры в STL C++

Question

Для 100 элементов какой контейнер из них: карта, набор, список, вектор займет самое нижнее пространство памяти? Другими словами, когда мы нажимаем 100 элементов на карту контейнера, набор, список и вектор, который из этого занимает самое низкое пространство в памяти? например sizeof (int) занимает 4Bytes, sizeof (short) занимает 2Bytes, и вопрос в том, какой из этих контейнеров занимает самую низкую память (самая низкая стоимость памяти является для меня самой важной)? Заранее спасибо.

Answer 1

Как правило, сокращение от vector будет иметь наименьшие служебные данные пространства для любого контейнера последовательности, поскольку, кроме нескольких указателей и/или счетчиков, единственными служебными данными пространства будут пространство для самих элементов (и любое пространство, используемое распределителем, которое будет неизбежно для контейнеров STL, которые вы описываете). map, set и list все дополнительные указатели для каждого добавленного элемента. (И map также нужно будет удерживать тип ключа вместе с типом значения.) Чтобы быть педантичным, вы не можете на самом деле push_back в set или map, хотя вы можете в них insert.

С другой стороны, vector, который не сжимается до места размещения, обычно будет чрезмерно распределен, как правило, около 1,5, но, возможно, до 2 раз (возможно, для некоторых реализаций) требуемое пространство, чтобы амортизировать затраты на добавление к нему, в то время как контейнеры на основе узлов, такие как list, set, или map обычно не будут.

Если это вызывает беспокойство, вы можете подумать о deque, который имеет некоторые накладные расходы на единицу (как правило, намного меньше одного указателя на элемент), но имеет гораздо более жесткую привязку к его перераспределению, которое не будет расти линейно с размером последовательности.

Однако пространство над головой контейнера, как правило, не является основным критерием, используемым, чтобы решить, между контейнерами, таких как vector, set, list или map. Требования шаблона использования часто более значительны. Например, вам нужно иметь возможность удалять произвольные элементы в постоянное время или без аннулирования итераторов или ссылок? Если да, то vector не подходит. Нужно ли вам вставлять/добавлять без аннулирования итераторов или ссылок? Если да, то vector не подходит. Вам нужен эффективный поиск (особенно в сочетании с вставками и удалениями)? Если это так, list является неуместным, и vector, вероятно, также не подходит, если повторная сортировка последовательности не является жизнеспособной для вашего шаблона использования. Вам нужен контроль над порядком последовательности? Если да, то map и set будут изменять порядок элементов для вас и, вероятно, неуместны.