Асоціативні контейнери STL. Частина 6

Оціни цю статтю




c ++ для початківців, Стандартна бібліотека шаблонів, асоціативні контейнери STL C ++, пара C ++, карта<> C ++Всі попередні типи контейнерів (розглянуті докладно або згадувані: vector, list, deque) - Це послідовні колекції, в яких елементи послідовно упорядковані один за іншим, а відрізняються вони між собою способом доступу до елементів.

Іншу велику категорію контейнерів складають так звані асоціативні контейнери, які представляють собою, фактично, таблицы, пошук значень в яких проводиться за деякими ключам.

Але перш ніж деталізувати асоціативні контейнери, звернемо увагу на такий шаблонний клас (в складі СТЛ) як пара<>. Це досить проста конструкція. Кожен такий об'єкт являє зв'язну пару полів first і second. При побудові таблиць (в STL або в ваших власних класах) ці поля можуть представляти як ключ, так і значення. Але не будемо поспішати - шаблонний клас пара<> і сам по собі може становити інтерес безвідносно до контейнерів.

Ми можемо, например, визначити класс представлення точок 2D площині для вирішення широкого класу геометричних задач (point.h файл):

точка p(*this); означає, що створюється нова змінна (об'єкт) класса точка, і викликається її конструктор копіювання. Для ініціалізації береться значення поточного об'єкта *this – то на що вказує указатель this. Тобто,. нова змінна точка р створюється, як копія поточного об'єкта. В іншому вам все повинно бути зрозуміло.

Результат:c ++ для початківців, Стандартна бібліотека шаблонів, асоціативні контейнери STL C ++, пара<> C ++

тепер, коли ми бачимо, що з себе представляє шаблонний клас пара<>, ми можемо перейти до огляду того, що представляють собою основні асоціативні контейнери STL.

На відміну від розглянутих раніше послідовних контейнерів, де розташування елемента визначається його положенням серед інших елементів, в асоціативних контейнерах елементи зберігаються як пара (пара<>) <ключ, значение>. Для пошуку значення елемента потрібно його ключ пошуку, який може бути найрізноманітніших типів.

Примітка: Можна вважати, що в масиві или векторі ключем пошуку є індекс, який завжди має целочисленное значение. За аналогією, шаблонний тип таблиці (хеш-таблиці) карта<>, з якого ми почнемо огляд асоціативних типів, можна розглядати, як масив або вектор (для простоти розуміння ). Він може індексуватися будь-яким (але завжди тільки одним) довільним типом ключа, типу: назва[ 'а’ ], або платити[ “Іванов” ].

Одним з найбільш часто використовуваних асоціативних контейнерів STL є карта<> - таблиця, масив пар <ключ, значение>, в якому пошук елемента проводиться по ключу. Ключ може мати будь-який складний тип, за умови, що для цього типу існує операція порівняння (менше більше), або така операція реалізується користувачем і вказується при створенні таблиці. Для ілюстрації найпростішого застосування карта<> скористаємося вже розглянутим раніше прикладом з базою даних студентів факультету:

Результат:c ++ для початківців, Стандартна бібліотека шаблонів, асоціативні контейнери STL C ++, пара C ++, карта<> C ++Навіть такий поверхневий приклад (поки ми не заглибилися в деталі асоціативних контейнерів) дозволяє побачити і зробити деякі висновки:

  • елементи, поміщаються в таблицю, розміщені не в порядку їх приміщення (як було з vector или list), а в відсортованому порядку по значенням ключа (FIO);

  • Ось чому для типу даних ключа повинна або існувати операція порівняння, або вона повинна бути створена користувачем;

Для пошуку (по ключу) в асоціативних контейнерах використовується не послідовний перебір всіх елементів, а надзвичайно ефективні і складні алгоритми, відпрацьовані за роки (і навіть десятиліття) СТЛ існування . Зазвичай для реалізації карта<> використовується техніка червоно-чорних дерев ... але деталі цього не принципові. Важливим висновком з цього факту має стати те, що пошук в асоціативних контейнерах вельми швидкий, і він набагато краще, ніж якби ви спробували його реалізовувати вручну.

Нові уроки з програмування:

Olej

Про Olej

Стаж практичних програмних розробок близько 40 лет. Викладач міжнародної софтверної компанії Global Logic. Постійний автор публікацій IBM Developer Works. Науковий редактор книжкового видавництва комп'ютерної літератури "Символ-Плюс", Санкт-Петербург.

залишити коментар

Код розміщуйте в тегах: <pre class="lang:C ++ декодуванням:true ">ВАШ КОД</заздалегідь>