§25 Ассоциативные контейнеры

Множество и мультимножество. Классы set и multiset

Общие сведения

Ассоциативный контейнер setмножество (или набор) имеет (в отличие от последовательных контейнеров) принципиально иную организацию хранения данных в виде, так называемого, сбалансированного бинарного дерева, что обеспечивает быстрый поиск элементов в этом контейнере. Для начала работы с этим контейнером необходимо подключить заголовок set следующей директивой:

#include <set>

Контейнер set относится к ассоциативным контейнерам (в библиотеке STD восемь типов таких контейнеров), которые хранят пары «ключ-значение». Но, в отличие от других ассоциативных контейнеров, set предназначен только для хранения уникальных ключей. При добавлении элемента в контейнер он автоматически занимает необходимую позицию в упорядоченной совокупности других элементов, т. е. осуществляется автоматическая сортировка. При вставке или удалении элементов множества итераторы, указывающие на элементы этого множества, остаются рабочими. Итераторы, используемые для setConstant bidirectional iterator (константный двусторонний итератор), нельзя передавать в функции библиотеки algorithm, которые не поддерживают данный тип итераторов. Следует использовать те методы работы с элементами массива (в замен алгоритмам), которые определены в данном классе. Это также означает, что удалять ключи (иначе, элементы множества) с помощью итераторов тоже нельзя! Для вставки и удаления элементов необходимо использовать методы класса. Множества не поддерживают операцию обращения по индексу, вследствие этого, элементы массива можно обходить применяя диапазонный цикл for или итераторы. Причем контейнер поддерживает все стандартные функции для получения итераторов (упомянутые нами ранее для контейнера vector).

Класс multiset

Класс multiset (мультимножество) определен в том же заголовке, что и класс set. Мультимножество позволяет осуществлять работу с массивами, которые могут содержать дубликаты ключей. Во всем остальном работа с multiset не будет отличаться от работы с контейнером set.

Конструкторы

Типы объектов классов set и multiset могут содержать функцию сравнения (comp). Если такая функция отсутствует, то она задана неявно функцией less<> (операция <).
Объекты класса set можно получить с помощью следующих конструкторов:
Конструктор копирования/перемещения

set<type, comp> ar(other_ar); // или
set<type, comp> ar = other_ar;

Итераторами (вставки)

set<type, comp> ar(first, last); // или
set<type> ar(first, last, comp);

Списком инициализации

set<type, comp> ar {}; // или
set<type, comp> ar = {};

Деструктор (уничтожает объект класса set)

ar.~set();
Методы для работы с размером

Для работы с размером и объемом set определены только эти методы:

  • empty() Возвращает true, если set пуст
  • size() Возвращает количество элементов в set
  • max_size() Возвращает максимально возможное количество элементов
Модификаторы
  • clear() Очищает контейнер.
  • insert() Вставляет элементы. Если вставляемый элемент перемещается или копируется, то возвращается пара pair<iterator,bool> - итератор на вставленный элемент и логический флаг успешности вставки. Если первый аргумент итератор-подсказка, а второй - вставляемый элемент, то возвращается итератор вставки. Если аргумент диапазон итераторов или список инициализации, то ничего не возвращается. Итераторы и указатели остаются в рабочем состоянии.
  • emplace() Создает элементы на месте. Аргументы направляются в конструктор элемента. Итераторы и указатели остаются в рабочем состоянии.
  • erase() Удаляет элементы. Если аргументом является итератор или диапазон итераторов, то возвращается итератор, следующих за последним удаленным элементом. Если аргументом является ключ, то возвращается количество удаленных элементов. Недействительными становятся только итераторы на удаленные элементы, все остальные - в силе.
  • swap() Обменивает содержимое.
Методы поиска

К наиболее важному аспекту работы с set относится поиск элементов, который осуществляется очень эффективно, поэтому set имеет несколько собственных методов поиска.

  • count(key) Возвращает (size_t) количество элементов, соответствующих определенному ключу
  • find(key) находит элемент с конкретным ключом. Возвращает константный итератор позиции элемента или итератор end(), если таковой не найден.
  • equal_range(key) возвращает диапазон (pair итераторов, см. ниже), содержащий все элементы с ключом key в контейнере (по ссылке).
  • lower_bound(key) возвращает итератор на первый элемент, который меньше, чем key
  • upper_bound(key) возвращает итератор на первый элемент, который больше, чем key

