C++. Клас map. Асоціативний контейнер

Клас map. Асоціативний контейнер. Створення контейнера. Конструктори. Створення пари. Огляд функцій та операторів класу


Зміст


1. Загальні відомості про клас map. Оголошення класу

Клас map представляє собою асоціативний контейнер або хеш-таблицю. Асоціативний контейнер map є набором елементів, кожен з яких представлений у вигляді пар ключ:значення (key:value). Ключ є іменем з допомогою якого можна отримати необхідне значення. Іншими словами, доступ до значення здійснюється з допомогою ключа. Між ключем та значенням встановлюється зв’язок (асоціація).

Усі ключі в асоціативному контейнері map є унікальними (повторення ключів не допускається). Якщо потрібно забезпечити повторюваність ключів, то для цього використовується інший клас multimap.

Щоб використовувати можливості класу map потрібно підключити заголовок <map>

#include <map>

Згідно з документацією оголошення шаблонної форми класу map наступне

template <class Key, class T, class Comp = less<Key>,
class Allocator = allocator<pair<const key, T> class map

тут

  • Key – клас, що визначає тип ключа;
  • T – тип даних (значень), що отримуються за ключем типу Key;
  • Comp – функція, яка дозволяє порівнювати два ключі. За замовчування в функції Comp() використовується стандартний функтор less;
  • Allocator – клас, що виступає в якості розподілювача пам’яті. За замовчуванням виступає стандартний клас allocator.

 

2. Конструктори класу map. Створення асоціативного контейнера

Клас map має декілька конструкторів.

Конструктор який створює пустий масив має вигляд

explicit map(const Comp &compare_func = Comp(),
    const Allocator &alloc = Allocator());

Конструктор який створює асоціативний контейнер на основі об’єкту obj, який є теж типу map

map(const map<Key, T, Comp, Allocator> &obj);

Конструктор, який створює асоціативний масив, що міститься з елементів заданого діапазону

template <class InIterator> 
list(InIterator start, InIterator end, const Comp &compare_func = Comp(), const Allocator &a = Allocator());

У всіх трьох вищенаведених конструкторах використовуються наступні позначення:

  • start, end – ітератори, що задають початок та кінець діапазону;
  • compare_func – функція, що визначає порядок слідування елементів масиву.

Приклад.

У прикладі створюється асоціативний масив пар, в яких ключ (key) є типу int а значення (value) є типу string. Для створення масиву використовуються різні способи (конструктори).

#include <iostream>
#include <map>
using namespace std;

void main()
{
  // Конструктори класу map.
  // Конструктор 1. Створити пустий масив пар int:string
  map<int, string> m1;
  m1.insert(pair<int, string>(1, "One")); // додати пару 1:"One"
  m1.insert(pair<int, string>(2, "Two")); // додати пару 2:"Two"
  m1.insert(pair<int, string>(4, "Four")); // додати пару 4:"Four"
  m1.insert(pair<int, string>(5, "Five")); // додати пару 5:"Five"

  // Конструктор 2. Створити інший масив на основі існуючого
  map<int, string> m2(m1);
  cout << m2.at(2) << endl; // Two
  cout << m2.at(4) << endl; // Four

  // Конструктор 3. Створити масив на основі ітераторів
  // Взяти діапазон позицій [0; 1] включно (позиції нумеруються з 0)
  // 3.1. Оголосити ітератори
  map<int, string>::iterator it_start;
  map<int, string>::iterator it_end;

  // 3.2. Встановити ітератор it_start на перший елемент масиву m1
  it_start = m1.begin();

  // 3.3. Встановити ітератор it_end за елементом з індексом 1
  it_end = m1.begin();

  // 3.4. Перемотати ітератор на 2 позиції (за позицію з індексом 1)
  for (int i = 0; i < 2; i++)
    it_end++;

  // 3.5. Створити масив m3 на основі масиву m1
  map<int, string> m3(it_start, it_end);

  // 3.6. Вивести масив m3
  map<int, string>::iterator it = m3.begin();
  cout << "Array m3:" << endl;
  while (it != m3.end())
  {
    cout << it->first << " : " << it->second << endl;
    it++;
  }
  cout << "--------------------" << endl;
}

Результат

Two
Four
Array m3:
1 : One
2 : Two
--------------------

 

3. Функції класу map. Огляд

