Асоціативні контейнери

В обчислювальній техніці асоціативні контейнери відносяться до групи шаблонів класів у стандартній бібліотеці мови програмування C++, які реалізують упорядковані асоціативні масиви . Будучи шаблонами, вони можуть використовуватися для зберігання довільних елементів, таких як цілі числа, символьні рядки чи класи користувача. У поточній редакції стандарту C++ визначені такі контейнери: set, map, multiset, multimap . Кожен із цих контейнерів відрізняється лише обмеженнями, накладеними на їхні елементи.

Асоціативні контейнери подібні до невпорядкованих асоціативних контейнерів у стандартній бібліотеці C++, єдина відмінність полягає в тому, що невпорядковані асоціативні контейнери, як випливає з їх назви, не впорядковують свої елементи.

Структура

Характеристики

• Унікальність ключів : у map та set кожен ключ має бути унікальним. multimap і multiset не мають цього обмеження.
• Склад елементів : у map та multimap кожен елемент складається з ключа(key) та зіставленого значення(value). У set та multiset кожен елемент є ключовим; немає зіставлених значень.
• Порядок елементів : елементи дотримуються строгого порядку розміщення.

Асоціативні контейнери створені для особливо ефективного доступу до елементів за їх ключем, на відміну від послідовних контейнерів, які більш ефективні для доступу до елементів за їхньою позицією(індексом). Асоціативні контейнери гарантовано виконують операції вставки, видалення та перевірки наявності в ньому елемента за логарифмічний час – O(log n ). Таким чином, вони зазвичай реалізуються за допомогою самобалансуючих бінарних дерев пошуку(self-balancing binary search tree) та підтримують двонаправлену ітерацію. Ітератори та посилання не анулюються операціями вставки та стирання, за винятком ітераторів та посилань на видалені елементи. Визначальною характеристикою асоціативних контейнерів є те, що елементи вставляються у заздалегідь визначеному порядку, наприклад, сортуються за зростанням.

Асоціативні контейнери можна згрупувати в дві підмножини: таблиці(maps) та множини(sets). Таблиця, яку іноді називають словником, складається з пари ключ/значення. Ключ використовується для впорядкування послідовності, а значення якимось чином асоціюється з цим ключем. Наприклад, таблиця може містити ключі, що репрезентують кожне унікальне слово в тексті, і значення, що відображають кількість разів, коли це слово з'явилось у тексті. Множина — це просто контейнер унікальних елементів відсортований у висхідному порядку.

Як було зазначено раніше, map і set дозволяють вставити в контейнер лише один екземпляр ключа або елемента. Якщо потрібні кілька екземплярів елементів, використовуйте multimap або multiset .

І таблиці, і набори підтримують двонаправлені ітератори. Щоб отримати додаткові відомості про ітератори, перегляньте Ітератори .

Хоча hash_map і hash_set офіційно не є частиною стандарту STL, вони зазвичай використовуються для покращення часу пошуку. Ці контейнери зберігають свої елементи як хеш-таблицю, де кожен запис таблиці містить двонаправлений зв'язний список елементів. Щоб забезпечити найшвидший час пошуку ( O(1) ), переконайтеся, що алгоритм хешування для ваших елементів повертає рівномірно розподілені хеш-значення.

Швидкість роботи

Асимптотична складність операцій, які можна застосувати до асоціативних контейнерів, така:

Операція	Асимптотична Складність
Пошук елемента	O(log n)
Вставка нового елемента	O(log n)
Збільшення/зменшення ітератора	O(log n) (амортизується до O(1), якщо виконуються лише операції інкременту та декременту)
Видалення окремого елемента	O(log n)

Огляд стандартного функціоналу

Контейнери визначаються в файлах заголовків, названих за іменами контейнерів, наприклад, set визначається у файлі <set> . Усі контейнери відповідають вимогам концепції контейнера, що означає, що вони мають методи begin(), end(), size(), max_size(), empty() і swap() .

	set	map	multiset	multimap	Description
	(constructor)	(constructor)	(constructor)	(constructor)	Constructs the container from variety of sources
	(destructor)	(destructor)	(destructor)	(destructor)	Destructs the set and the contained elements
	operator=	operator=	operator=	operator=	Assigns values to the container
	get_allocator	get_allocator	get_allocator	get_allocator	Returns the allocator used to allocate memory for the elements
Доступ до елементів	Н/Д	at	Н/Д	Н/Д	Accesses specified element with bounds checking.
	Н/Д	operator[]	Н/Д	Н/Д	Accesses specified element without bounds checking.
Ітератори	begin	begin	begin	begin	Returns an iterator to the beginning of the container
	end	end	end	end	Returns an iterator to the end of the container
	rbegin	rbegin	rbegin	rbegin	Returns a reverse iterator to the reverse beginning of the container
	rend	rend	rend	rend	Returns a reverse iterator to the reverse end of the container
Розмір	empty	empty	empty	empty	Checks whether the container is empty
	size	size	size	size	Returns number of elements in the container.
	max_size	max_size	max_size	max_size	Returns the maximum possible number of elements in the container
Модифікатори	clear	clear	clear	clear	Clears the contents.
	insert	insert	insert	insert	Inserts elements.
	emplace	emplace	emplace	emplace	Constructs elements in-place (C++11)
	emplace_hint	emplace_hint	emplace_hint	emplace_hint	Constructs elements in-place using a hint (C++11)
	erase	erase	erase	erase	Erases elements.
	swap	swap	swap	swap	Swaps the contents with another container.
