Головна

Адаптери контейнерів | Алгоритми | Ітератори | До програми включений заголовочний файл ALGORITHM. В цьому файлі містяться оголошення алгоритмів STL. | Функціональні об'єкти | Функції користувача замість функціональних об'єктів | Додавання _if до аргументів | Вектори | Черги з двостороннім доступом | Ітератори як інтелектуальні вказівники |

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

  1. Послідовні контейнери

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

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

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

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

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

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

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



Послідовні контейнери | Set <int> intSet; // створює множину значень int
© um.co.ua - учбові матеріали та реферати