Класс map и multimap: ассоциативные массивы

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

#include <map>

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

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

template <typename _Key, typename _Tp, typename _Compare = less<_Key>,
          typename _Alloc = allocator<pair<const _Key, _Tp> > >
   class map;

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

typedef _Key key_type;
typedef _Tp mapped_type;
typedef pair<const _Key, _Tp> value_type;
typedef _Compare key_compare;
typedef _Alloc allocator_type;

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

  • объявить переменную без инициализации. Для этого перед названием переменной указывается название класса, а после названия внутри угловых скобок через запятую задаются типы данных ключа и значения. В этом случае словарь не содержит элементов. Пример объявления без инициализации:
std::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::map<std::string, int, std::less<std::string> > m;
  • указать объект класса map внутри круглых скобок или после оператора = (доступны конструкторы копирования и перемещения):
std::map<int, int> m1;
m1[0] = 1;
m1[1] = 2;
std::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::map<int, int> m1;
m1.insert(PAIR(0, 10));
m1.insert(PAIR(1, 20));
std::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::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::map<int, int> m = { {0, 10}, {1, 20} };
std::cout << m[0] << std::endl;    // 10
std::cout << m[1] << std::endl;    // 20

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

std::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; // 0=>1 1=>2

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

typedef struct std::pair<int, int> PAIR;
std::map<int, int> m;
m = {PAIR(0, 10), PAIR(1, 20)};
std::cout << m[0] << std::endl;    // 10
std::cout << m[1] << std::endl;    // 20

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

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

std::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::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;
// Использование value_type
m.insert(std::map<std::string, int>::value_type("two", 2));
for (auto &el : m) {
   std::cout << el.first << "=>" << el.second << ' ';
}
std::cout << std::endl; // one=>1 two=>2

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

std::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::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; // 1=>1 2=>2

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

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

Пример:

std::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; // 1=>1 2=>2
  • emplace_hint() — аналогичен методу emplace(), но дополнительно позволяет подсказать позицию вставки с помощью итератора. Метод возвращает итератор на вставленный элемент или на существующий элемент (вставить элемент с одинаковым ключом нельзя). Прототип метода:
template<typename... _Args>
   iterator emplace_hint(const_iterator pos, _Args &&... args);

Пример:

std::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; // 1=>1 2=>2
  • swap() — меняет элементы двух контейнеров местами. Прототип метода:
void swap(map &x);

Пример:

std::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; // 3=>3 4=>4
for (auto &el : m2) {
   std::cout << el.first << "=>" << el.second << ' ';
}
std::cout << std::endl; // 1=>1 2=>2

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

std::swap(m1, m2);

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

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

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

Пример:

std::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::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::map<std::string, int> m;
std::cout << m.max_size() << std::endl;
// 256204778801521550

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

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

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

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

std::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::map<std::string, int> m;
m.emplace("1", 1); m.emplace("2", 2);
m.erase(--m.end());
for (auto &el : m) {
   std::cout << el.first << "=>" << el.second << ' ';
}
std::cout << std::endl; // 1=>1

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

std::map<std::string, int> m;
m.emplace("1", 1); m.emplace("2", 2);
m.emplace("3", 3); m.emplace("4", 4);
m.erase(++m.begin(), --m.end());
for (auto &el : m) {
   std::cout << el.first << "=>" << el.second << ' ';
}
std::cout << std::endl; // 1=>1 4=>4
  • clear() — удаляет все элементы. Прототип метода:
void clear() noexcept;

Пример:

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

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

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

std::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::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::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::map<std::string, int> m;
std::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
}
  • lower_bound() — возвращает итератор, установленный на элемент, ключ которого больше или равен значению k. Если элемент не найден, то метод возвращает итератор, указывающий на позицию после последнего элемента. Прототипы метода:
iterator lower_bound(const key_type &k);
const_iterator lower_bound(const key_type &k) const;

Пример:

std::map<int, int> m;
std::map<int, int>::iterator i;
m[0] = 0; m[1] = 1; m[4] = 4; m[5] = 5;
i = m.lower_bound(2);
if (i != m.end()) {
   std::cout << i->second << std::endl; // 4
}
i = m.lower_bound(1);
if (i != m.end()) {
   std::cout << i->second << std::endl; // 1
}
  • upper_bound() — возвращает итератор, установленный на элемент, ключ которого больше значения k. Если элемент не найден, то метод возвращает итератор, указывающий на позицию после последнего элемента. Прототипы метода:
