В обчислювальній техніці асоціативні контейнери відносяться до групи шаблонів класів у стандартній бібліотеці мови програмування 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() . setmapmultisetmultimapDescription(constructor)(constructor)(constructor)(constructor)Constructs the container from variety of sources(destructor)(destructor)(destructor)(destructor)Destructs the set and the contained elementsoperator=operator=operator=operator=Assigns values to the containerget_allocatorget_allocatorget_allocatorget_allocatorReturns the allocator used to allocate memory for the elementsДоступ до елементів at Accesses specified element with bounds checking. operator[] Accesses specified element without bounds checking.ІтераториbeginbeginbeginbeginReturns an iterator to the beginning of the containerendendendendReturns an iterator to the end of the containerrbeginrbeginrbeginrbeginReturns a reverse iterator to the reverse beginning of the containerrendrendrendrendReturns a reverse iterator to the reverse end of the containerРозмірemptyemptyemptyemptyChecks whether the container is emptysizesizesizesizeReturns number of elements in the container.max_sizemax_sizemax_sizemax_sizeReturns the maximum possible number of elements in the containerМодифікаториclearclearclearclearClears the contents.insertinsertinsertinsertInserts elements.emplaceemplaceemplaceemplaceConstructs elements in-place (C++11)emplace_hintemplace_hintemplace_hintemplace_hintConstructs elements in-place using a hint (C++11)eraseeraseeraseeraseErases elements.swapswapswapswapSwaps the contents with another container.ПошукcountcountcountcountReturns the number of elements matching specific key.findfindfindfindFinds an element with specific key.equal_rangeequal_rangeequal_rangeequal_rangeReturns a range of elements matching specific key.lower_boundlower_boundlower_boundlower_boundReturns an iterator to the first element with a key not less than the given value.upper_boundupper_boundupper_boundupper_boundReturns an iterator to the first element with a key greater than a certain value.Оглядачіkey_compkey_compkey_compkey_compReturns the key comparison function.value_compvalue_compvalue_compvalue_compReturns 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++
Список літератури