Пошук	count	count	count	count	Returns the number of elements matching specific key.
	find	find	find	find	Finds an element with specific key.
	equal_range	equal_range	equal_range	equal_range	Returns a range of elements matching specific key.
	lower_bound	lower_bound	lower_bound	lower_bound	Returns an iterator to the first element with a key not less than the given value.
	upper_bound	upper_bound	upper_bound	upper_bound	Returns an iterator to the first element with a key greater than a certain value.
Оглядачі	key_comp	key_comp	key_comp	key_comp	Returns the key comparison function.
	value_comp	value_comp	value_comp	value_comp	Returns the value comparison function. In set and multiset this function is equivalent to key_comp, since the elements are composed from a key only.

Використання

Наступний приклад коду демонструє, як використовувати map<string, int> для підрахунку повторень слів у введеному рядку. Він використовує слово як ключ і кількість як значення .

#include <iostream>
#include <map>

int main()
{
    std::map<std::string, int> wordcounts;
    std::string s;

    while (std::cin >> s && s != "end")
    {
        ++wordcounts[s];
    }
    
    while (std::cin >> s && s != "end")
    {
        std::cout << s << ' ' << wordcounts[s] << '\n';
    }
    
    return 0;
}

Під час виконання програма дозволяє користувачеві вводити ряд слів, розділених пропусками, і слово "end", щоб позначити кінець введення. Після цього користувач може ввести слово, щоб отримати інформацію, скільки разів воно зустрічалося в попередньо введеному рядку.

Наведений вище приклад також демонструє, що оператор [] вставляє нові об’єкти (використовуючи конструктор за замовчуванням) у таблицю, якщо немає такого, пов’язаного з ключем. Отже, цілі чила типи ініціалізуються нулем, рядки ініціалізуються порожніми рядками тощо.

Наступний приклад ілюструє вставлення елементів у карту, за допомогою функції вставки та пошук ключа за допомогою ітератора карти та функції find():

#include <iostream>
#include <map>
#include <utility> // To use make_pair function

int main()
{
    typedef std::map<char, int> MapType;
    MapType my_map;

    // Insert elements using insert function
    my_map.insert(std::pair<char, int>('a', 1));
    my_map.insert(std::pair<char, int>('b', 2));
    my_map.insert(std::pair<char, int>('c', 3));
    
    // You can also insert elements in a different way like shown below
    // Using function value_type that is provided by all standart containers
    my_map.insert(MapType::value_type('d', 4));
    // Using the utility function make_pair
    my_map.insert(std::make_pair('e', 5));
    // Using C++11 initializer list
    my_map.insert({'f', 6});                    
    
    //map keys are sorted automatically from lower to higher. 
    //So, my_map.begin() points to the lowest key value not the key which was inserted first.
    MapType::iterator iter = my_map.begin();

    // Erase the first element using the erase function
    my_map.erase(iter);

    // Output the size of the map using size function
    std::cout << "Size of my_map: " << my_map.size() << '\n';

    std::cout << "Enter a key to search for: ";
    char c;
    std::cin >> c;

    // find will return an iterator to the matching element if it is found
    // or to the end of the map if the key is not found
    iter = my_map.find(c);
    if (iter != my_map.end()) 
    {
        std::cout << "Value is: " << iter->second << '\n';
    }
    else 
    {
        std::cout << "Key is not in my_map" << '\n';
    }

    // You can clear the entries in the map using clear function
    my_map.clear();
    
    return 0;
}

Наведений вище приклад демонструє використання деяких функцій, які надає map, наприклад insert() (розмістити елемент в таблиці), erase() (видалити елемент з таблиці), find() (перевірити наявність елемента в таблиці) тощо.

Коли програма виконується, шість елементів вставляються за допомогою функції insert(), потім перший елемент видаляється за допомогою функції erase() і виводиться розмір таблиці. Далі користувачеві пропонується ввести ключ для його пошуку у таблиці. Використовуючи створений раніше ітератор, функція find() шукає елемент із заданим ключем. Якщо ключ знайдено, програма друкує значення елемента. Якщо ні, повертає ітератор до кінця таблиці та виводить, що ключ не знайдено. Нарешті всі елементи в дереві видаляться за допомогою clear() .

Ітератори

Таблиці можуть використовувати ітератори, щоб вказувати на певні елементи в контейнері. Ітератор може отримати доступ як до ключа, так і до відображеного значення елемента:

// Declares a map iterator
std::map<Key, Value>::iterator it;

// Accesses the Key value 
it->first;

// Accesses the mapped value
it->second;

// The "value" of the iterator, which is of type std::pair<const Key, Value>
(*it);

Нижче наведено приклад проходження таблиці з використанням циклу, для відображення всіх ключів і значень за допомогою ітераторів:

#include <iostream>
#include <map>

int main()
{
    std::map<std::string, int> data 
    {
     { "Bobs score", 10    },
     { "Martys score", 15  },
     { "Mehmets score", 34 },
     { "Rockys score", 22  },
     // The next values are ignored because elements with the same keys are already in the map
     { "Rockys score", 23  }, 
     { "Mehmets score", 33 } 
    };
    
    // Iterate over the map and print out all key/value pairs.
    for (const auto& element : data)
    {
        std::cout << "Who(key = first): " << element.first;
        std::cout << " Score(value = second): " << element.second << '\n';
    }
    
    // If needed you can iterate over the map with the use of iterator,
    // Note that the long typename of the iterator in this case can be replaced with auto keyword
    for (std::map<std::string, int>::iterator iter = data.begin(); iter != data.end(); ++iter) 
    {
        std::cout << "Who(key = first): " << iter->first;
        std::cout << " Score(value = second): " << iter->second << '\n';
    }

    return 0;
}

Перегляньте додатково

• Контейнер (абстрактний тип даних)
• Стандартна бібліотека шаблонів#Контейнери
• Невпорядковані асоціативні контейнери C++