Для контейнера set определены все операции сравнения. Элементы контейнера set сравниваются лексикографически.
Приведем пример задачи.
Программа 25.1 Дана последовательность n целых чисел из отрезка [10, 50], полученная случайным образом. Определить количество чисел из набора {10, 20, 30, 40, 50} имеющихся в данной последовательности.

#include <iostream>
#include <vector>
#include <set>
#include <random>
#include <ctime>
using namespace std;

int main() {
	default_random_engine rnd(time(0));
	uniform_int_distribution<unsigned> g(10, 50);
	vector<int> mas;
	int n, k = 0;
	cout << "n = "; cin >> n;
	for (int i = 0; i < n; i++) {
		int d = g(rnd);
		mas.push_back(d);
		cout << mas[i] << " ";
	}
	set<int> ar {10, 20, 30 , 40, 50};
	for (int i = 0; i < n; i++)
		if (ar.count(mas[i])) k++;
	cout << "\nНайдено - " << k 
	     << " элементов."  << endl;
	return 0;
}

Можно задаться вопросом: насколько set эффективен по сравнению с vector? Составим программу в которой осуществляется заполнение массивов множества и вектора случайными числами и производится поиск заданного значения.
Программа 25.2

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <random>
#include <ctime>
#include <chrono>
using namespace std;

int main() {
	int n;
	default_random_engine rnd(time(0));
	uniform_int_distribution<unsigned> g(1, 10000);
	cout << "n = "; cin >> n;
	const int k = 100;
	int a = n;
	auto start = chrono::system_clock::now();
	vector<int> ar1;
	while (a--) ar1.push_back(g(rnd));
	auto result1 = find(ar1.begin(), ar1.end(), k);
	auto end = chrono::system_clock::now();
	auto elapsed = end - start;
	cout << "vector => "
		 << elapsed.count()
		 << endl;
	a = n;
	start = chrono::system_clock::now();
	set<int> ar2;
	while (a--) ar2.emplace(g(rnd));
	auto result2 = ar2.find(k);
	end = chrono::system_clock::now();
	elapsed = end - start;
	cout << "set    => "
		 << elapsed.count()
		 << endl;
	return 0;
}
n = 1000000
vector => 67106305
set    => 716554449

Производительность множества будет значительно уступать вектору. Нужно иметь ввиду, что операция заполнения множества производится с сортировкой, а это, естественно, затратная операция. Но если мы произведем замер производительности в обоих массивах только для поиска, то ситуация изменится в пользу set:

n = 1000000
vector => 11343
set    => 693

Какой можно из этого сделать вывод? Не следует использовать множество (или мультимножество) и словари для получения элементов из других последовательностей в цикле, поэлементно (поскольку на каждом шаге производится автоматическая сортировка). Однако, если в программе производится частый поиск элементов в массиве, то setmap) здесь вне конкуренции. Если сортировка не является необходимой, то лучше, в этом случае, использовать неупорядоченные ассоциативные массивы с возможностью быстрого поиска (о которых речь пойдет ниже).
Необходимо получать последовательность целиком при создании объекта set или с помощью метода insert и итераторов. Таким образом, словари и карты должны являться либо целевыми массивами для вставки, либо массивами-источниками. Но это не является, конечно, строгим правилом. Исходить нужно из практической необходимости и ресурсоёмкости поставленной задачи.

Вспомогательный класс pair

Для дальнейшего рассмотрения работы с прочими ассоциативными контейнерами нам необходимо познакомиться со вспомогательным шаблонным классом pair. Этот класс предоставляет возможность хранить два разнородных объекта, как единое целое. pair используется в разных местах STD, в частности, в алгоритме minmax(), методе класса set equal_range(), для работы с элементами ассоциативных контейнеров, которые также представляют из себя пары: Ключ: Значение.

Конструктор

Для создания объекта пары используется следующий синтаксис:

