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

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

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

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

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

#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;
}

#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 є карта<> - таблиця, масив пар <ключ, значение>, в якому пошук елемента проводиться по ключу.

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

#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; 
}

#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);
Ось чому для типу даних ключа повинна або існувати операція порівняння, або вона повинна бути створена користувачем;

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

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

Павло говорить:
03.05.2018 at 13:14
Автор, ти мудак, школота срана. На що я витратив час?
відповісти
Євген говорить:
18.05.2018 at 17:44
Приклади коду громіздкі, новачкові суть вловити складно!
відповісти
Мимопроходил говорить:
18.07.2018 at 15:17
Таке відчуття, що коментарі тут пишуть розумово відсталі.
відповісти
мистецтво говорить:
03.10.2018 at 00:53
карта, комплект, мультімножество, MultiMap – реалізовані НЕ через хеш таблиці, а через червоно-чорні дерева, принаймні так в gcc. Через хеш таблиці реалізовані контейнери з префіксом unordered_. Дуже дивно що автор з 40-річним стажем і таким значним списком досягнень про це не знає.
відповісти
Павло говорить:
20.08.2023 at 07:32
Чому в прикладі point у функціях дещо return, якщо вони без розгалужень?
відповісти