Map в C++: что это и как с этим работать

обложка статьи

В данном уроке мы разберем еще один часто используемый контейнер STL - map.

Что такое map

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

  1. Ключом может быть все что угодно. От обычной переменной до класса.

    mp1[0] = 7; // ключ - число
    
    mp2["zero"] = 4;  // ключ - строка
    
    pair <int, int> p = make_pair(1, 3);
    mp3[p] = 3;  // ключ - пара
  2. При добавлении нового элемента контейнер будет отсортирован по возрастанию.

map ключ c++

Мы можем создать ключ из любых компонентов и он будет - рабочим.

Поэтому можно с легкостью сделать словарь:

  • Ключом в нашем случае будет - русское слово.
  • А значением - английское.
map <string, string> mp;
mp["привет"] = "hi";

Добавление, удаление, обращение к элементам происходит за log n. n - в нашем случае размер контейнера.

Как создать map

Сперва понадобится подключить соответствующую библиотеку:

#include <map>

Чтобы создать map нужно воспользоваться данной конструкцией:

map < <L>, <R> > <имя>;
  • <L> - этот тип данных будет относиться к значению ключа.
  • <R> - этот тип данных соответственно относится к значению.
map <string, int> mp; // пример

В нашем случае:

При создании map все его элементы будут иметь значение нуля.

Также имеется возможность добавить значения при инициализации (C++ 11 и выше):

map <string, string> book = {{"Hi", "Привет"},
                             {"Student", "Студент"},
                             {"!", "!"}};

cout << book["Hi"];

Итераторы для map

Использование итераторов одна из главных тем, если вам понадобится оперировать с этим контейнером. Создание итератора, как обычно происходит так:

map <тип данных> :: iterator <имя>;
  • <тип данных> - <string, int> например.

С помощью его можно использовать две операции (it - итератор):

  1. Чтобы обратится к ключу нужно сделать так: it->first.
  2. Чтобы обратится к значению ячейки нужно сделать так: it->second.

Нельзя обращением к ключу (...->first) изменять его значение, а вот изменять таким образом значение ячейки (...->second) легко.

Нельзя использовать никакие арифметические операции над итератором:

it *= 5;

it += 3;

it /= 10;

Все это будет считаться еще одной ошибкой для компилятора.

Для увеличения или уменьшения можно использовать инкремент или декремент.

it++;
it--;

Нельзя делать то же самое используя операцию присваивания (it += 1) или вычитания (it -= 1).

Чтобы не писать циклы для увеличения итератора на большие значения, можно воспользоваться функцией advance():

advance(it, 7);
advance(it, -5);

Она сдвигает указанный итератор вниз или вверх на указанное количество ячеек. В нашем случае он сначала увеличит на 7, а потом уменьшит на 5, в итоге получится сдвиг на две вверх.

Вывод контейнера

Давайте попробуем вывести все элементы, которые находятся в контейнере.

#include <iostream>
#include <map>

using namespace std;
int main() {
    setlocale(0, "");
    map <int, int> mp;
    
    cout << "Введите количество элементов: "; int n; cin >> n;

    for (int i = 0; i < n; i++) {
        cout << i << ") "; int a; cin >> a;
        mp[a] = i;  // добавляем новые элементы
    }

    map <int, int> :: iterator it = mp.begin();
    cout << "А вот все отсортированно: " << endl;
    for (int i = 0; it != mp.end(); it++, i++) {  // выводим их
        cout << i << ") Ключ " << it->first << ", значение " << it->second << endl;
    }
    
    system("pause");
    return 0;
}

А вот рабочая программа:

Введите количество элементов: 5
0) 33
1) 5
2) 2
3) 9
4) 27
А вот все отсортированно:
0) Ключ 2, значение 2
1) Ключ 5, значение 1
2) Ключ 9, значение 3
3) Ключ 27, значение 4
4) Ключ 33, значение 0
Process returned 0 (0x0) execution time : 0.010 s
Press any key to continue.

Методы map

Ниже мы разберем функции которые можно использовать для работы с map.

Некоторые функции не могут работать с map из-за его специфической архитектуры.

insert

Это функция вставки нового элемента.

mp.insert(make_pair(num_1, num_2));
  • num_1 - ключ.
  • num_2 - значение.

Мы можем сделать то же самое вот так:

mp[num_1] = num_2;

count

Возвращает количество элементов с данным ключом. В нашем случае будет возвращать - 1 или 0.

Эта функция больше подходит для multimap, у которого таких значений может быть много.

...

mp[0] = 0;
    
mp.count(0); // 1
mp.count(3); // 0

...

Нужно помнить, что для строк нужно добавлять кавычки - count("Good").

find

У этой функции основная цель узнать, есть ли определенный ключ в контейнере.

  • Если он есть, то передать итератор на его местоположение.
  • Если его нет, то передать итератор на конец контейнера.

Например, давайте разберем данный код:

#include <iostream>
#include <map>  // подключили библиотеку

using namespace std;

int main() {
  setlocale(0, "");
  map <string, string> book;  
  book["book"] = "книга";     

  map <string, string> :: iterator it, it_2;

  it = book.find("book");
  cout << it->second << endl;

  it_2 = book.find("books");

  if (it_2 == book.end()) {
      cout << "Ключа со значением 'books' нет";
  }

  system("pause");
  return 0;
}

Давайте рассмотрим поподробнее:

  • В строке 8: мы создали map под названием - book.
  • В строке 9: задали единственный ключ "book" со значением "книга".
  • В строке 11: создали два итератора it и it_2.
  • В строке 13 - 14: получаем итератор на ключ “book” и выводим его значение.
  • В строке 16: получаем итератор на ключ “books”, которого нет в нашем контейнере.
  • В строке 18 - 20: проверяем не указывает ли it_2 на конец контейнера и предупреждаем пользователя.