Клас map має наступні основні функції:

  • at() – повертає значення за відомим ключем;
  • begin() – повертає ітератор на перший елемент контейнера;
  • clear() – видаляє з масиву всі елементи;
  • count() – повертає кількість дублікатів елементів для заданого ключа;
  • empty() – визначає, чи асоціативний масив пустий (не містить жодного елементу);
  • end() – повертає ітератор, встановлений за останнім елементом контейнера;
  • erase() – видаляє елемент з асоціативного контейнера;
  • find() – повертає ітератор, що встановлений на заданий ключ;
  • insert() – додає до контейнера нову пару;
  • max_size() – повертає розмір, який фактично виділений для асоціативного контейнера з врахуванням його подальшого зростання;
  • size() – повертає поточну кількість елементів (розмір) в асоціативному контейнері;
  • swap() – обмінює місцями вміст двох контейнерів;
  • operator=() – присвоює один контейнер іншому;
  • operator[]() – повертає значення (value) за заданим ключем.

 

4. Оператори порівняння класу map. Огляд. Приклади

У класі map визначені оператори порівняння: ==, !=, <=, >=, <, >.

В операторах порівняння на рівність == та нерівність != порівнюються як ключі так і значення. Якщо при використанні оператора порівняння == знайдено хоча б одне неспівпадіння в парах ключ:значення або кількість елементів в контейнерах різна, то результат буде false. Оператор != є протилежним до оператора ==, тому в такому випадку результат цього оператора буде true.

В операторах <, >, <=, >= порівняння відбувається у такому порядку:

  1. Спочатку порівнюються ключі контейнерів в порядку з першого до останнього. Це означає, що ключ першого контейнера порівнюється з ключем другого контейнера. Перше неспівпадіння в ключах встановить відповідний результат.
  2. Якщо відповідні ключі контейнерів співпадають, то наступними порівнюються значення у порядку з першого до останнього. Значення послідовно переглядаються і порівнюються.
  3. Якщо і ключі і значення співпадають до якоїсь пари, то порівнюються довжини контейнерів.

Приклад 1. Порівняння на рівність та нерівність.

...

// Оператори порівняння
// 1. Порівняння ідентичних асоціативних контейнерів
map<int, string> m1;
m1.insert(make_pair(5, "Five"));

map<int, string> m2;
m2.insert(make_pair(5, "Five"));

bool res = m1 == m2; // res = true
res = m1 != m2; // res = false

// 2. Порівняння контейнерів, в яких відрізняється значення
map<int, string> m3, m4;
m3.insert(make_pair(4, "Four"));
m4.insert(make_pair(4, "4"));
res = m3 == m4; // res = false
res = m3 != m4; // res = true

// 3. Порівняння контейнерів в яких відрізняються ключі
map<int, string> m5, m6;
m5.insert(make_pair(6, "Six"));
m6.insert(make_pair(7, "Six"));
res = m3 == m4; // res = false
res = m3 != m4; // res = true
cout << res << endl;

...

Приклад 2. Порівняння на більше/менше.

...

// Оператори порівняння
// 1. Порівняння >, >= контейнери рівні
map<int, string> m1;
m1.insert(make_pair(5, "Five"));

map<int, string> m2;
m2.insert(make_pair(5, "Five"));

bool res = m1 > m2; // res = false
res = m1 >= m2; // res = true

// 2. Порівняння >, >=, <, <=
map<int, string> m3, m4;
m3.insert(make_pair(1, "One"));
m4.insert(make_pair(0, "Zero"));
res = m3 > m4; // res = true
res = m3 >= m4; // res = true
res = m3 < m4; // res = false
res = m3 <= m4; // res = false

// 3. Ключі рівні, відрізняються значення,
// спочатку порівнюються ключі, потім значення
map<int, string> m5, m6;
m5.insert(make_pair(1, "AAA"));
m6.insert(make_pair(1, "ABC"));
res = m5 > m6; // res = false
res = m5 >= m6; // res = false
res = m5 < m6; // res = true
res = m5 <= m6; // res = true

// 4. Довжини контейнерів різні,
// перші пари key:value співпадають
map<int, string> m7, m8;
m7.insert(make_pair(1, "One"));
m7.insert(make_pair(2, "Two"));
m8.insert(make_pair(1, "One"));
res = m7 > m8; // res = true - береться до уваги довжина контейнерів
res = m7 >= m8; // res = true
res = m7 < m8; // res = false
res = m7 <= m8; // res = false

