Основи програмування на С ++ для початківців

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

Всі попередні типи контейнерів (розглянуті докладно або згадувані: 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);

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

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

5 думки про "Асоціативні контейнери STL. Частина 6

  1. карта, комплект, мультімножество, MultiMap – реалізовані НЕ через хеш таблиці, а через червоно-чорні дерева, принаймні так в gcc. Через хеш таблиці реалізовані контейнери з префіксом unordered_. Дуже дивно що автор з 40-річним стажем і таким значним списком досягнень про це не знає.

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

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