erase

Иногда приходится удалять элементы. Для этого у нас есть функция - erase().

Давайте посмотрим как она работает на примере:

map <string, string> passport;

passport["maxim"] = "Denisov";     // добавляем
passport["andrey"] = "Puzerevsky"; // новые
passport["dima"] = "Tilyupo";      // значения

cout << "Size: " << passport.size() << endl;

map <string, string> :: iterator full_name; // создали итератор на passport

full_name = passport.find("andrey"); // находим ячейку
passport.erase(full_name);           // удаляем

cout << "Size: " << passport.size();

passport в нашем случае хранит имя как ключ, а фамилию как значение.

В итоге мы уменьшим количество наших элементов на один.

Также здесь мы воспользовались функцией size(), которая возвращает количество элементов.

А вот вывод:

Size: 3
Size: 2

Process returned 0 (0x0) execution time : 0.010 s
Press any key to continue.

Создаем простую игру

Давайте закрепим наши знания на практике - создав примитивную игру.

Пользователю понадобится ввести количество домов на улице и указать для каждого дома сколько людей там проживает.

Далее он может модифицировать данные об улице таким образом:

  • Введя 0 - он сможет узнать имеется ли такой дом и если да, то сколько там живет людей.
  • Введя 1 - сможет удалить ключ из контейнера навсегда.
  • Введя 2 - он сможет добавить новый дом.

Вот код:

#include <iostream>
#include <map>

using namespace std;

int main() {
  map <int, int>  street; // создали журнал
  int n;

  cout << "Введите количество домов на улице: "; cin >> n;      // считываем количество 
  cout << "Укажите дом и сколько в нем живет людей: " << endl;  // домов 

  for (int i = 0; i < n; i++) {
    int house, people;
    cout << i << ") Дом "; 
    cin >> house;cin >> people;  // считываем введенные значения
    street.insert(make_pair(house, people));  
  }

  int q;
  cout << endl << "Введите количество операций: "; 
  cin >> q;  

  for (int i = 0; i < q; i++) {
    cout << i << ") "; 
    int a; cin >> a;

    if (a == 0) { // начала первой операция
      int house; 
      cout << "Укажите номер дома: "; cin >> house;
      if (street.count(house)) {
        cout << "Количество людей: " <<
        street[house] << endl;
      }
      else {
        cout << "Такого дома не существует! " << endl;
      }
    }
    if (a == 1) { // начала второй операции
      int deleter;
      cout << "Какой дом удалить: ";  cin >> deleter;
      if (street.find(deleter) == street.end()) {
        cout << "Его нет в списке, возможно уже разрушен :)";
      }
      else {
        street.erase(street.find(deleter));
        cout << "Элемент удален! " << endl;
      }
    }

    if (a == 2) { // начала третьей операции
      int house, people;
      cout << "Какой дом добавить: "; cin >> house;
      cout << "Какое количество людей там проживает: "; cin >> people;
      street[house] = people;
    }
  }

  return 0;
}

Теперь давайте подробно разберем, что тут такое:

  1. В строках 13 - 18: считываем все дома и их жителей.
    • В строке 17: вместо обычного объявления ячейки мы использовали функцию insert.
  2. В строках 24 - 57: здесь находится основной блок и на него стоит обратить внимание.
  3. В строке 26: считываем операцию, которую хочет выполнить пользователь.
  4. В строках 29 - 38: находится код для выполнения операции 0 (вывод элемента).
    • В строке 31: оперируем функцией count, чтобы узнать имеется ли у нас данный элемент.
  5. В строках 39 - 49: находится блок кода для использования операции 1 (удаление).
    • В строке 42: проверяем есть ли этот вообще (даже если его нет, удаление не существующего элемента не приведет к ошибке).
    • Если он есть - удаляем.
  6. В строках 51 - 57: здесь выполнятся код для операции 2 (добавление).

А вот рабочая программа:

Введите количество домов на улице: 5
Укажите дом и сколько в нем живет людей:
0) Дом 1 64
1) Дом 2 81
2) Дом 3 100
3) Дом 4 25
4) Дом 5 121

Введите количество операций: 5
0) 0
Укажите номер дома: 1
Количество людей: 64
1) 1
Какой дом удалить: 1
Элемент удален!
2) 0
Укажите номер дома: 1
Такого дома не существует!
3) 2
Какой дом добавить: 7
Какое количество людей там проживает: 169
4) 1
Какой дом удалить: 9
Его нет в списке, возможно уже разрушен :)

Process returned 0 (0x0) execution time : 0.010 s
Press any key to continue.

Плюсы и минусы: использования map

Плюсы:

  • Ключом может быть любая переменная. Это огромный плюс, например если придется делать словарь.

Минусы:

  • Долгое добавление нового элемента.
  • Долгое обращение к элементу.
  • Долгое удаление нового элемента.
  • Также слишком затратный по памяти

Все эти операции происходят за - log n (n - это размер контейнера).

Подытожим:

  1. Если вам требуется быстрый отклик программы, то если возможно оперировать вектором либо массивом лучше использовать именно их.
  2. Если же время не стоит на первом месте, то можно им пренебречь и использовать map.

Упражнение

Создайте программу в которой пользователь сможет использовать данные операции:

  • Добавлять новое слова - [английское - русское].
  • Удалять их.
  • Изменять значение уже существующего слова (...->second).

Если есть вопросы пишите их в комментариях. Удачи в новых начинаниях!

Обсуждение