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

Давайте сначала узнаем о карте, затем мы перейдем к изучению unordered_map, а затем мы увидим различия между map и unordered_map.

Карты – это ассоциативные контейнеры, в которых хранятся элементы в сопоставленном виде. Карта – это упорядоченная последовательность уникальных ключей. Каждый элемент имеет значение ключа и сопоставленное значение. Никакие два сопоставленных значения не могут иметь одинаковые значения ключа. Карта реализована в виде сбалансированной древовидной структуры, поэтому можно поддерживать порядок между элементами (за счет определенного обхода дерева). Временная сложность операций с картами составляет O (log n).

Список всех функций карты

insert() — это встроенная функция C++ STL, которая используется для вставки элементов с определенным ключом в контейнер карты —> O(log n)

count() – это встроенная функция C++ STL, которая возвращает 1, если элемент с ключом K присутствует в контейнере карты. Возвращает 0, если элемент с ключом K отсутствует в контейнере.

equal_range() Возвращает итератор пар. Пара относится к границам диапазона, включающего все элементы в контейнере, у которых есть ключ, эквивалентный k.

erase() — это встроенная функция C++ STL, которая используется для стирания элемента из контейнера. Его можно использовать для стирания ключей, элементов в любой указанной позиции или заданном диапазоне –> O(log n)

rend() Возвращает обратный итератор, указывающий на теоретический элемент прямо перед первой парой ключ-значение в карте (которая считается его обратным концом).

rbegin()Возвращает обратный итератор, указывающий на последний элемент карты.

find() Возвращает итератор к элементу с ключом-значением g на карте, если он найден, иначе возвращает итератор в конец.

crbegin() и crend() crbegin() возвращает постоянный обратный итератор, ссылающийся на последний элемент в контейнере карты. crend() возвращает постоянный обратный итератор, указывающий на теоретический элемент перед первым элементом на карте.

cbegin() и cend() cbegin() возвращает постоянный итератор, ссылающийся на первый элемент в контейнере карты. cend() возвращает постоянный итератор, указывающий на теоретический элемент, который следует за последним элементом в мультикарте.

emplace() Вставляет ключ и его элемент в контейнер карты.

max_size() Возвращает максимальное количество элементов, которые может содержать контейнер карты –> O(1)

upper_bound() Возвращает итератор к первому элементу, который эквивалентен отображенному значению с ключом-значением "g" или определенно будет идти после элемента с ключом-значением "g" на карте.

operator= Назначает содержимое контейнера другому контейнеру, заменяя его текущее содержимое.

lower_bound() Возвращает итератор к первому элементу, который эквивалентен отображенному значению с ключом-значением 'g' или определенно не будет идти перед элементом с ключом-значением 'g' на карте — › O(log n)

emplace_hint() Вставляет ключ и его элемент в контейнер карты с заданной подсказкой.

value_comp() Возвращает объект, определяющий порядок расположения элементов на карте (по умолчанию ‘‹’).

key_comp() Возвращает объект, определяющий порядок расположения элементов на карте (по умолчанию ‘‹’).

size() Возвращает количество элементов на карте. map::empty() Возвращает, является ли карта пустой

begin() и end() begin() возвращает итератор к первому элементу карты. end() возвращает итератор к теоретическому элементу, который следует за последним элементом на карте.

operator[]Этот оператор используется для ссылки на элемент, присутствующий в позиции, заданной внутри оператора.

clear() Удаляет все элементы с карты.

at() и swap()функция at() используется для возврата ссылки на элемент, связанный с ключом k. Функция swap() используется для обмена содержимым двух карт, но карты должны быть одного типа, хотя размеры могут различаться.

unordered_map – это связанный контейнер, в котором хранятся элементы, сформированные комбинацией "ключ-значение" и сопоставленного значения. Значение ключа используется для уникальной идентификации элемента, а сопоставленное значение — это содержимое, связанное с ключом. И ключ, и значение могут быть любого типа, предопределенными или определенными пользователем. Внутренне unordered_map реализован с использованием хеш-таблицы, ключ, предоставленный для сопоставления, хэшируется в индексы хеш-таблицы, поэтому производительность структуры данных во многом зависит от хэш-функции, но в среднем стоимость поиска, вставки и удалить из хеш-таблицы — O(1).

Список всех функций unordered_map

at() Эта функция unordered_map в C++ возвращает ссылку на значение с элементом в качестве ключа k.

begin() Возвращает итератор, указывающий на первый элемент в контейнере в контейнере unordered_map.

end() Возвращает итератор, указывающий на позицию после последнего элемента в контейнере в контейнере unordered_map.

bucket() Возвращает номер корзины, в которой находится элемент с ключом k на карте.

bucket_count Bucket_count используется для подсчета общего количества запросов. ведер в unordered_map. Для передачи в эту функцию не требуется никаких параметров.

bucket_size Возвращает количество элементов в каждом сегменте unordered_map.

count() Подсчитывает количество элементов, присутствующих в unordered_map с заданным ключом.

equal_range Возвращает границы диапазона, включающего все элементы в контейнере с ключом, равным k.

find() Возвращает итератор к элементу.

empty() проверяет, пуст ли контейнер в контейнере unordered_map.

erase() стереть элементы в контейнере в контейнере unordered_map.

Теперь давайте посмотрим на различия

Используйте std::map, когда

  • Вам нужны упорядоченные данные.
  • Вам нужно будет распечатать/получить доступ к данным (в отсортированном порядке).
  • Вам нужен предшественник/преемник элементов.

Используйте std::unordered_map, когда

  • Вам нужно вести подсчет некоторых данных (пример — строки) и не требуется упорядочение.
  • Вам нужен доступ к одному элементу, т.е. без обхода.

Удачного обучения!!