Всі попередні типи контейнерів (розглянуті докладно або згадувані: vector, list, deque) - Це послідовні колекції, в яких елементи послідовно упорядковані один за іншим, а відрізняються вони між собою способом доступу до елементів.
Іншу велику категорію контейнерів складають так звані асоціативні контейнери, які представляють собою, фактично, таблицы, пошук значень в яких проводиться за деякими ключам.
Але перш ніж деталізувати асоціативні контейнери, звернемо увагу на такий шаблонний клас (в складі СТЛ) як пара<>. Це досить проста конструкція. Кожен такий об'єкт являє зв'язну пару полів first і second. При побудові таблиць (в STL або в ваших власних класах) ці поля можуть представляти як ключ, так і значення. Але не будемо поспішати - шаблонний клас пара<> і сам по собі може становити інтерес безвідносно до контейнерів.
Ми можемо, например, визначити класс представлення точок 2D площині для вирішення широкого класу геометричних задач (point.h файл):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | #include <iostream> using namespace std; // класс point наследуется от класса pair<float, float> class point : protected pair<float, float> { public: // конструкторы point(void) { first = second = 0; } point(float x, float y) { first = x; second = y; } point operator -(const point& sub) { point p(*this); p.first -= sub.first; p.second -= sub.second; return p; // разница по координатам } float abs(void) { return sqrt(first * first + second * second); return 0; } inline friend ostream& operator <<(ostream& out, const point& obj) { return out << "<" << obj.first << "," << obj.second << ">"; return out; } }; int main(int argc, char *argv[]) { point p1(1, 3), p2(3, 1); cout << "the distance between two points " << p1 << " & " << p2 << " is " << (p1 - p2).abs() << endl; } |
точка p(*this); означає, що створюється нова змінна (об'єкт) класса точка, і викликається її конструктор копіювання. Для ініціалізації береться значення поточного об'єкта *this – то на що вказує указатель this. Тобто,. нова змінна точка р створюється, як копія поточного об'єкта. В іншому вам все повинно бути зрозуміло.
Результат:
тепер, коли ми бачимо, що з себе представляє шаблонний клас пара<>, ми можемо перейти до огляду того, що представляють собою основні асоціативні контейнери STL.
На відміну від розглянутих раніше послідовних контейнерів, де розташування елемента визначається його положенням серед інших елементів, в асоціативних контейнерах елементи зберігаються як пара (пара<>) <ключ, значение>. Для пошуку значення елемента потрібно його ключ пошуку, який може бути найрізноманітніших типів.
Примітка: Можна вважати, що в масиві или векторі ключем пошуку є індекс, який завжди має целочисленное значение. За аналогією, шаблонний тип таблиці (хеш-таблиці) карта<>, з якого ми почнемо огляд асоціативних типів, можна розглядати, як масив або вектор (для простоти розуміння ). Він може індексуватися будь-яким (але завжди тільки одним) довільним типом ключа, типу: назва[ 'а’ ], або платити[ “Іванов” ].
Одним з найбільш часто використовуваних асоціативних контейнерів STL є карта<> - таблиця, масив пар <ключ, значение>, в якому пошук елемента проводиться по ключу.
Ключ може мати будь-який складний тип, за умови, що для цього типу існує операція порівняння (менше більше), або така операція реалізується користувачем і вказується при створенні таблиці. Для ілюстрації найпростішого застосування карта<> скористаємося вже розглянутим раніше прикладом з базою даних студентів факультету:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | #include <iostream> #include <string> #include <map> using namespace std; struct data1 { int group, age, scholarship; // группа, возраст, стипендия data1(void) { group = age = scholarship = 0; } data1(int group, int age, int scholarship = 0) : group(group), age(age), scholarship(scholarship) {} data1(const data1& d) : group(d.group), age(d.age), scholarship(d.scholarship) {} inline friend ostream& operator <<(ostream& out, const data1& obj) { return out << "[" << obj.group << " : " << obj.age << " : " << obj.scholarship << " ]"; } }; // это и есть наша таблица, журнал деканата, ФИО здесь - ключ: typedef map< string, data1 > faculty; int main(void) { setlocale(LC_ALL, "rus"); faculty filology; // заполняем поочерёдно 3 записи в журнал: filology.insert(pair< string, data1 >("Сидоров С.С.", data1(13, 19, 1500))); filology.insert(pair< string, data1 >("Иванов И.И.", data1(13, 20))); filology.insert(pair< string, data1 >("Петров П.П.", data1(11, 21))); // вывод на экран ФИО и учётных данных for (auto i = filology.begin(); i != filology.end(); i++) { cout << i->first << " : " << i->second << endl; } data1 d1(filology["Иванов И.И."]); data1 d2 = filology["Иванов И.И."]; cout << d2 << endl; } |
Результат:
Навіть такий поверхневий приклад (поки ми не заглибилися в деталі асоціативних контейнерів) дозволяє побачити і зробити деякі висновки:
елементи, поміщаються в таблицю, розміщені не в порядку їх приміщення (як було з vector или list), а в відсортованому порядку по значенням ключа (FIO);
Ось чому для типу даних ключа повинна або існувати операція порівняння, або вона повинна бути створена користувачем;
Для пошуку (по ключу) в асоціативних контейнерах використовується не послідовний перебір всіх елементів, а надзвичайно ефективні і складні алгоритми, відпрацьовані за роки (і навіть десятиліття) СТЛ існування . Зазвичай для реалізації карта<> використовується техніка червоно-чорних дерев ... але деталі цього не принципові. Важливим висновком з цього факту має стати те, що пошук в асоціативних контейнерах вельми швидкий, і він набагато краще, ніж якби ви спробували його реалізовувати вручну.
Автор, ти мудак, школота срана. На що я витратив час?
Приклади коду громіздкі, новачкові суть вловити складно!
Таке відчуття, що коментарі тут пишуть розумово відсталі.
карта, комплект, мультімножество, MultiMap – реалізовані НЕ через хеш таблиці, а через червоно-чорні дерева, принаймні так в gcc. Через хеш таблиці реалізовані контейнери з префіксом unordered_. Дуже дивно що автор з 40-річним стажем і таким значним списком досягнень про це не знає.
Чому в прикладі point у функціях дещо return, якщо вони без розгалужень?