Асоціативний контейнер – це дещо інша організація даних. Дані розміщуються не послідовно, доступ до них здійснюється через посередництво ключів. Ключі – це просто номери рядків, вони звичайно використовуються для вишиковування збережених елементів у певному порядку і модифікуються контейнерами автоматично. прикладом може виступати звичайний орфографічний словник, де слова розміщені за алфавітом. Ми просто вводимо потрібне слово, тобто значення ключа, а контейнер конвертує його в адресу цього елемента в пам’яті. Якщо відомий ключ, доступ до даних здійснюється дуже просто.
В STL є два типи контейнерів: множини і відображення. Ті й інші зберігають дані у вигляді дерева, що дозволяє здійснювати швидку вставку, видалення і пошук даних. Множини і відображення є дуже зручними і при цьому достатньо універсальними інструментами, які можна використовувати в дуже багатьох ситуаціях. Але здійснювати сортування і виконувати інші операції, що вимагають випадкового доступу. складно.
Множини простіші і тому популярніші, ніж відображення. Множина зберігає набір елементів, що містить ключі – атрибути, що використовуються для впорядковування даних. Наприклад, множина може зберігати об’єкти класу person, впорядковані в алфавітному порядку за значенням поля nsme, яке виступає в ролі ключа. При такій організації даних можна дуже швидко знайти потрібний об’єкт, здійснюючи пошук за іменем об’єкта (в нашому випадку за атрибутом name). Якщо в множині зберігаються значення одного з базових типів, таких як int, то ключем є сам елемент. На майбутнє ми будемо використовувати термін ключовий об’єкт, щоб підкреслити, що атрибут, використовуваний для впорядковування 9ключ) – це не обов’язково весь елемент даних.
Відображення зберігає пари об’єктів. Один кортеж в такій «базі даних» складається з двох «атрибутів»: ключовий об’кт і цільовий (асоційований) об’єкт. Цей інструмент часто використовується в якості контейнера, який дещо нагадує масив. Різниця лише в тому, що доступ до даних здійснюється не по номеру елементу, а по спеціальному індексу, який сам по собі може бути довільного типу. Тобто, ключовий об’єкт служить індексом, а цільовий – значенням цього індекса.
Контейнери відображення і множина дозволяють співставляти тільки один ключ даному значенню. Це має сенс в таких, наприклад, випадках, як зберігання списку працівників, де кожному імені співставляється унікальний ідентифікаційний номер. З іншого боку, мультивідображення і мультимножини дозволяють зберігати кілька ключів для одного значення. Наприклад, слову «ключ» в енциклопедії може відповідати кілька статей.
В таблиці 10.2 зібрані всі асоціативні контейнери, що зберігаються в STL.
Таблиця 15.2
Основні асоціативні контейнери
Контейнер
| Характеристики
|
Множина
| Зберігає тільки ключові об’єкти. Кожному значенню відповідає один ключ
|
Мультимножина
| Зберігає тільки ключові об’єкти. Одному значенню може відповідати кілька ключів
|
Відображення
| Асоціює ключовий об’єкт з об’єктом, що зберігає значення (цільовим). Одному значенню відповідає один ключ
|
Мультивідображення
| Асоціює ключовий об’єкт з об’єктом, що зберігає значення (цільовим). Одному значенню може відповідати кілька ключів.
|
Створюються асоціативні контейнери приблизно так само, як і послідовні.
set <int> intSet; // створює множину значень int
або
multiset <employee> machinists; // створює мультимножину значень типу employee
Методи
Алгоритми – це робочі інструменти STL, що виконують складні операції типу сортування і пошуку. Однак для виконання простіших операцій, специфічних для конкретного контейнера, потрібні методи.
В таблиці 10.3 представлені деякі найпопулярніші методи, імена та призначення яких спільні для більшості класів контейнерів.
Таблиця 15.3
Деякі методи, спільні для всіх контейнерів
Ім’я
| Призначення
|
size()
| Повертає число елементів у контейнері
|
empty()
| Повертає true, якщо контейнер порожній
|
max_size
| Повертає максимально допустимий розмір контейнера
|
begin()
| Повертає ітератор на початок контейнера (ітерації будуть відбуватися в прямому напрямку)
|
end()
| Повертає ітератор на останню позицію в контейнері (ітерації в прямому напрямку закінчені)
|
rbegin()
| Повертає ітератор на кінець контейнера (ітерації будуть відбуватися в зворотньому напрямку)
|
rend()
| Повертає ітератор на початок контейнера (ітерації у зворотньому напрямку закінчені)
|