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. Порівняння на рівність та нерівність.

...

// Оператори порівняння
// 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));

...

BestProg

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

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

Зміст

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

⇑

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

⇑

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

⇑

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

⇑

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

⇑

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

⇑

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

⇑

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

⇑

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

⇑

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

⇑

Програмування: теорія та практика