Контейнеры стандартной библиотеки C++. Микросправочник. Ассоциативные контейнеры. Ч.2

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

std::set

set, unordered_set, multiset и unordered_multiset - все они являются контейнерами ассоциативного типа данных в STL C++, используемыми для хранения уникальных элементов.

• set хранит уникальные элементы в отсортированном порядке, при этом вставка и удаление элементов занимают O(log n) времени.
• unordered_set хранит неупорядоченные уникальные элементы, при этом вставка и удаление элементов занимают O(1) времени в среднем случае, благодаря использованию хеш-таблицы.
• multiset хранит неупорядоченные элементы, допускающие повторения. Элементы могут добавляться и удаляться за O(log n) времени.
• unordered_multiset хранит неупорядоченные элементы, допускающие повторения. Вставка и удаление элементов занимают O(1) времени в среднем случае, благодаря использованию хеш-таблицы.

Таким образом, основное отличие между set и unordered_set, а также между multiset и unordered_multiset заключается в том, что первые используют упорядоченное хранение элементов, тогда как вторые - неупорядоченное. При этом, unordered_set и unordered_multiset имеют более быстрый доступ к элементам, но могут потребовать больше памяти. Использование того или иного контейнера зависит от конкретной задачи и ее требований к производительности.

std::map

map, unordered_map, multimap и unordered_multimap - все они являются контейнерами ассоциативного типа данных в STL C++, используемыми для хранения пар ключ-значение.

• map хранит уникальные ключи, каждый из которых соотносится только с одним значением. Элементы в map всегда отсортированы по возрастанию ключа.
• unordered_map хранит неупорядоченные пары ключ-значение. Поиск элемента осуществляется за константное время, но порядок элементов в unordered_map не гарантирован и может меняться при изменении контейнера.
• multimap также хранит пары ключ-значение, но допускает наличие нескольких значений, связанных с одним и тем же ключом. Элементы в multimap всегда отсортированы по ключу, невзирая на количество значений, связанных с каждым ключом.
• unordered_multimap хранит неупорядоченные пары ключ-значение, но допускает наличие нескольких значений, связанных с одним и тем же ключом. Поиск элемента осуществляется за константное время, но порядок элементов в unordered_multimap не гарантирован и может меняться при изменении контейнера.

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

Скорость доступа к элементам зависит от конкретной реализации и хеш-функции в случае unordered_map и unordered_multimap. Однако, в целом можно сказать, что для поиска в unordered_map и unordered_multimap требуется O(1) времени в среднем случае, в то время как для map и multimap скорость поиска зависит от размера контейнера и требует O(log n) времени.

К тому же, unordered_map и unordered_multimap не гарантируют сохранение порядка элементов, в отличие от map и multimap, что может быть важно в некоторых случаях.

Таким образом, при поиске по ключу в больших контейнерах unordered_map и unordered_multimap могут быть более быстрыми, но могут потребовать больше памяти, чем map и multimap. Однако, если порядок элементов важен или размер контейнера небольшой, то лучше использовать map и multimap.