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

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

Интересное

Последние новости в мире программирования

Самые свежие новости и полезные материалы в моем telegram канале.

Что такое map

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

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

mp1[0] = 7; // ключ - число

mp2["zero"] = 4;  // ключ - строка

pair <int, int> p = make_pair(1, 3);
mp3[p] = 3;  // ключ - пара

При добавлении нового элемента контейнер будет отсортирован по возрастанию.

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

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

Ключом в нашем случае будет - русское слово.
А значением - английское.

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 - итератор):

Чтобы обратится к ключу нужно сделать так: it->first.
Чтобы обратится к значению ячейки нужно сделать так: 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, в итоге получится сдвиг на две вверх.

Интересное

Последние новости в мире программирования

Самые свежие новости и полезные материалы в моем telegram канале.

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

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

#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.

insert
count
find
erase

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

insert

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

mp.insert(make_pair(num_1, num_2));

num_1 - ключ.
num_2 - значение.

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

mp[num_1] = num_2;

Интересное

Последние новости в мире программирования

Самые свежие новости и полезные материалы в моем telegram канале.

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.

Интересное

Последние новости в мире программирования

Самые свежие новости и полезные материалы в моем telegram канале.

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

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

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

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

Введя 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;
}

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

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

Подытожим:

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

Упражнение

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

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

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

Если хотите всегда быть в курсе последних новостей в мире программирования и IT, подписываетесь на мой Telegram-канал, где я делюсь свежими статьями, новостями и полезными советами. Буду рад видеть вас среди подписчиков!

Что такое map

Как создать map

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

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

Методы map

insert

count

find

erase

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

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

Упражнение

Читайте также

Обсуждение