// 5. Довжина першого контейнера більше за довжину другого,
// однак перший ключ першого контейнера менше за перший ключ другого.
map<int, string> m9, m10;
m9.insert(make_pair(1, "One"));
m9.insert(make_pair(2, "Two"));
m10.insert(make_pair(2, "Two"));
res = m9 > m10; // res = false
res = m9 >= m10; // res = false
res = m9 < m10; // res = true
res = m9 <= m10; // res = true

...

 

5. Структура pair<Key, Value>

Щоб створити пару ключ:значення (key:value) потрібно використати структуру pair, яка має наступне шаблонне оголошення

template <class Ktype, class Vtype>
struct pair
{
  typedef Ktype first_type;
  typedef Vtype second_type;
  Ktype first;
  Vtype second;
}

тут

  • Ktype – тип ключа;
  • Vtype – тип значення;
  • first – ключ;
  • second – значення.

Після створення, пара типу pair<Key, Value> може бути додана до асоціативного контейнеру з допомогою методу insert().

Екземпляр типу структури pair створюється різними способами з використанням відповідних конструкторів. Нижче наведено деякі основні способи створення пари ключ:значення.

 

5.1. Створення пари key:value. Використання полів структури first, second

У структурі pair<Key, Value> є поля, які дають безпосередній доступ до ключа та значення:

  • first – визначає ключ;
  • second – визначає значення.

У найбільш загальному випадку створення пари з заповненням полів first, second виглядає наступним чином

// Створення об'єкту пари
pair<K, V> p;

// Заповнення значень
p.first = key;
p.second = value;

тут

  • K, V – тип ключа та тип значення;
  • key – значення ключа типу K;
  • value – значення, що зв’язується з ключом K.

Приклад.

...

// Використання полів first, second структури pair<K, V>
// 1. Створити пару типів double, float та вивести її на екран
pair<double, float> p;
p.first = 2.5;
p.second = 100.55f;
cout << p.first << " : " << p.second << endl;

// 2. Створити пару типів char:string та вивести її на екран
pair<char, string> season;
season.first = 'W';
season.second = "Winter";
cout << p.first << " : " << p.second << endl;

...

 

5.2. Створення пари key:value з допомогою конструктора

Екземпляр структури pair<Key, Value> може бути створений з допомогою відповідного конструктора за наступною формою

pair<K, V> objP(key, value);

тут

  • K, V – тип ключа та тип значення;
  • key, value – конкретні значення ключа та значення.

Приклад.

...

// Створення пари з допомогою конструктора pair(K, V)
// 1. Створити пару типів char, int
pair<char, int> p1('H', 16);
cout << p1.first << " : " << p1.second << endl; // 'H' : 16

// 2. Створити пару типів bool, string
pair<bool, string> p2(true, "True");
cout << p2.first << " : " << p2.second << endl; // 1 : True

...

 

5.3. Створення пари key:value на основі іншої пари

Якщо потрібно отримати екземпляр структури pair<Key, Value> з іншої пари, тоді використовується наступна форма

pair<K, V> p2(p1);

тут

  • p1 – екземпляр-оригінал. Значення first, second цього екземпляру копіюються в екземпляр p2;
  • p2 – екземпляр-копія. Ключ (first) та значення (second) p2 заповнюються з екземпляру p1.

Приклад.

...

// Створення пари з іншої пари
// 1. Створити пару типів char, int
pair<char, int> p1('H', 16);

// 2. Отримати іншу пару
pair<char, int> p2(p1);

cout << p2.first << " : " << p2.second << endl; // H : 16

...

 

5.4. Створення пари з допомогою функції make_pair()

Пару типу pair<Key, Value> можна створити з допомогою функції make_pair(), яка згідно з документацією має наступний прототип

template <class Ktype, class Vtype>
pair<Ktype, Vtype> make_pair(const Ktype &k, const Vtype &v);

тут

  • Ktype – тип ключа;
  • Vtype – тип значення.

Зручність використання методу make_pair() полягає в тому, що типи об’єктів (ключа та пари) визначаються компілятором автоматично.

Приклад.

...

// Створення пари методом make_pair()
// 1. Створити пару типу int:string
pair<int, string> p1;
p1 = make_pair(2, "Two");

// 2. Створити пару типу char:int та додати її до асоціативного контейнера
pair<char, int> p2 = make_pair('B', 2);
map<char, int> m1;
m1.insert(p2);

// 3. Створити пару, в якій тип визначається автоматично та додати її до контейнера
m1.insert(make_pair('O', 8));

...

 


Споріднені теми