pair<T1, T2> p1;
pair<T1, T2> p2(val1, val2);
pair<T1, T2> p3(p1);
Операции
  • p.first - доступ к первому значению пары (по ссылке)
  • p.second - доступ ко второму значению пары (по ссылке)
  • p->first - доступ к первому значению пары (по указателю)
  • p->second - доступ ко второму значению пары (по указателю)
  • p = other_p - присваивание (с возможностью неявного преобразования типов по правилам C++)
  • p.swap(other_p) или swap(p, other_p) - обмен значениями между p и other_p
  • <, <=, >, >=, ==, != - операции сравнения
  • make_pair(val1, val2) - возвращает пару
Программа 25.3

#include <iostream>
using namespace std;

int main() {
	int a1 = 1, b1 = 2;
	int a2 = 3, b2 = 4;
	pair<int, int> par1(a1, b1);
	pair<int, int> *par2 = new pair<int, int>(a2, b2);
	cout << par1.first
		 << "\n"
		 << par1.second
		 << endl;
	cout << par2->first
		 << "\n"
		 << par2->second
		 << endl;
	return 0;
}

Словарь (карта). Классы map и multimap

Общие сведения

Класс map (словарь, карта, отображение) реализует упорядоченный ассоциативный массив элементов, представляющих из себя пары уникальных ключей и соответствующих им значений. Ключ и значение могут иметь произвольный тип, но, поскольку поиск в массиве осуществляется по ключам, то тип ключа должен разрешать критерий сортировки (функции сравнения). По умолчанию (как и для set) используется функция сортировки less<> (операция <). Если в массиве предполагается хранить дубликаты ключей, то необходимо использовать контейнер multimap. Оба контейнера определены в одном заголовочном файле map:

#include <map>

Словарь имеет общий с множеством набор функций. Тип данных элемента map:

pair<const Key, T>

И в словарях, и в множествах - ключи константны. Это означает, что при обходе элементов словаря (и множества), с помощью итераторов, нельзя изменять ключи. Доступ к ключам осуществляется только для чтения. Значения же элементов в словаре можно и читать, и изменять. Элементы map можно вставлять и удалять с помощью специальных методов класса.

Конструкторы

Типы объектов классов map и multimap могут содержать функцию сравнения (comp). Если такая функция отсутствует, то она задана неявно функцией less<>. Объекты класса map можно получить с помощью следующих конструкторов:
Конструктор копирования/перемещения

map<typeKey, typeValue, comp> ar(other_ar); // или
map<typeKey, typeValue, comp> ar = other_ar;

Итераторами (вставки)

map<typeKey, typeValue, comp> ar(first, last); // или
map<typeKey, typeValue> ar(first, last, comp);

Списком инициализации

map<typeKey, typeValue, comp> ar {}; // или
map<typeKey, typeValue, comp> ar = {};

Примечание. Каждая пара заключается во вложенные фигурные скобки, например: {{'a', 13.2}, {'a', 6.8}, {'b', 9.9}}.
Деструктор (уничтожает объект класса map)

ar.~map();
Доступ к элементам

Ассоциативные контейнеры не поддерживают произвольный доступ к элементам. Для того, чтобы получить доступ к элементам контейнера необходимо использовать либо диапазонный цикл for, либо итераторы. При обращении к элементу можно получить ключ и значение используя интерфейс пары (см. выше), не забывая, при этом, что ключ является константной величиной и изменять его нельзя. Если применяется диапазонный цикл for, то доступ к ключу и значению можно получить по ссылке:

for (auto &m: ar) {
	if (m.second > 10)
		m.second = 20;
	cout << m.first << " "
		 << m.second << endl;
}

Если используются итераторы, то применяется цикл while и интерфейс указателей. Такой способ более гибкий, так как позволяет непосредственно управлять итераторами. Доступны любые формы стандартных итераторов:

  • begin(), cbegin() - возвращает итератор на первый элемент
  • end(), cend() - возвращает итератор на элемент, следующий за последним
  • rbegin(), crbegin() - возвращает обратный итератор на первый элемент
  • rend(), crend() - возвращает обратный итератор на элемент, следующий за последним
auto fst = m.cbegin();
auto lst = m.cend();
while (fst != lst) {
	auto d = fst -> first;
	auto S = fst -> second;
	if (S == "SwEr34gg0zf")
		S = "00000000";
	cout << d << " " << S << endl;
	fst++;
}

