Карты в STL

Карты в С++В этой статье мы начнем обсуждение ассоциативных контейнеров в STL. Первый такой контейнер — «Map» (карта).

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

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

Реализация карты

В STL для реализации карты нам нужно включить заголовок <map> в нашу программу:

#include<map>

Общий синтаксис объявления карты следующий:

map<key type, value type> map_name;

В этой строке, тип ключа и тип значения — это типы данных ключей и значений соответственно.

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

map<int, int> mymap;

Теперь мы можем инициализировать карту во время самого объявления.

Это делается следующим образом:

map<int, int> mymap {{1, 10}, {2, 20}, {3, 30}};

Приведенная выше строка кода инициализирует карту тремя парами ключ-значение.

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

Операции

Вот некоторые основные операции с картой:

  • at и [ ]: операторы at и [ ] используются для доступа к элементам карты. Оба оператора at и [] имеют одинаковую функциональность с одним отличием. Если полученный ключ отсутствует в карте, оператор at создает исключение. Операторы [ ] вставляют новый ключ в карту, если полученный ключ отсутствует в карте.
  • begin: возвращает итератор к первому элементу карты.
  • end: возвращает итератор, указывающий на элемент после последнего элемента на карте.

Давайте рассмотрим приведенный ниже пример использования at и [ ]:

Вывод данных:

The map mymap is :

KEY    VALUE
1              10
2             20
3             30

The map mymap is :

KEY    VALUE
1             10
2            10
3            10

Читать также:  Static в С++

Итак, в приведенном выше коде у нас есть карта mymap с парой ключ-значение целочисленного типа. Мы инициализировали его тремя элементами. Мы отображаем эту карту, используя функции итератора begin и end.

Затем с помощью оператора «at» мы изменяем значение второго значения, а с помощью оператора [ ] изменяем значение третьего элемента таким образом, что теперь все три элемента имеют значение 10. Это становится очевидным, когда мы снова отображаем карту после изменение значений.

  • insert(key, value): вставляет новый элемент (пару ключей и значений) в карту.
  • erase: эта операция используется для удаления элемента с карты. Она имеет две версии:
    • erase(position) — здесь мы указываем позицию, на которую указывает итератор, и элемент в этой позиции удаляется.
    • erase(key) — здесь мы можем указать ключ определенного элемента в качестве аргумента для функции стирания, и элемент, имеющий это конкретное значение ключа, будет удален.
  • empty: проверяет, пуста ли карта.
  • size: возвращает размер карты, т.е. количество элементов в карте.
  • max_size: возвращает максимальный размер, который может содержать карта.
  • clear: удаляет все элементы из карты.

Вот пример кода, в котором показано использование этих функций:

Вывод данных:

The map mymap is :

KEY           VALUE
1                      1
2                     3
3                     5
4                     7
5                     9
6                    11
7                    13

mymap.size(): 7
mymap.max_size(): 461168601842738790
mymap.erase(3) : 1 removed

KEY      ELEMENT
1                    1
2                   3
4                   7
5                   9
6                  11
7                  13

After clear operation mymap.size() : 0

Читать также:  Функции классификации и преобразования символов С++

Данная программа показывает использование различных функций для работы с картой. Видно, что после операции стирания (erase) размер карты уменьшается на 1 и становится равным 0 при выполнении очистки.

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

Мультикарта (multimap)

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

Операции, которые мы обсуждали выше для карты, также применимы и для мультикарты.

Вот измененный выше пример, демонстрирующий Multimap:

Вывод данных:

The multimap mymap is :

KEY           VALUE
1                      1
2                     3
3                     5
3                     7
4                     9

mymap.size(): 5
mymap.max_size(): 461168601842738790
mymap.erase(3) : 2 removed

KEY          ELEMENT
1                        1
2                       3
4                       9

After clear operation mymap.size() : 0

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

Обратите внимание, что в мультикарте есть два элемента с одним и тем же ключом = 3. Но поскольку это мультикарта, то это разрешено, т.к. пара ключ-значение уникальна. Затем мы отобразили размер мультикарты.

Затем мы вызвали операцию стирания на мультикарте с ключом = 3. Теперь, когда есть две записи с одним и тем же ключом, обратите внимание, что операция стирания удалила два элемента из мультикарты.

Читать также:  Введение в объектно-ориентированное программирование на C++

Теперь мы рассмотрим другой вариант карты — неупорядоченную карту, т.е. unordered_map.

Неупорядоченная карта

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

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

Внутренне неупорядоченная карта реализована как структура данных «Hash Table» (хэш-таблица), ключ, предоставленный для карты, хэшируется в индексы в хеш-таблице. Следовательно, производительность структуры данных во многом зависит от предоставленной хеш-функции.

Общее объявление неупорядоченной карты:

unordered_map<keyType, valueType> umap_name;

Заголовок, который необходимо включить для реализации неупорядоченной карты, — <unordered_map>.

Давайте обсудим некоторые операции, которые поддерживает unordered_map для доступа к элементам и управления ими:

  • begin: возвращает ссылку на первый элемент в неупорядоченной карте.
  • end: указывает на элемент, за которым следует последний элемент в неупорядоченной карте.
  • at: возвращает ссылку на значение по ключу k.
  • bucket: возвращает количество элементов с ключом k, которое находится на карте.
  • bucket_count: возвращает общее количество сегментов в неупорядоченной карте.
  • bucket_size: возвращает количество элементов в каждом сегменте.
  • count: возвращает количество элементов, присутствующих в неупорядоченной карте для данного ключа.

Давайте посмотрим пример кода, чтобы проверить использование операций неупорядоченной карты:

Вывод данных:

All Elements in unordered map umap :
YELLOW 4
BLUE 3
GREEN 2
RED 1
umap bucket_count : 11
bucket_size : 0

В приведенном выше коде мы объявили неупорядоченную карту и вставили в нее значения с помощью оператора [ ] и операции вставки. Затем мы отобразили карту с помощью итераторов.

Мы также объявили операции «bucket_count», которые дают общее количество сегментов в этой конкретной неупорядоченной карте (это внутренний расчет), а также «bucket_size» для значения ключа = 2.

Итог

На этом мы подошли к концу данной статьи по картам в STL. В следующей статье мы рассмотрим детали контейнера «Set» в STL.

С Уважением, МониторБанк

Добавить комментарий