iterator upper_bound(const key_type &k);
const_iterator upper_bound(const key_type &k) const;

Пример:

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

Пример:

typedef std::map<int, int> M;
M m;
std::pair<M::iterator, M::iterator> pr;
m[0] = 0; m[1] = 1; m[4] = 4; m[5] = 5;
pr = m.equal_range(1);   // Ключ существует
if (pr.first != m.end()) {
   std::cout << pr.first->second << std::endl;  // 1
}
if (pr.second != m.end()) {
   std::cout << pr.second->second << std::endl; // 4
}
pr = m.equal_range(2);   // Ключ не существует
if (pr.first != m.end()) {
   std::cout << pr.first->second << std::endl;  // 4
}
if (pr.second != m.end()) {
   std::cout << pr.second->second << std::endl; // 4
}
  • begin(), end(), cbegin(), cend(), rbegin(), rend(), crbegin() и crend() — возвращают итераторы (см. разд. 16.1.1). Выведем ключ и значение первого элемента:
std::map<int, int> m;
m[0] = 5; m[1] = 6; m[2] = 7;
std::map<int, int>::iterator it = m.begin();
std::cout << it->first << std::endl;  // 0
std::cout << it->second << std::endl; // 5

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

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

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

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

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

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

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

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

std::map<int, int> m;
m[0] = 5; m[1] = 6; m[2] = 7;
std::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; // 0=>5 1=>6 2=>7

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

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

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

// #include <algorithm>
std::map<int, int> m;
m[0] = 5; m[1] = 6; m[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; // 0=>10 1=>12 2=>14

Класс multimap: ассоциативный массив с повторяющимися ключами

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

#include <map>

Создание экземпляра класса multimap выполняется точно так же как и создание экземпляра класса map. Над двумя объектами класса multimap определены операции ==, !=, <, <=, > и >=. Кроме того, один объект можно присвоить другому объекту.

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

iterator insert(const value_type &x);
template<typename _Pair>
   iterator 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. В отличие от аналогичных прототипов в классе map метод insert() возвращает итератор, а не объект класса pair. Третий и четвертый прототипы позволяют подсказать позицию вставки с помощью итератора pos. Пятый прототип вставляет элементы из диапазона, ограниченного итераторами first и last. Шестой прототип вставляет элементы из списка инициализации. Для вставки элементов вместо метода insert() можно использовать методы emplace() (возвращает итератор, ссылающийся на вставленный элемент) и emplace_hint(). Пример:

std::multimap<std::string, int> m;
auto it = m.insert(std::make_pair("one", 1));
std::cout << it->first << "=>" << it->second << std::endl;
// one=>1
m.insert({{"two", 2}, {"s", 5}});
// Вставка повторяющегося ключа
m.insert(m.begin(), std::make_pair("one", 6));
// Использование метода emplace()
m.emplace("2", 2);
// Использование метода emplace_hint()
m.emplace_hint(m.end(), "w", 7);
for (auto &el : m) { // Перебор элементов
   std::cout << el.first << "=>" << el.second << ' ';
}
std::cout << std::endl; // 2=>2 one=>6 one=>1 s=>5 two=>2 w=>7

Обратите внимание на то, что для вставки и извлечения элементов нельзя использовать оператор [], так как ключи могут повторяться. Кроме того, класс multimap не имеет метода at(). Чтобы получить доступ к элементам следует воспользоваться методами find(), lower_bound(), upper_bound() и equal_range(). Получить количество элементов с указанным ключом позволяет метод count(). Пример:

typedef std::multimap<std::string, int> M;
M m;
m.emplace("one", 1); m.emplace("one", 2);
m.emplace("one", 3); m.emplace("two", 2);
std::cout << m.count("one") << std::endl; // 3
std::cout << m.count("two") << std::endl; // 1
// Получаем все элементы с ключом one
std::pair<M::iterator, M::iterator> pr = m.equal_range("one");
for (auto it = pr.first; it != pr.second; ++it) {
   std::cout << it->first << "=>" << it->second << ' ';
}
std::cout << std::endl; // one=>1 one=>2 one=>3

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

Помощь сайту

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

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