Тип итераторов map - BidirectionalIterator (Двусторонний итератор), что означает возможность перемещения итератора в обоих направлениях. Такой тип итераторов поддерживает операции инкремента и декремента.
На основе значения ключа можно получать итераторы с помощью очень удобных и быстрых методов поиска: find(), equal_range(), lower_bound(), upper_bound(), которые мы описали выше. Пример использования этих методов можно увидеть в программе 25.4.

Операция [] и метод at()

Для словарей (в отличие от множеств, в которых данные операции не применимы) определены операция обращения по индексу ([]) и метод at(). Но использование этих функций отличается от использования подобных операций в последовательных контейнерах.

  • m[Key] 1) Если значения с ключом Key в массиве не существует, то будет осуществлена вставка нового значения с ключом Key, например, ar["price"] = 22.3. Если присваивания не производится, то новое значение инициализируется значением по умолчанию.
    2) Если значение с ключом Key существует, то будет возвращена ссылка на элемент.
    Примечание. Используйте эту операцию внимательно, т. к. это может привести к нежелательным результатам, например, вставка (и вывод) нулевого значения на выводе: cout << ar["price"]
  • m.at(Key) Возвращает ссылку на элемент с ключом Key. Если такого элемента не существует, то генерируется исключение out_of_range

#include <iostream>
#include <map>
using namespace std;

int main() {
	map<string, int> M;
	M["WWW"] = 20;
	M["RRR"];
	M["SSS"] = 1;
	M["###"] = 10000;
	for (auto &r : M)
		cout << r.first << " " << r.second << endl;
	return 0;
}
### 10000
RRR 0
SSS 1
WWW 20

Отсюда видно, что в качестве индекса может выступать любой тип ключа, а не только целый тип, как в последовательных контейнерах. Поскольку данные операции работают медленнее соответствующих методов, последним отдается предпочтение.

Вставка, поиск и удаление элементов в словаре

Вставка элементов

В ассоциативных контейнерах map и set элементы можно добавить только с помощью специальных методов класса insert и emplace (а также emplace_hint). В контейнерах map метод insert() принимает аргумент - pair, который необходимо создать. Существует несколько способов создания пары:

// С помощью специального типа value_type класса map:
m.insert(map<typeKey, typeValue>::value_type(Key, Value));

// С помощью типа pair<>:
m.insert(pair<typeKey, typeValue>(Key, Value));

// С помощью метода make_pair():
m.insert(make_pair(Key, Value));

В программе ниже продемонстрирован процесс заполнения словаря с помощью метода insert(), аргументы которого, в свою очередь, создаются с помощью метода make_pair(). Также в этой программе показано как можно вставить пару литералов (список инициализации). Пара литералов должна заключаться в дополнительные фигурные скобки.
Программа 25.4 (Постановка задачи в комментариях)

#include <iostream>
#include <random>
#include <ctime>
#include <string>
#include <map>
#include <vector>
using namespace std;

