5. Контейнер map

Основные сведения

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

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

Отображение хранит пары “ключ-значение” с уникальными ключами, отсортированными по значениям ключей.

map

Создание экземпляра класса pair

Класс pair (пара) стандартной библиотеки С++ позволяет нам определить одним объектом пару значений, если между ними есть какая-либо семантическая связь. Эти значения могут быть одинакового или разного типа. Например, инструкция

std::pair<std::string, int> pr("Key", 10);

создает объект pr типа pair, состоящий из двух значений.

Отдельные части пары могут быть получены с помощью членов first и second:

#include <iostream>

int main() {
  std::pair<std::string, int> pr("Key", 10);
  std::cout << "pr: " << pr.first << ' ' << pr.second << std::endl;
}

Получим в результате:

pr: Key 10

Итак, map содержит пары (объекты класса-шаблона pair), каждая пара состоит из ключа (first) и значения (second), ассоциированного с ключом.

Создание экземпляра класса map

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

объявить экземпляр класса map без инициализации. Для этого перед названием переменной указывается название класса. После названия переменной внутри угловых скобок через запятую задаются типы данных ключа и значения. В этом случае объект не содержит элементов. Пример объявления без инициализации:
```
std::map<std::string, int> m;
```
указать объект класса map внутри круглых скобок или после оператора =:
```
std::map<std::string, int> m1;
std::map<std::string, int> m2(m1);
std::map<std::string, int> m3 = m1;
```

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

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

#include <iostream>
#include <map>

int main() {
  std::map<std::string, int> m;
  std::map<std::string, int>::iterator i;
  m["one"] = 0;  // заполнение в контейнер
  m["two"] = 2;  // заполнение в контейнер
  m["one"] = 1;  // изменение значения по ключу

  for (i = m.begin(); i != m.end(); i++) {
    std::cout << i->first << " -> " << i->second << "; ";
  }
  std::cout << std::endl;
} 

Получим в результате:

one -> 1; two -> 2; 

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

#include <iostream>
#include <map>

int main() {
#ifdef WIN32
  system("chcp 65001");
#else
  setlocale(LC_ALL, "Russian");
#endif
  std::map<int, int> m1, m2;
  std::map<int, int>::iterator i;
  m1[0] = 10;  // заполнение контейнера
  m1[1] = 20;  // заполнение контейнера
  m2 = m1;
  for (i = m2.begin(); i != m2.end(); i++) {
    std::cout << i->first << ' ' << i->second << "; ";
  }
  std::cout << std::endl;
}

Получим в результате:

0 10; 1 20; 

Обратите внимание, как в примере производится перебор всего содержимого отображения и вывод каждой пары "ключ/значение". Для этого используется итератор i:

std::map<int, int>::iterator i;

разыменование которого дает пару (объект pair) с ключом и значением. Доступ к компонентам пары осуществляется через переменные first и second:

std::cout << i->first << ' ' << i->second << "; ";

Как уже упоминалось, в ассоциативном контейнер можно хранить только уникальные ключи. Дублирования ключей не допускается.

Как правило, для любого объекта, заданного в качестве ключа, должны быть определены конструктор по умолчанию и несколько операторов сравнения.

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

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

erase() - удаляет один элемент или элементы из диапазона.

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

std::map<std::string, int> m;
std::map<std::string, int>::iterator i;
m["one"] = 1;
m["two"] = 2;
m.erase("one");
for (i = m.begin(); i != m.end(); ++i) {
  std::cout << i->first << " -> " << i->second << "; ";
}  // two -> 2;

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

std::map<std::string, int> m;
std::map<std::string, int>::iterator i;
m["one"] = 1;  // заполнение в контейнер
m["two"] = 2;
m.erase(--m.end());
for (i = m.begin(); i != m.end(); i++) {
  std::cout << i->first << " -> " << i->second << "; ";
}  // one -> 1;

clear() – удаление всех элементов.
empty() – возвращает значение true, если контейнер не содержит элементов, и false – в противном случае.

size() – возвращает количество элементов в контейнере. Пример:

std::map<std::string, int> m;
std::map<std::string, int>::iterator i;
m["one"] = 1;
m["two"] = 2;
m["third"] = 3;
m["four"] = 4;

std::cout << "size: " << m.size() << std::endl;  // 4
m.clear();
if (m.empty()) {
  std::cout << "Нет элементов\n";  // Нет элементов
}
std::cout << "size: " << m.size() << std::endl;  // 0

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

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

Пример:

std::map<std::string, int> m;
std::map<std::string, int>::iterator i;
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 (i = m.begin(); i != m.end(); ++i) {
std::cout << i->first << " -> " << i->second << "; ";
}  // key -> 0; one -> 100; two -> 2;

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

count(Keyval) – возвращает количество элементов, у которых ключ соответствует значению Keyval.
find(Keyval) – возвращает итератор, установленный на элемент, ключ которого соответствует значению Keyval. Если элемент не найден, то метод возвращает итератор, указывающий на позицию после последнего элемента.

Пример 1

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

A   0
B   1
C   2
. . .
J   9

