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

Асоціативний контейнер – це дещо інша організація даних. Дані розміщуються не послідовно, доступ до них здійснюється через посередництво ключів. Ключі – це просто номери рядків, вони звичайно використовуються для вишиковування збережених елементів у певному порядку і модифікуються контейнерами автоматично. прикладом може виступати звичайний орфографічний словник, де слова розміщені за алфавітом. Ми просто вводимо потрібне слово, тобто значення ключа, а контейнер конвертує його в адресу цього елемента в пам’яті. Якщо відомий ключ, доступ до даних здійснюється дуже просто.

В STL є два типи контейнерів: множини і відображення. Ті й інші зберігають дані у вигляді дерева, що дозволяє здійснювати швидку вставку, видалення і пошук даних. Множини і відображення є дуже зручними і при цьому достатньо універсальними інструментами, які можна використовувати в дуже багатьох ситуаціях. Але здійснювати сортування і виконувати інші операції, що вимагають випадкового доступу. складно.

Множини простіші і тому популярніші, ніж відображення. Множина зберігає набір елементів, що містить ключі – атрибути, що використовуються для впорядковування даних. Наприклад, множина може зберігати об’єкти класу person, впорядковані в алфавітному порядку за значенням поля nsme, яке виступає в ролі ключа. При такій організації даних можна дуже швидко знайти потрібний об’єкт, здійснюючи пошук за іменем об’єкта (в нашому випадку за атрибутом name). Якщо в множині зберігаються значення одного з базових типів, таких як int, то ключем є сам елемент. На майбутнє ми будемо використовувати термін ключовий об’єкт, щоб підкреслити, що атрибут, використовуваний для впорядковування 9ключ) – це не обов’язково весь елемент даних.

Відображення зберігає пари об’єктів. Один кортеж в такій «базі даних» складається з двох «атрибутів»: ключовий об’кт і цільовий (асоційований) об’єкт. Цей інструмент часто використовується в якості контейнера, який дещо нагадує масив. Різниця лише в тому, що доступ до даних здійснюється не по номеру елементу, а по спеціальному індексу, який сам по собі може бути довільного типу. Тобто, ключовий об’єкт служить індексом, а цільовий – значенням цього індекса.

Контейнери відображення і множина дозволяють співставляти тільки один ключ даному значенню. Це має сенс в таких, наприклад, випадках, як зберігання списку працівників, де кожному імені співставляється унікальний ідентифікаційний номер. З іншого боку, мультивідображення і мультимножини дозволяють зберігати кілька ключів для одного значення. Наприклад, слову «ключ» в енциклопедії може відповідати кілька статей.

В таблиці 10.2 зібрані всі асоціативні контейнери, що зберігаються в STL.

Таблиця 15.2

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

Створюються асоціативні контейнери приблизно так само, як і послідовні.

set <int> intSet; // створює множину значень int

або

multiset <employee> machinists; // створює мультимножину значень типу employee

Методи

Алгоритми – це робочі інструменти STL, що виконують складні операції типу сортування і пошуку. Однак для виконання простіших операцій, специфічних для конкретного контейнера, потрібні методи.

В таблиці 10.3 представлені деякі найпопулярніші методи, імена та призначення яких спільні для більшості класів контейнерів.

Таблиця 15.3

Деякі методи, спільні для всіх контейнерів