Я нашел различные ресурсы, в которых указана временная сложность различных контейнеров C++ STL. Где я могу найти космические сложности, связанные с использованием контейнеров C++ STL?
Я знаю, что для большинства контейнеров отношения линейны по отношению к количеству содержащихся элементов. Но как насчет контейнеров, использующих хеш-функцию? Можно ли в таком случае дать какие-то гарантии?
std::map, которая удваивает размер выделенного узла при каждом выделении и просто позволяет дополнительной памяти не использоваться. Поскольку время выделения или освобождения блока памяти не зависит от размера этого блока (если не принимать во внимание возможную перегрузку диска), такая реализация вполне удовлетворит требованиям временной сложности. 05.09.2014 Для каждого контейнера STL есть два источника ограничений сложности. Во-первых, это то, что требует стандарт. Хорошим (и почти всегда правильным) источником для этого является cppreference.com, например. http://en.cppreference.com/w/cpp/container, если вы не т есть сам стандарт. Во-вторых, вещи, не указанные в стандарте, определяются реализацией. Эти реализации в основном очень эффективны, учитывая их многоцелевой характер.
Чтобы ответить на ваш вопрос коротким ответом: да, вы можете ожидать линейного пространства. Но детали немного сложнее.
Беглый взгляд на Стандарт (23.2.1 Общие требования к контейнерам) гласит:
Все требования к сложности в этом разделе сформулированы исключительно с точки зрения количества операций над содержащимися объектами.
Раздел 23.2.5 (Неупорядоченные ассоциативные контейнеры) гласит:
В наихудшем случае сложность большинства операций линейна, но в среднем все происходит намного быстрее.
Стандарт продолжается и определяет некоторые аспекты неупорядоченных ассоциативных контейнеров более подробно. Внимательно изучив сложности операций, мы можем сделать кое-что для пространства. Копнув немного дальше (конструкторы 23.5.4.2 unordered_map), мы обнаружим:
Создает пустую карту unordered_map, используя указанную хеш-функцию, функцию равенства ключей и распределитель, а также используя не менее n сегментов. Если n не указано, количество сегментов определяется реализацией. Затем вставляет элементы из диапазона [f, l). max_load_factor() возвращает 1,0. Сложность: линейная в среднем, квадратичная в худшем случае.
Квадратичное время происходит для патологически плохой хеш-функции. Средний случай — это то, что вы должны ожидать, а именно, линейное время подразумевает линейное пространство. Наихудший случай возникает, когда хэш-карта выходит за пределы и ее необходимо реконструировать (да, говоря небрежно).
Для доступа к элементу мы получаем аналогичную вещь:
Сложность: средний случай O(1), худший случай O(size()).
Кроме того, стандарт говорит, что реализация должна использовать структуру данных с сегментами. Элементы хешируются в ведра. Этим сегментам также потребуется место, и в зависимости от того, как вы инициализируете unordered_map, количество сегментов определяется реализацией. Таким образом, эффективные реализации будут использовать пространство O(n+N), где n — количество элементов, а N — количество сегментов.
Надеюсь, это немного проясняет ситуацию.
Я искал ответ на пространственную сложность ассоциативного контейнера set. Надеюсь это поможет.
Содержание ниже частично ответило на вопрос.
setВ этом сообщении пространственная сложность набора stl? из-за структуры данных set (красный -черное дерево), сложность пространства обычно составляет O(n)
mapСтруктура данных map и set представляет собой красно-черное дерево, поэтому пространственная сложность map обычно равна O(n), но это зависит от реальных случаев (см.: пространственная сложность карты).