int main() {
	multimap<string, int> rat;
	vector<string> lit {"a1", "a2", "a3",
						"b1", "b2", "b3",
						"c1", "c2", "c3"};
	default_random_engine rnd(time(0));
	uniform_int_distribution<int> d(-10, 20);
	uniform_int_distribution<int> c(0, 8);
	//=============================1==============================//
	// Заполняем словарь: случайный ключ получает случайное       //
	// значение. Используем цикл while                            //
	//============================================================//
	int n;
	cout << "Введите количество элементов словаря: ";
	cin >> n;
	while (n--) {
		string S = lit[c(rnd)];
		int D = d(rnd);
		pair<string, int> tpr = make_pair(S, D);
		rat.insert(tpr);
		// Для emplace пару можно не создавать:
		//rat.emplace(S, D);
	}
	//=============================2==============================//
	// Вставить 3 дополнительных элемента с помощью трех          //
	// различных операций                                         //
	//============================================================//
	rat.emplace("d1", 10);
	rat.insert({"d2", -5});
	rat.insert(pair<const string, int>("d3", 6));
	//=============================3==============================//
	// Вывести  все элементы расположенные между первым и         //
	// вторым ключом                                              //
	//============================================================//
	string el_l, el_r;
	cout << "Введите ключи:\n";
	cout << "1-ый: "; cin >> el_l;
	cout << "2-ой: "; cin >> el_r;
	auto fst = rat.lower_bound(el_l);
	auto lst = rat.upper_bound(el_r);
	while (fst != lst) {
		cout << fst -> first
			 << " => "
			 << fst -> second
			 << endl;
		fst++;
	}
	//==============================4==============================//
	// Вывести значения только тех элементов с искомым ключом,     //
	// которые имеют рейтинг не меньше 10. Если таких элементов не //
	// существует - вывести 0. Используем equal_range,             //
	// возвращающую ссылку на пару итераторов диапазона искомых    //
	// ключей                                                      //
	//=============================================================//
	string tmp;
	cout << "Введите ключ: ";
	cin >> tmp;
	auto first = rat.equal_range(tmp).first;
	auto last = rat.equal_range(tmp).second;
	if (first == last)
		cout << 0 << endl;
	else
		while (first != last) {
			auto r = first -> second;
			if (r >= 10)
				cout << r << " ";
			first++;
		}
	return 0;
}

Более компактным решением для вставки пары является использование метода emplace(). В этом случае фигурные скобки не нужны, а для двух аргументов (ключа и значения) не нужно создавать и саму пару. Если аргументов для ключа и значения более чем два, то инициализатором будет структура на основе кортежей для ключей и их значений, куда и будут переданы аргументы.

Поиск элементов

Преимуществом ассоциативных контейнеров перед другими видами контейнеров является быстрый поиск элементов по ключам. Использование основных инструментов для поиска продемонстрирована во второй и третьей части программы 25.4. Поскольку значение элемента является изменяемой величиной, то, зачастую, удобно использовать один контейнер map, вместо нескольких контейнеров (например, vector или array). Эффективность такого подхода проявится на большом количестве элементов или в задачах, в которых количество элементов изначально неопределено. В первой части программы 25.5 применяется именно такой подход. Аналогичное решение на векторах потребовало бы использования нескольких массивов, а при использовании статических C-массивов или array так же и большого количества элементов массива, про запас, что привело бы к перерасходу памяти. К тому же, пришлось бы привлекать алгоритм быстрого поиска, а таковой имеется в классе map как стандартный инструмент (в данной программе метод find()).

Условие задачи
Программа 25.5

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

int main() {
	size_t K, N;
	cin >> K >> N;
	//==============================1==============================//
	// Получаем протокол в словарь, который позволяет эффективно   //
	// искать участника по ключу и ограничиться использованием     //
	// одного массива                                              //
	//=============================================================//
	map<string, string> rat;
	for (size_t i = 0; i < N; i++) {
		string S;
		int d;
		cin >> d >> S;
		string temp = to_string(d) + '.' + to_string(i);
		// Ищем в словаре по ключу
		auto pos = rat.find(S);
		// если элемент не найден, то добавляем в словарь ключ и значение
		if (pos == rat.end()) {
			rat.emplace(S, temp);
		} else {
			// иначе проверяем значение элемента словаря
			string old = pos -> second;
			old = old.substr(0, old.find('.'));
			// и, если оно меньше, то заменяем
			if (stoi(old) < d)
				pos -> second = temp;
		}
	}
	//==============================2==============================//
	// Реализация списка награжденных участников. Чтобы управится  //
	// с временной меткой, именем участника и его результатом      //
	// создаем два вектора. Устанавливаем размер для массивов на   //
	// основе величины размера словаря, равного числу участников.  //
	//=============================================================//
	int R = rat.size();
	size_t save = R;
	// массив для хранения имени и временной метки
	vector<string> tabn(R);
	// массив для хранения результатов (заполняем нулями)
	vector<int> tabr(R, 0);
	auto fst = rat.cbegin();
	auto lst = rat.cend();
	while (fst != lst) {
		string name = fst -> first;
		string res = fst -> second;
		// Максимальный результат участника
		int r = stoi(res.substr(0, res.find('.')));
		// его временная метка
		int n = stoi(res.substr(res.find('.') + 1, string::npos));
		// для того, чтобы не создавать три массива (обойдемся двумя),
		// метку времени поставим перед именем
		name = res.substr(res.find('.') + 1, string::npos) + '.' + name;
		// Определяем порядок следования
		for (int i = 0; i < R; i++) {
			if (tabr[i] > r) continue;
			if (tabr[i] == 0) {
				tabr[i] = r;
				tabn[i] = name;
				break;
			}
			if (tabr[i] < r) {
				// Смещаем вправо
				for (int j = R - 2; j >= i; j--) {
					tabr[j + 1] = tabr[j];
					tabn[j + 1] = tabn[j];
				}
				tabr[i] = r;
				tabn[i] = name;
				break;
			}
			if (tabr[i] == r && stoi(tabn[i].substr(0, tabn[i].find('.'))) > n) {
				// Будем сдвигать со следующего
				i++;
				for (int j = R - 2; j >= i; j--) {
					tabr[j + 1] = tabr[j];
					tabn[j + 1] = tabn[j];
				}
				tabr[i] = r;
				tabn[i] = name;
				break;
			}
		}
		fst++;
	}
	// Выводим К призеров
	if (save < K) K = save;
	for (size_t i = 0; i < K; i++)
		cout << i + 1
			 << ". "
			 << tabn[i].substr(tabn[i].find('.') + 1, string::npos)
			 << " ("
			 << tabr[i]
			 << ")" << endl;
	return 0;
}
Удаление элементов