Поскольку пары хранятся именно таким образом, то, когда пользователь набирает на клавиатуре ключ (т. е. одну из букв от А до J), программа выводит на экран соответствующее этому ключу значение.

#include <iostream>
#include <map>

int main() {
#ifdef WIN32
  system("chcp 65001");
#else
  setlocale(LC_ALL, "Russian");
#endif
  std::map<char, int> m;
  int i;
  // размещение пар в ассоциативном списке
  for (i = 0; i < 10; i++) {
    m['A' + i] = i;
  }
  char ch;
  std::cout << "Введите ключ: ";
  std::cin >> ch;
  std::map<char, int>::iterator p;
  // поиск значения по заданному ключу
  p = m.find(ch);
  if (p != m.end()) {
    std::cout << p->second;
  } else {
    std::cout << "Такого ключа в ассоциативном списке нет";
  }

  std::cout << std::endl;
}

Получим в результате:

Введите ключ: B
1

После того как ассоциативный контейнер инициализирован парами ключ/значение, найти нужное значение по заданному ключу можно с помощью функции find(). Функция find() возвращает итератор соответствующего ключу элемента или итератор конца ассоциативного контейнера, если указанный ключ не найден. Когда соответствующее ключу значение найдено, оно выводится в консоль.

Пример 2

Так же как и в других контейнерах, в ассоциативных контейнерах можно хранить создаваемые вами типы данных. Например, в представленной ниже программе создается отображение для хранения слов с соответствующими словам антонимами. С этой целью используются два класса: word (слово) и opposite (антоним). Поскольку для ассоциативных контейнеров поддерживается отсортированный список ключей, в программе для объектов типа word определяется оператор <. Как правило, оператор < необходимо перегружать для всех классов, объекты которых предполагается использовать в качестве ключей. (Помимо оператора < в некоторых компиляторах может потребоваться определить дополнительные операторы сравнения).

#include <iostream>
#include <map>

class word {
  char str[20];

 public:
  word() { strcpy(str, ""); }

  word(char* s) { strcpy(str, s); }

  word(const char* s) { strcpy(str, s); }

  char* get() { return str; }

  // Для объектов типа word следует определить оператор < (меньше)
  bool operator<(word b) { return strcmp(get(), b.get()) < 0; }
};

// Для объектов типа word следует определить оператор < (меньше)
bool operator<(word a, word b) { return strcmp(a.get(), b.get()) < 0; }

class opposite {
  char str[20];

 public:
  opposite() { strcpy(str, ""); }

  opposite(const char* s) { strcpy(str, s); }

  char* get() { return str; }
};

int main() {
#ifdef WIN32
  system("chcp 65001");
#else
  setlocale(LC_ALL, "Russian");
#endif
  std::map<word, opposite> m;
  // Размещение в ассоциативном контейнере имен абонентов
  // и их телефонных номеров
  m[word("Vasiliy")] = opposite("541-85-51");
  m[word("Joseph")] = opposite("550-09-96");
  m[word("Michael")] = opposite("8-3712-41-16-36");
  m[word("Nicodem")] = opposite("8-095-967-85-85");
  // Поиск телефонного номера по заданному имени абонента
  char str[80];
  std::cout << "Введите имя: ";
  std::cin >> str;
  std::map<word, opposite>::iterator p;
  p = m.find(word(str));
  if (p != m.end()) {
    std::cout << "Телефонный номер: " << p->second.get();
  } else {
    std::cout << "Такого имени в ассоциативном контейнере нет";
  }
  std::cout << std::endl;
}

Получим в результате:

Введите имя: Michael
Телефонный номер: 8-3712-41-16-36

В данном примере любой объект, который вводится в ассоциативный контейнер, представляет собой символьный массив для хранения заканчивающейся нулем строки.

Пример 3

Поскольку класс string определяет тип данных, появляется возможность создавать контейнеры для хранения объектов типа string. Например, ниже представлена усовершенствованная версия программы создания ассоциативного списка для хранения слов и антонимов.

#include <iostream>
#include <map>

int main() {
#ifdef WIN32
  system("chcp 65001");
#else
  setlocale(LC_ALL, "Russian");
#endif
  std::map<std::string, std::string> m;
  m["yes"] = "no";
  m["well"] = "no";
  m["left"] = "right";
  m["up"] = "down";
  std::string s;
  std::cout << "Введите слово: ";
  std::cin >> s;
  std::map<std::string, std::string>::iterator p;
  p = m.find(s);
  if (p != m.end()) {
    std::cout << "Антоним: " << p->second;
  } else {
    std::cout << "Такого слова в ассоциативном списке нет";
  }
  std::cout << std::endl;
}

Получим в результате:

Введите слово: yes
Антоним: no

5. Контейнер map

Основные сведения​

Создание экземпляра класса pair​

Создание экземпляра класса map​

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

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

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

Пример 1​

Пример 2​

Пример 3​

Основные сведения

Создание экземпляра класса pair

Создание экземпляра класса map

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

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

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

Пример 1

Пример 2

Пример 3