Асоціативні контейнери 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);

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

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

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

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

Про Olej

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

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

Ваша електронна адреса не буде опублікований. Обов'язкові поля позначені * *