Классы unordered_map и unordered_multimap: ассоциативные массивы

Класс unordered_map реализует ассоциативный массив, в котором каждому ключу соответствует одно значение. Чтобы получить доступ к элементу, необходимо указать ключ, который использовался при сохранении элемента. В отличии от класса map для быстрого поиска элементов используется хеш-таблица, значения которой состоят из целых чисел (тип size_t). Класс unordered_multimap реализует ассоциативный массив, в котором одному ключу могут соответствовать несколько значений. Работа с классами производится аналогичным образом, поэтому в этом разделе мы рассмотрим только возможности класса unordered_map.

Прежде чем использовать классы, необходимо в начало программы добавить инструкцию:

#include <unordered_map>

Класс hash: хеш

Для быстрого поиска элементов в классах unordered_map и unordered_multimap используется хеш-таблица, значения которой состоят из целых чисел (тип size_t). Получить эти значения для основных типов позволяет класс hash. Прежде чем использовать класс, необходимо в начало программы добавить инструкцию:

#include <functional>

При объявлении переменной после названия класса внутри угловых скобок указывается элементарный тип данных или тип указателя. Чтобы получить хеш следует передать значение внутри круглых скобок. Для одного и того же значения хеш всегда будет одинаковым:

double n1 = 2.5, n2 = 3.2;
std::hash<double> double_hash;
std::cout << double_hash(n1) << std::endl; // 9366101741534969300
std::cout << double_hash(n1) << std::endl; // 9366101741534969300
std::cout << double_hash(n2) << std::endl; // 12593207821162580661

В других заголовочных файлах существуют реализации для классов string, wstring, u16string, u32string, vector<bool>, bitset, unique_ptr, shared_ptr и др. Пример получения хеша для строки:

std::string str1("string1"), str2("string2");
std::hash<std::string> str_hash;
std::cout << str_hash(str1) << std::endl;  // 3934116607259143573
std::cout << str_hash(str2) << std::endl;  // 5981711598734670988

Создание объекта

Объявление класса unordered_map:

template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
         typename _Pred = equal_to<_Key>,
         typename _Alloc = allocator<pair<const _Key, _Tp> > >
   class unordered_map;

Основные псевдонимы для типов:

typedef typename _Key key_type;
typedef typename _Tp mapped_type;
typedef pair<const _Key, _Tp> value_type;
typedef typename _Hash hasher;
typedef typename _Pred key_equal;
typedef typename _Alloc allocator_type;

Создать экземпляр класса unordered_map можно следующими способами (полный список конструкторов смотрите в документации):

  • объявить переменную без инициализации. Для этого перед названием переменной указывается название класса, а после названия внутри угловых скобок через запятую задаются типы данных ключа и значения. В этом случае словарь не содержит элементов. Пример объявления без инициализации:
std::unordered_map<std::string, int> m;
m["one"] = 1;
m["two"] = 2;
std::cout << m["one"] << std::endl;    // 1
std::cout << m["two"] << std::endl;    // 2

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

// #include <functional>
std::unordered_map<std::string, int,
     std::hash<std::string>, std::equal_to<std::string> > m;
  • указать объект класса unordered_map внутри круглых скобок или после оператора = (доступны конструкторы копирования и перемещения):
std::unordered_map<int, int> m1;
m1[0] = 1;
m1[1] = 2;
std::unordered_map<int, int> m2(m1);
std::cout << m2[0] << std::endl;    // 1
std::cout << m2[1] << std::endl;    // 2
  • указать диапазон внутри контейнера с помощью итераторов. В первом параметре передается итератор, указывающий на начало диапазона, а во втором параметре — итератор, указывающий на конец диапазона. Пример:
typedef struct std::pair<int, int> PAIR;
std::unordered_map<int, int> m1;
m1.insert(PAIR(0, 10));
m1.insert(PAIR(1, 20));
std::unordered_map<int, int> m2(m1.begin(), m1.end());
std::cout << m2[0] << std::endl;    // 10
std::cout << m2[1] << std::endl;    // 20
  • указать список инициализации, состоящий из объектов класса pair:
typedef struct std::pair<int, int> PAIR;
std::unordered_map<int, int> m = {PAIR(0, 10), PAIR(1, 20)};
std::cout << m[0] << std::endl;    // 10
std::cout << m[1] << std::endl;    // 20

Вместо объектов класса pair можно указать ключи и значения через запятую внутри фигурных скобок:

std::unordered_map<int, int> m = { {0, 10}, {1, 20} };
std::cout << m[0] << std::endl;    // 10
std::cout << m[1] << std::endl;    // 20

Над двумя объектами класса unordered_map определены операции == и !=. Кроме того, один объект можно присвоить другому объекту. В этом случае выполняется поэлементное копирование (оператор копирования) или перемещение элементов (оператор перемещения). Пример:

std::unordered_map<int, int> m1, m2;
m1[0] = 1;
m1[1] = 2;
m2 = m1;
for (auto &el : m2) {
   std::cout << el.first << "=>" << el.second << ' ';
}
std::cout << std::endl; // 1=>2 0=>1

Доступно также присваивание элементов из списка инициализации:

std::unordered_map<int, int> m;
m = { {0, 10}, {1, 20} };
std::cout << m[0] << std::endl;    // 10
std::cout << m[1] << std::endl;    // 20

Вставка элементов

Вставить элемент можно указав ключ внутри квадратных скобок. Значение элемента задается после оператора присваивания. Если ключ уже существует, то вместо вставки элемента производится изменение значения. Пример:

std::unordered_map<std::string, int> m;
m["one"] = 1;                       // Вставка
m["two"] = 2;
std::cout << m["one"] << std::endl; // 1
std::cout << m["two"] << std::endl; // 2
m["two"] = 0;                       // Изменение значения
std::cout << m["two"] << std::endl; // 0
Примечание

Вставить элементы позволяют следующие методы:

  • insert() — вставляет один или несколько элементов. Прототипы метода:
pair<iterator, bool> insert(const value_type &x);
template<typename _Pair>
   pair<iterator, bool> insert(_Pair &&x);
iterator insert(const_iterator pos, const value_type &x);
template<typename _Pair>
   iterator insert(const_iterator pos, _Pair &&x);
template<typename _InputIterator>
   void insert(_InputIterator first, _InputIterator last);
void insert(initializer_list<value_type> list);

Первые два прототипа вставляют экземпляр класса pair и возвращают объект того же класса. Через свойство first будет доступен итератор, указывающий на вставленный элемент, а через свойство second — логическое значение true, если элемент вставлен, и false — в противном случае. Обратите внимание на то, что вставить можно только элемент, ключ которого не содержится в словаре. Пример:

std::unordered_map<std::string, int> m;
auto pr = m.insert(std::make_pair("one", 1));
if (pr.second) { // Проверка успешности вставки
   std::cout << (pr.first)->first << "=>"
             << (pr.first)->second << std::endl;
} // one=>1
else std::cout << "Error" << std::endl;

Обратите внимание на то, что метод insert() в классе unordered_multimap возвращает итератор, а не объект класса pair. Прототипы метода в классе unordered_multimap:

iterator insert(const value_type &x);
template<typename _Pair>
   iterator insert(_Pair &&x);

Можно вставить элементы, имеющие одинаковый ключ:

std::unordered_multimap<std::string, int> m;
m.insert(std::make_pair("one", 1));
auto it = m.insert(std::make_pair("one", 2));
std::cout << it->first << "=>"
          << it->second << std::endl; // one=>2

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

std::unordered_map<std::string, int> m;
m.insert(std::make_pair("1", 1));
m.insert(std::make_pair("2", 2));
m.insert(m.begin(), std::make_pair("0", 0));
for (auto &el : m) {
   std::cout << el.first << "=>" << el.second << ' ';
}
std::cout << std::endl; // 0=>0 1=>1 2=>2

Пятый прототип вставляет элементы из диапазона, ограниченного итераторами first и last:

std::unordered_map<std::string, int> m1, m2;
m1.insert(std::make_pair("0", 0));
m1.insert(std::make_pair("1", 1));
m1.insert(std::make_pair("2", 2));
m2.insert(m1.begin(), m1.end());
for (auto &el : m2) {
   std::cout << el.first << "=>" << el.second << ' ';
}
std::cout << std::endl; // 0=>0 1=>1 2=>2

Шестой прототип вставляет элементы из списка инициализации:

std::unordered_map<int, int> m;
m.insert({ {0, 10}, {1, 20} });
for (auto &el : m) {
   std::cout << el.first << "=>" << el.second << ' ';
}
std::cout << std::endl; // 1=>20 0=>10
  • emplace() — создает элемент и вставляет его в словарь. Метод возвращает объект класса pair. Через свойство first будет доступен итератор, указывающий на вставленный элемент, а через свойство second — логическое значение true, если элемент вставлен, и false — в противном случае. Обратите внимание на то, что вставить можно только элемент, ключ которого не содержится в словаре. Прототип метода:
template<typename... _Args>
   pair<iterator, bool> emplace(_Args &&... args);

Пример:

std::unordered_map<std::string, int> m;
m.emplace("1", 1);
m.emplace("2", 2);
for (auto &el : m) {
   std::cout << el.first << "=>" << el.second << ' ';
}
std::cout << std::endl; // 2=>2 1=>1

Обратите внимание на то, что метод emplace() в классе unordered_multimap возвращает итератор, а не объект класса pair. Прототип метода в классе unordered_multimap:

template<typename... _Args>
   iterator emplace(_Args &&... args);

Можно вставить элементы, имеющие одинаковый ключ:

std::unordered_multimap<std::string, int> m;
m.emplace("1", 1);
m.emplace("2", 2);
auto it = m.emplace("2", 3);         // OK
std::cout << it->first << "=>"
          << it->second << std::endl; // 2=>3
for (auto &el : m) {
   std::cout << el.first << "=>" << el.second << ' ';
}
std::cout << std::endl; // 1=>1 2=>3 2=>2
  • emplace_hint() — аналогичен методу emplace(), но дополнительно позволяет подсказать позицию вставки с помощью итератора. Метод возвращает итератор на вставленный элемент или на существующий элемент (вставить элемент с одинаковым ключом нельзя). Прототип метода:
template<typename... _Args>
   iterator emplace_hint(const_iterator pos, _Args &&... args);

Пример:

std::unordered_map<std::string, int> m;
m.emplace_hint(m.begin(), "1", 1);
m.emplace_hint(m.end(), "2", 2);
for (auto &el : m) {
   std::cout << el.first << "=>" << el.second << ' ';
}
std::cout << std::endl; // 2=>2 1=>1
  • swap() — меняет элементы двух контейнеров местами. Прототип метода:
void swap(unordered_map &x);

Пример:

std::unordered_map<std::string, int> m1, m2;
m1.emplace("1", 1); m1.emplace("2", 2);
m2.emplace("3", 3); m2.emplace("4", 4);
m1.swap(m2);
for (auto &el : m1) {
   std::cout << el.first << "=>" << el.second << ' ';
}
std::cout << std::endl; // 4=>4 3=>3
for (auto &el : m2) {
   std::cout << el.first << "=>" << el.second << ' ';
}
std::cout << std::endl; // 2=>2 1=>1

Вместо метода swap() можно воспользоваться одноименной функцией:

std::swap(m1, m2);

Определение количества элементов

Для определения количества элементов предназначены следующие методы:

  • size() — возвращает количество элементов в словаре. Прототип метода:
size_type size() const noexcept;

Пример:

std::unordered_map<std::string, int> m;
m.emplace("1", 1); m.emplace("2", 2);
std::cout << m.size() << std::endl; // 2
  • empty() — возвращает значение true, если словарь не содержит элементов, и false — в противном случае. Прототип метода:
bool empty() const noexcept;

Пример:

std::unordered_map<std::string, int> m1, m2;
m1.emplace("1", 1);
std::cout << std::boolalpha;
std::cout << m1.empty() << std::endl; // false
std::cout << m2.empty() << std::endl; // true
  • max_size() — возвращает максимальное количество элементов, которое теоретически может содержаться в словаре. Прототип метода:
size_type max_size() const noexcept;

Пример:

std::unordered_map<std::string, int> m;
std::cout << m.max_size() << std::endl;
// 329406144173384850

Удаление элементов

Для удаления элементов предназначены следующие методы:

  • erase() — удаляет один элемент или элементы из диапазона. Прототипы метода:
size_type erase(const key_type &k);
iterator erase(const_iterator pos);
iterator erase(const_iterator first, const_iterator last);

Первый прототип удаляет элемент с указанным ключом и возвращает количество удаленных элементов:

std::unordered_map<std::string, int> m;
m.emplace("1", 1); m.emplace("2", 2);
std::cout << m.erase("1") << std::endl; // 1
std::cout << m.erase("1") << std::endl; // 0
for (auto &el : m) {
   std::cout << el.first << "=>" << el.second << ' ';
}
std::cout << std::endl; // 2=>2

