Ми переконалися, що послідовні контейнери (вектори, списки і черги з двостороннім доступом) зберігають дані у фіксованій лінійній послідовності. Пошук конкретного елемента в такому контейнері (якщо невідомий або недоступний його індекс або він не знаходится в одному з кінців контейнера) – це тривала процедура, що включає в себе покроковий перехід від позиції до позиції.
В асоціативних контейнерах елементи не організуються в послідовності. Вони являють собою складніші структури, що дає значний виграш у швидкості пошуку. Звичайно асоціативні контейнери – це «дерева», хоча можливі й інші варіанти, наприклад, таблиці. В будь-якому випадку, головною перевагою цієї категорії контейнерів є швидкість пошуку.
Пошук здійснюється за допомогою ключів, що звичайно являють собою одне числове або рядкове значення, яке може бути атрибутом об’єкту в контейнері або самим об’єктом.
Дві основні категорії асоціативних контейнерів STL – це множини та відображення.
Множина зберігає об’єкти, які містять ключі. Відображення можна уявляти собі як свого роду таблицю з двох стовпчиків, в першому з яких зберігаються об’єкти, що містять ключі, а в другому – об’єкти, що містять значення.
В множинах, як і у відображеннях, може зберігатися тільки один екземпляр кожного ключа. А кожному ключу, в свою чергу, відповідає унікальне значення. Такий підхід використовується в словниках, коли кожному слову відповідає лише одна стаття. Але в STL є спосіб обійти це обмеження. Мультимножини та мультивідображення аналогічні до споріднених контейнерів, але в них одному ключу може відповідати кілька значень.
Асоціативні контейнери мають кілька спільних методів з іншими контейнерами. Але даякі алгоритми, такі як lower_bound() та equal_range(), характерні лише для них. Крім того, деякі методи не можуть застосовуватися до асоціативних контейнерів. Серед них – сімейство методів проштовхування і виштовхування (push_back() та ін.). Дійсно, немає особливого сенсу в їх застосуванні до даної категорії контейнерів, оскільки все одно елементи повинні проштовхуватися і виштовхуватися в певному порядку, але не в кінець чи початок контейнера.