Для удаления элементов из словаря, как и для множеств, используется метод erase(), описанный нами выше. Используется данный метод аналогично тому, как он используется в классе set. Заметим, однако, что аргументами могут выступать значения методов lower_bound() и upper_bound(), которые позволяют более эффективно определять диапазоны ключей:

iterator m.erase(m.lower_bound(key), m.upper_bound(key));

Неупорядоченные ассоциативные контейнеры

Неупорядоченные ассоциативные контейнеры (далее - хэши) представляют собой хэш-таблицы. Хеш-таблицей называется структура данных, позволяющая хранить пары вида «ключ» — «хеш-код». Хеш-таблицы применяются с целью ускорение поиска. Аналогом хеширования может служить размещение слов в словаре в алфавитном порядке: первая буква слова является его хеш-кодом, и при поиске просматривается не весь словарь, а только слова, начинающиеся на нужную букву. Таким образом, хэш-функция используется как один из аргументов в конструкторах хэшей. Теория хэш-функций выходит за рамки нашего курса и здесь мы ограничимся лишь упоминанием того, что для базовых арифметических типов и типа string определена хэш-функция по умолчанию (hash<>). С помощью хэш-функции массив разделяется на сегменты. В каждом сегменте (или слоте) элементы содержатся в виде односвязного списка. Для каждого элемента этого списка вычисляется одинаковый хеш-код. Фактический порядок элементов в хэше зависит от хэш-функции, функции сравнения, порядка вставки, коэффициента максимального заполнения (см. ниже) и текущего числа сегментов. Считается, что эффективность поиска, вставки и удаления элемента в хэшах является их главным преимуществом по сравнению с упорядоченными ассоциативными контейнерами map и set. Однако выбор контейнера будет зависеть от типа решаемой задачи. Рекомендуется производить тестовые замеры производительности алгоритма в различных условиях и только после этого выбирать между упорядоченным и неупорядоченным контейнером (если для вас не очевидна итоговая производительность составленной вами программы). Поскольку разница в производительности, зачастую, не столь существенна, а сама задача решается проще с помощью упорядоченных set или map. В программе 25.6 (тестирование производилось в среде GCC 6.3.1) unordered_set показал лучшую производительность по сравнению с set.
К хэшам относятся следующие контейнеры STD:

  • unordered_set
  • unordered_map
  • unordered_multiset
  • unordered_multimap

Для начала работы с хэшем необходимо включить соответствующий заголовочный файл:

#include <unordered_set>
#include <unordered_map>

Для создания объекта хэша необходимо использовать определение типа включающее в себя:

  • Тип ключа
  • Тип значения (для map)
  • Тип хэш-функции (не обязательно, по умолчанию hash<>)
  • Тип функции эквивалентности (не обязательно, по умолчанию equal_to<>)
  • Тип распределителя (не обязательно)