Второй прототип удаляет элемент на который указывает итератор:

std::unordered_map<std::string, int> m;
m.emplace("1", 1); m.emplace("2", 2);
m.erase(m.begin());
for (auto &el : m) {
   std::cout << el.first << "=>" << el.second << ' ';
}
std::cout << std::endl; // 1=>1

Третий прототип удаляет элементы из диапазона, ограниченного итераторами first и last. Удалим все элементы:

std::unordered_map<std::string, int> m;
m.emplace("1", 1); m.emplace("2", 2);
m.erase(m.begin(), m.end());
std::cout << m.size() << std::endl; // 0
  • clear() — удаляет все элементы. Прототип метода:
void clear() noexcept;

Пример:

std::unordered_map<std::string, int> m;
m.emplace("1", 1); m.emplace("2", 2);
m.clear();
std::cout << m.size() << std::endl; // 0

Доступ к элементам

К любому элементу словаря можно обратиться как к элементу массива. Достаточно указать его ключ внутри квадратных скобок. Можно как получить значение, так и изменить его. Если производится присваивание значения по ключу и ключа не существует, то производится вставка элемента. Если элемент уже существует, то его значение изменяется на новое. Если производится получение значения по ключу и ключа не существует, то элемент вставляется со значением по умолчанию для типа, а затем это значение возвращается. Пример:

std::unordered_map<std::string, int> m;
m["one"] = 1;   // Вставляем новый элемент
m["two"] = 2;
m["one"] = 100; // Изменяем значение существующего элемента
std::cout << m["one"] << std::endl; // 100
std::cout << m["two"] << std::endl; // 2
std::cout << m["key"] << std::endl; // 0 (элемент вставлен)
for (auto &el : m) {
   std::cout << el.first << "=>" << el.second << ' ';
}
std::cout << std::endl; // key=>0 one=>100 two=>2
Примечание

Для доступа к элементам предназначены следующие методы:

  • at() — возвращает ссылку на элемент, ключ которого соответствует значению k. Метод позволяет как получить значение, так и изменить его. Если ключ не существует, то генерируется исключение out_of_range. Прототипы метода:
mapped_type &at(const key_type &k);
const mapped_type &at(const key_type &k) const;

Пример:

std::unordered_map<std::string, int> m;
// m.at("one") = 1; // Ошибка. Ключ не существует
m["one"] = 1;       // Вставляем новый элемент
m.at("one") = 100;  // Изменяем значение элемента
std::cout << m.at("one") << std::endl; // 100
  • count() — возвращает количество элементов, у которых ключ соответствуют значению k. Прототип метода:
size_type count(const key_type &k) const;

Пример:

std::unordered_map<std::string, int> m;
m["one"] = 1;
std::cout << m.count("one") << std::endl; // 1
std::cout << m.count("two") << std::endl; // 0
  • find() — возвращает итератор, установленный на элемент, ключ которого соответствует значению k. Если элемент не найден, то метод возвращает итератор, указывающий на позицию после последнего элемента. Прототипы метода:
iterator find(const key_type &k);
const_iterator find(const key_type &k) const;

Пример:

std::unordered_map<std::string, int> m;
std::unordered_map<std::string, int>::iterator i;
m["one"] = 1;
i = m.find("one");
if (i != m.end()) {
   std::cout << i->second << std::endl; // 1
}
i = m.find("two");
if (i == m.end()) {
   std::cout << "No" << std::endl;      // No
}
  • equal_range() — возвращает экземпляр класса pair. Через свойство first будет доступен итератор, ссылающийся на первый элемент с указанным ключом, а через свойство second — итератор, ссылающийся на позицию после последнего элемента с указанным ключом. Если ключ отсутствует в словаре, то оба итератора будут ссылаться на значение, возвращаемое методом end(). Прототипы метода:
pair<iterator, iterator> equal_range(const key_type &k);
pair<const_iterator, const_iterator>
     equal_range(const key_type &k) const;

Пример:

typedef std::unordered_map<int, int> M;
M m;
m.emplace(0, 0); m.emplace(1, 1);
m.emplace(4, 4); m.emplace(5, 5);
std::pair<M::iterator, M::iterator> pr;
pr = m.equal_range(1);   // Ключ существует
if (pr.first != m.end()) {
   M::iterator it1, it2;
   for (it1 = pr.first, it2 = pr.second; it1 != it2; ++it1) {
      std::cout << it1->first << "=>" << it1->second << ' ';
   }
   std::cout << std::endl; // 1=>1
}
pr = m.equal_range(2);   // Ключ не существует
if (pr.first == m.end()) {
   std::cout << "No" << std::endl;  // No
}
  • begin(), end(), cbegin() и cend() — возвращают итераторы (см. разд. 16.1.1). Обратите внимание: обратные итераторы не поддерживаются. Перебор возможен только в прямом порядке. Выведем ключ и значение первого элемента:
std::unordered_map<int, int> m;
m[0] = 5; m[1] = 6; m[2] = 7;
std::unordered_map<int, int>::iterator it = m.begin();
std::cout << it->first << std::endl;  // 2
std::cout << it->second << std::endl; // 7

Обратите внимание: итераторы не поддерживают операторы +, - и --. Для перемещения итератора нужно использовать оператор ++ или функцию advance(). Пример доступа к третьему элементу словаря:

std::unordered_map<int, int> m;
m[0] = 5; m[1] = 6; m[2] = 7; m[3] = 8;
std::unordered_map<int, int>::iterator it = m.begin();
std::advance(it, 2);
std::cout << it->first << std::endl;  // 0
std::cout << it->second << std::endl; // 5

Вместо методов begin() и end() можно воспользоваться одноименными функциями. Выведем ключ и значение первого элемента:

std::unordered_map<int, int> m;
m[0] = 5; m[1] = 6; m[2] = 7; m[3] = 8;
std::unordered_map<int, int>::iterator it = std::begin(m);
std::cout << it->first << std::endl;  // 3
std::cout << it->second << std::endl; // 8

Перебор элементов

Перебрать все элементы можно с помощью цикла for each, итераторов и алгоритма for_each(). Обратите внимание: перебор элементов возможен только в прямом направлении, кроме того, порядок следования элементов может быть произвольным. Пример использования цикла for each (внутри тела цикла можно изменить значение элемента, но ключ изменить нельзя):

std::unordered_map<int, int> m = { {0, 5}, {1, 6}, {2, 7} };
// Умножаем все значения на 2
for (auto &el : m) {
   el.second *= 2;
}
// Выводим значения всех элементов
for (auto &el : m) {
   std::cout << el.first << "=>" << el.second << ' ';
}
std::cout << std::endl; // 2=>14 1=>12 0=>10

Пример перебора элементов с помощью итераторов и цикла for:

std::unordered_map<int, int> m = { {0, 5}, {1, 6}, {2, 7} };
std::unordered_map<int, int>::iterator it1, it2;
for (it1 = m.begin(), it2 = m.end(); it1 != it2; ++it1) {
   std::cout << it1->first << "=>" << it1->second << ' ';
}
std::cout << std::endl; // 2=>7 1=>6 0=>5

Пример перебора элементов с помощью итераторов и цикла while:

std::unordered_map<int, int> m = { {0, 5}, {1, 6}, {2, 7} };
auto it1 = m.begin(), it2 = m.end();
while (it1 != it2) {
   std::cout << it1->first << "=>" << it1->second << ' ';
   ++it1;
}
std::cout << std::endl; // 2=>7 1=>6 0=>5

С помощью алгоритма for_each() умножим значение каждого элемента на 2, а затем выведем все ключи и значения в окно консоли:

std::unordered_map<int, int> m = { {0, 5}, {1, 6}, {2, 7} };
// Умножаем значения всех элементов на 2
std::for_each( m.begin(), m.end(),
               [](auto &el) { el.second *= 2; } );
// Выводим значения всех элементов
std::for_each( m.begin(), m.end(),
     [](auto &el){
        std::cout << el.first << "=>" << el.second << ' '; } );
std::cout << std::endl; // 2=>14 1=>12 0=>10
Примечание

Учебник C++ (Qt Creator и MinGW)
Учебник C++ (Qt Creator и MinGW) в формате PDF

Помощь сайту

ЮMoney (Yandex-деньги): 410011140483022

ПАО Сбербанк:
Счет: 40817810855006152256
Реквизиты банка:
Наименование: СЕВЕРО-ЗАПАДНЫЙ БАНК ПАО СБЕРБАНК
Корреспондентский счет: 30101810500000000653
БИК: 044030653
КПП: 784243001
ОКПО: 09171401
ОКОНХ: 96130
Скриншот реквизитов