unordered_map<Key, Value, Hash, Eq> un;

Элементы unordered_map и unordered_multimap могут иметь любой тип для ключа и значения, который поддерживает копирование или перемещение, а ключ должен быть совместим с функцией эквивалентности. Если тип ключа является пользовательским, то для данного типа должна создаваться собственная хэш-функция и, в этом случае, имя должно указываться явно. Создать объект хэша можно следующими способами:

unordered_set<TypeKey> uns;
unordered_set<TypeKey> uns(numseg);
unordered_set<TypeKey> uns(InputIt_first, InputIt_last);
unordered_set<TypeKey> uns(other_uns); // или
unordered_set<TypeKey> uns = other_uns;
unordered_set<TypeKey> uns(ilist);

Здесь numseg - минимальное количество сегментов (не обязательно, т. к. будет определено значение по умолчанию). Деструктор:

uns.~unordered_set();

Программа 25.6 Сравнение производительности set и unordered_set при выполнении одних и тех же операций (заполнение n-случайными числами и поиск ключа)

#include <iostream>
#include <unordered_set>
#include <set>
#include <random>
#include <ctime>
#include <chrono>
using namespace std;

int main() {
	default_random_engine rnd(time(0));
	uniform_int_distribution<unsigned> g(10, 50);
	unordered_set<int> unords;
	set<int> orders;
	int n;
	cout << "n = "; cin >> n;
	int k = 100, a = n;
	auto start = chrono::system_clock::now();
	while (n--) {
		orders.emplace(g(rnd));
	}
	auto res1 = orders.find(k);
	auto end = chrono::system_clock::now();
	auto elapsed = end - start;
	cout << "set => "
		 << elapsed.count()
		 << endl;
	start = chrono::system_clock::now();
	while (a--) {
		unords.emplace(g(rnd));
	}
	auto res2 = unords.find(k);
	end = chrono::system_clock::now();
	elapsed = end - start;
	cout << "unordered_set => "
		 << elapsed.count()
		 << endl;
	return 0;
}

Методы хэша

Помимо стандартных для всех контейнеров методов, хэши имеют ряд специфических методов. Вкратце, перечислим известные нам методы и более подробно остановимся на ранее неизвестных.

Итераторы

Поскольку тип итераторов - константный однонаправленный итератор, не поддерживается реверсивная форма стандартных итераторов.

Вместимость
  • empty()
  • size()
  • max_size()
Модификаторы
  • clear()
  • insert() Если вставляемый элемент перемещается или копируется, то возвращается пара pair<iterator,bool> - итератор на вставленный элемент и логический флаг успешности вставки. Если первый аргумент итератор-подсказка, а второй - вставляемый элемент, то возвращается итератор вставки. Если аргумент диапазон итераторов или список инициализации, то возвращается итератор вставки. Если во время вставки происходит рехэшинг, все итераторы и указатели становятся недействительными. Рехэшинг происходит только если число элементов больше, чем max_load_factor() * bucket_count()
  • emplace() Аналогично предыдущему, возвращается пара pair<iterator,bool>
  • erase() Указатели и итераторы удалённых элементов становятся недействительными.
  • swap()
Поиск
  • count()
  • find()
  • equal_range()
  • Для unordered_map:

  • at(const Key& key) - возвращает ссылку на значение элемента с ключом эквивалентным key. Если такого элемента не существует, то вернет исключение out_of_range.
  • operator[] Особенности этой операции, в применении к словарям, описаны выше. Если происходит вставка, результатом которой является рехэшинг контейнера, все итераторы аннулируются. В противном случае итераторы и указатели остаются без изменений. Рехэшинг происходит только если число элементов больше, чем max_load_factor() * bucket_count().

Примечание. Методы lower_bound и upper_bound не поддерживаются.

Интерфейс сегмента

Данные методы позволяют следить за состоянием контейнера. С их помощью можно получить визуальное представление хэша (см. программу 25.6).

  • begin(int), cbegin(int) - возвращает итератор на начало указанного сегмента
  • end(int), cend(int) - возвращает итератор на конец указанного сегмента
  • bucket_count() - возвращает количество сегментов (size_t)
  • max_bucket_count() - возвращает максимальное количество сегментов (size_t)
  • bucket_size() - возвращает количество элементов в конкретном сегменте (size_t)
  • bucket() - возвращает сегмент для конкретного ключа (size_t)

Программа 25.7 Тестирование производительности при различных значениях коэффициента максимального заполнения. Вывод структуры хэша (unordered_multiset).

#include <iostream>
#include <iomanip>
#include <unordered_set>
#include <random>
#include <ctime>
#include <chrono>
using namespace std;

int main() {
	default_random_engine rnd(time(0));
	uniform_int_distribution<unsigned> g(100, 999);
	unordered_multiset<int> unm;
	int n = 200;
	while (n--) unm.emplace(g(rnd));
	cout << "Количество сегментов в контейнере: "
		 << unm.bucket_count()
		 << "\n"
		 << "Коэффициент максимального заполнения: "
		 << unm.max_load_factor()
		 << endl;
	auto start = chrono::system_clock::now();
	auto res = unm.find(200);
	auto end = chrono::system_clock::now();
	auto elapsed = end - start;
	cout << "Первый замер => "
		 << elapsed.count()
		 << endl;
	// Устанавливаем собственное значение коэффициента
	unm.max_load_factor(0.7);
	unm.rehash(200);
	cout << "Количество сегментов в контейнере: "
		 << unm.bucket_count()
		 << "\n"
		 << "Коэффициент максимального заполнения: "
		 << unm.max_load_factor()
		 << endl;
	start = chrono::system_clock::now();
	res = unm.find(200);
	end = chrono::system_clock::now();
	elapsed = end - start;
	cout << "Второй замер => "
		 << elapsed.count()
		 << endl;
	cout << "Структура хэша" << endl;
	for (size_t i = 0; i < unm.bucket_count(); i++) {
		cout << "Сегмент №" << setw(3) << i << " => ";
		// Получаем локальные итераторы на сегмент
		auto first = unm.cbegin(i);
		auto last = unm.cend(i);
		while (first != last) {
			cout << *first++ << " ";
		}
		cout << endl;
	}
	return 0;
}
Вывод программы для 200 элементов
Управление хэшированием
  • load_factor() - возвращает (float) среднее количество элементов в сегменте
  • max_load_factor() - коэффициент максимального заполнения (средний размер сегмента). Перегружена: если используется без аргумента, то возвращает тип float (текущее значение коэффициента), если имеет параметр float, то устанавливает коэффициент максимального заполнения и ничего не возвращает (void)
  • rehash(size_type count) - перестраивая хэш-таблицу так, чтобы backet_count() >= count и bucket_count() > size() / max_load_factor()
  • reserve(size_type count) - устанавливает количество сегментов по числу необходимого для размещения, по меньшей мере, count элементов без превышения коэффициента максимального заполнения и рехэшинга контейнера.

Коэффициент максимального заполнения по умолчанию равен единице. Уменьшение коэффициента (и рехэшинг) может положительно отразиться на производительности программы. В программе 25.7 показано, что уменьшение коэффициента до 0.7 позволило в два раза увеличить скорость работы. Во избежании преждевременного рехэшинга необходимо использовать метод reserve(), позволяющий выполнять расчет необходимого количества сегментов в автоматическом режиме.

Ссылки
Литература
  1. Зайдельман Я. Н., Ройтенберг М. А. ИНформатика. Подготовка к ЕГЭ в 2014 году. Диагностические работы. - М: МЦНМО, 2014
  2. Сиддхартха Рао. Освой самостоятельно C++ за 21 день, 7-е изд. Вильямс, 2013
  3. Липпман Б. Стенли, Жози Лажойе, Барбара Э. Му. Язык программирования С++. Базовый курс. Изд. 5-е. М: ООО «И. Д. Вильямс», 2014
  4. Бьерн Страуструп. Язык программирования C++. Специальное издание. Пер. с англ. — Изд. Бином, 2011 г.
  5. Джосаттис Н.М. Стандартная библиотека C++. Справочное руководство. Вильямс, 2014


Comments are closed