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

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

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

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

#include <set>

Контейнеры set и multiset относятся к ассоциативным контейнерам (в библиотеке STD восемь контейнеров такого типа), которые хранят пары “ключ-значение”. Но, в отличие от других ассоциативных контейнеров, set и multiset хранят только ключи (set – уникальные ключи). Ключ – это объект определенного типа, в том числе абстрактного (для абстрактного типа должна быть определена соответствующая функция сравнения). Значение ключа является константным, т. е. изменять его нельзя (но можно удалить или вставить новый ключ). При добавлении элемента в контейнер он автоматически занимает необходимую позицию в упорядоченной совокупности других элементов. При вставке или удалении элементов множества итераторы, указывающие на элементы этого множества, остаются рабочими. Итераторы, используемые для set и multisetConstant bidirectional iterator (константный двусторонний итератор), нельзя передавать в функции библиотеки algorithm, которые не поддерживают данный тип итераторов. Следует использовать те методы работы с элементами массива (в замен обобщенным алгоритмам), которые определены в данном классе.

Классы set и multiset

Мультимножество multiset отличается от set только тем, что может хранить дубликаты ключей. Во всем остальном работа с multiset ничем не будет отличаться от работы с классом set.

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

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

Пустой массив

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

Конструктор копирования/перемещения

set<type, comp> ar(other);

С помощью итераторов (вставки)

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

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

set<type, comp> ar {init}; // или
set<type, comp> ar(init);  // или
set<type, comp> ar(init, Comp);

Здесь Comp - функция для сравнения ключей контейнера (необязательная). Помимо этого, конструктор включает необязательную функцию Allocator(), если разработчик определяет свою функцию аллокатора (опушена для простоты).

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

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

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

  • empty() Возвращает true, если set пуст
  • size() Возвращает количество элементов в set
  • max_size() Возвращает максимально возможное количество элементов
Модификаторы
  • clear() Очищает контейнер
  • insert() Вставляет элементы
  • erase() Удаляет элементы
  • swap() Обменивает содержимое
  • emplace() Создает элементы на месте
Методы поиска

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

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

Для контейнера set определены все операции сравнения. Все, что сказано об операциях сравнения для последовательных контейнеров, будет справедливо и для контейнера set.
Операцию "=" (operator=) можно использовать для получения множеством ar нового набора элементов, копированием другого множества other:

ar = other;

Также может использоваться семантика перемещения. Массив ar получит новый набор элементов, который будет перенесен из массива other. other не будет уничтожен, но его состояние будет не определено:

ar = std::move(other);

Приведем пример задачи.
Программа 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;
}

Мы уже сказали ранее, что множества не должны использоваться в алгоритмах в которых вставка и удаление элементов производится слишком часто. Сравним эффективность работы с вектором и множеством. Составим программу в которой осуществляется заполнение массивов множества и вектора случайными числами и производится поиск заданного значения.
Программа 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

Какой можно из этого сделать вывод? Использовать множество (или мультимножество) для получения элементов из других последовательностей в цикле поэлементно или производить частое удаление и вставку элементов будет неразумно. Необходимо получать уже сформированную последовательность целиком при создании объекта set или с помощью метода insert для существующего множества:

s.insert(first, last);

Однако, если в программе производится частый поиск элементов в массиве, то set здесь вне конкуренции.

Вспомогательный класс 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 (карта, словарь) реализован похожим образом, что и множества, на основе самобалансирующего дерева (красно-черное дерево). Главное отличие между множеством и словарем заключается в том, что массив map - это упорядоченный ассоциативный массив пар элементов, состоящих из ключей и соответствующих им значений. В map ключи уникальны, а multimap допускает дубликаты ключей. В словарях типы ключей и значений могут быть как одним из фундаментальных типов, так и абстрактным типом. Если тип ключа - абстрактный тип, то для него должна быть определена функция-компаратор (сравнения), определяющая направление сортировки. Ключ имеет константное значение, изменять значение ключа нельзя. Значение второго элемента пары (значение ключа) изменять можно.
Для начала работы с классами map (или multimap) необходимо подключить заголовок map (общий для обоих классов) следующей директивой:

#include <map>
Конструкторы

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

Пустой массив

map<Key, T, comp> ar; // или
map<Key, T, comp> ar(Comp);

Конструктор копирования/перемещения

map<Key, T, comp> ar(other);

С помощью итераторов (вставки)

map<Key, T, comp> ar(first, last); // или
map<Key, T, comp> ar(first, last, Сomp);

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

map<Key, T, comp> ar {init}; // или
map<Key, T, comp> ar(init);  // или
map<Key, T, comp> ar(init, Comp);

Примечание. При инициализации списком каждая пара должна заключаться в отдельные фигурные скобки:

map<string, int> ar {{"a1", 10}, {"www", 17}, {"j8", 100}};

Здесь Comp - функция для сравнения ключей контейнера (необязательная). Помимо этого, конструктор включает необязательную функцию Allocator(), если разработчик определяет свою функцию аллокатора (опушена для простоты).

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

ar.~map();
Методы словарей

Методы словарей общие с методами множеств, поэтому мы не будем здесь их повторять. Покажем работу этих методов на примере. Допустим, нам необходимо сформировать словарь который строится по следующему принципу: случайному ключу (строка) устанавливается случайное значение (целое число). Затем запрашивается вывод всех пар ключ => значение между ключами key1 и key2. В конце программы запрашивается вывод максимального значения для ключа key3 (см. комментарии в самой программе).
Программа 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;
}
Доступ к элементам

Для для доступа к элементам в словарях (помимо работы с итераторами) существует ещё два способа. Первый способ - использование уже знакомого нам метода at(key). Однако, в качестве аргумента он принимает не индекс, а значение ключа! Метод возвращает ссылку на соответствующее значение элемента с ключом, эквивалентным key. Если такого элемента не существует, то будет возвращено исключение out_of_range. Иначе говоря, проверяется: есть ли такой ключ в массиве?
Второй способ основан на использовании перегруженной операции []. Но использовать его нужно с осторожностью по следующей причине. Если ar[key] не существует, то в массив будет добавлен новый элемент с ключом key с использованием конструктора по умолчанию. В противном случае возвращается ссылка на элемент.
Примечание. Операцию "индексирования" можно использовать только с двумя типами ассоциативных классов контейнеров map и unordered_map.
Причины по которым добавлены эти методы разработчиками языка очевидны: код становится очень лаконичным и красивым. Поскольку at() возвращает исключение, то его можно обработать с помощью инструкций try - catch следующим образом:

try {
	users.at(U);
}
// Перехватываем исключение
catch (std::out_of_range) {
// И обрабатываем его
	users[U] = A;
}

Обработчики исключений мы рассмотрим позднее.
Если в словаре не будет найден ключ равный значению U, то операцией users[U] = A будет введен новый элемент массива.
"Фишка" в том, что операция индексирования возвращает L-значение, а это значит, что с помощью неё можно не только получать значение ключа, но и изменять это значение. Иными словами, такой код возможен:

users["ura"] = 42;
cout << users["ura"] << endl;
users["ura"] += 1;
cout << users["ura"] << endl;
--users["ura"];
cout << users["ura"] << endl;

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

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

В некоторых задачах автоматическая сортировка может рассматриваться как существенный недостаток, если накладные расходы по упорядочиванию элементов будут высоки. В этом случае заменой классов упорядоченных множеств и словарей могут стать классы неупорядоченных ассоциативных контейнеров (далее - неупорядоченные контейнеры) unordered_set, unordered_multiset, unordered_map и unordered_multimap. Операции поиска, вставки и удаления в неупорядоченных контейнерах имеют среднюю постоянную временную сложность (О(1)). Данные контейнеры вошли в стандарт начиная с C++11.
Неупорядоченные контейнеры реализованы в виде хеш-таблиц. Выполнение операции в хеш-таблице начинается с вычисления хеш-функции (хеширования) от ключа. Получающееся хеш-значение (также «хеш», «хеш-код») играет роль индекса в массиве. Хеш-таблица похожа на обычный словарь в котором литера может считаться хэш-значением.
Хеш-таблицы неупорядоченных контейнеров представляют собой массив ячеек, которые могут содержать неограниченное количество элементов. Такую ячейку мы будем называть сегментом. Фактически сегмент (с которым связан хеш) является связным списком. В программе 25.5 мы получим наглядное представление хеш-таблицы unordered_multiset.
Число хранимых элементов, делённое на размер массива (число возможных значений хеш-функции), называется коэффициентом заполнения хеш-таблицы (load factor) и является важным параметром, от которого зависит среднее время выполнения операций.
Для начала работы с классами unordered_set и unordered_multiset необходимо подключить заголовок unordered_set (общий для обоих классов) следующей директивой:

#include <unordered_set>

Аналогично, для классов unordered_map и unordered_multimap подключается заголовок:

#include <unordered_map>
Конструкторы

Типы неупорядоченных контейнеров включают в себя следующие шаблонные параметры:

  • const Key – тип ключа (unordered_set, unordered_multiset, unordered_map, unordered_multimap)
  • T – тип значения (unordered_map, unordered_multimap)
  • alloc – функция аллокатора (необязательно)
  • size_type bucket_count – минимальное количество сегментов для использования при инициализации (если не указан, определяется реализацией значением по умолчанию)
  • hash – хэш-функция (не обязательно)
  • equal – Функция сравнения, используемая для сравнения ключей (необязательно)
Объекты классов unordered_set и unordered_map можно получить с помощью следующих конструкторов:

Пустой массив

unordered_set<Key> ar;
unordered_set<Key, hash, equal> ar;
unordered_map<Key, T> ar;
unordered_map<Key, T, hash, equal> ar;

Примечание. Если хеш-функция hash опущена, то предполагается, что используется хеш-функция по умолчанию hash<key_type>. Если опущена функция сравнения equal, то предполагается, что используется equal_to<> (operator==). Для простоты Allocator() и bucket_count опущены.

Конструктор копирования/перемещения

unordered_set<Key> ar(other);
unordered_map<Key, T> ar(other);

С помощью итераторов (вставки)

unordered_set<Key> ar(first, last);
unordered_set<Key, hash, equal> ar(first, last);
unordered_map<Key, T> ar(first, last);
unordered_map<Key, T, hash, equal> ar(first, last);

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

unordered_set<Key> ar {init}; 
unordered_set<Key> ar(init); 
unordered_set<Key, hash, equal> ar(init); 
unordered_map<Key, T> ar {init}; 
unordered_map<Key, T> ar(init);
unordered_map<Key, T, hash, equal> ar(init);

Деструктор (уничтожает объекты классов unordered_set и unordered_map)

ar.~unordered_set();
ar.~unordered_map();
Методы, которые не поддерживаются

Неупорядоченные контейнеры и их упорядоченные аналоги имеют общие методы за исключением следующих, которые не поддерживаются:

  • Операции сравнения >, <, >=, <= (поддерживаются только == и !=)
  • lower_bound и upper_bound
  • Реверсивные итераторы: rbegin, crbegin, rend, crend

Методы неупорядоченных контейнеров

Политика хеширования

Данные методы позволяют управлять производительностью неупорядоченных контейнеров.

  • load_factor() – возвращает коэффициент заполнения (см. выше)
  • max_load_factor() – если используется без аргумента, то возвращает тип float коэффициент максимального заполнения, если использует в качестве аргумента тип float, то устанавливает коэффициент максимального заполнения. Контейнер может автоматически увеличить количество сегментов, если коэффициент заполнения превышает этот порог.
  • rehash(size_type count) – производит рехешинг контейнера так, чтобы количество сегментов (backet_count) было backet_count >= count и backet_count > size/max_load_factor
  • reserve(size_type count) – устанавливает количество сегментов к числу необходимого для размещения по крайней мере count элементов без превышения коэффициента максимального заполнения и рехешинга контейнера, т. е. помещает элементы в соответствующие сегменты, учитывая, что общее количество сегментов изменилось.
Примечание. Для достижения максимальной эффективности всегда следует задавать коэффициент максимального заполнения явно. Рекомендуемые значения находятся в интервале от 0.7 до 0.8. В программе 25.5 производятся замеры производительности поиска элемента при значениях коэффициента максимального заполнения по умолчанию (равен 1.0) и установленного разработчиком равным 0.7.
Примечание. Повысить производительность контейнера может собственно разработанная хеш-функция, но эта тема выходит за рамки нашего курса.

Интерфейс сегментов

Для непосредственной работы с элементами сегмента (как связного списка) используются следующие методы:

  • begin(), end(), cbegin(), cend() – итераторы. Обращаю внимание, что это именно итераторы по сегменту, а не по массиву в целом! Для контейнера также определены аналогичные итераторы.
  • size_type bucket_count() – возвращает количество сегментов в массиве
  • size_type max_bucket_count() – максимально возможное количество сегментов (связанное с ограничениями в реализации или системы)
  • size_type bucket_size(size_type n) – количество элементов в сегменте с индексом n
  • size_type bucket(Key) – возвращает индекс сегмента по ключу
С помощью этих методов мы можем создать наглядное представление хеш-массива. Вывод результатов работы программы спрятан под спойлер ниже.
Программа 25.5

#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;
	size_t n = 200;
	unm.reserve(n);
	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;
}
Вывод Программы 25.5
Количество сегментов в контейнере: 211
Коэффициент максимального заполнения: 1
Первый замер => 596
Количество сегментов в контейнере: 293
Коэффициент максимального заполнения: 0.7
Второй замер => 215
Структура хэша
Сегмент № 0 => 293 586
Сегмент № 1 => 880 294
Сегмент № 2 =>
Сегмент № 3 => 589 882
Сегмент № 4 => 297
Сегмент № 5 =>
Сегмент № 6 =>
Сегмент № 7 =>
Сегмент № 8 => 594
Сегмент № 9 =>
Сегмент № 10 => 889 303
Сегмент № 11 =>
Сегмент № 12 => 305
Сегмент № 13 => 599
Сегмент № 14 => 307 307
Сегмент № 15 => 601
Сегмент № 16 =>
Сегмент № 17 =>
Сегмент № 18 =>
Сегмент № 19 =>
Сегмент № 20 =>
Сегмент № 21 => 314
Сегмент № 22 =>
Сегмент № 23 => 316
Сегмент № 24 => 317 610
Сегмент № 25 =>
Сегмент № 26 => 905 319
Сегмент № 27 => 906
Сегмент № 28 =>
Сегмент № 29 => 908
Сегмент № 30 =>
Сегмент № 31 => 617
Сегмент № 32 =>
Сегмент № 33 => 326 619
Сегмент № 34 =>
Сегмент № 35 =>
Сегмент № 36 => 622
Сегмент № 37 => 330 330
Сегмент № 38 => 917
Сегмент № 39 => 625
Сегмент № 40 => 626
Сегмент № 41 => 920 627
Сегмент № 42 => 921
Сегмент № 43 =>
Сегмент № 44 => 923 630
Сегмент № 45 =>
Сегмент № 46 => 632 925
Сегмент № 47 =>
Сегмент № 48 =>
Сегмент № 49 => 635 928
Сегмент № 50 => 636
Сегмент № 51 =>
Сегмент № 52 =>
Сегмент № 53 =>
Сегмент № 54 => 347
Сегмент № 55 => 934 934
Сегмент № 56 =>
Сегмент № 57 => 643
Сегмент № 58 =>
Сегмент № 59 =>
Сегмент № 60 => 646
Сегмент № 61 =>
Сегмент № 62 => 941 941
Сегмент № 63 =>
Сегмент № 64 =>
Сегмент № 65 => 651 651
Сегмент № 66 =>
Сегмент № 67 => 946 946
Сегмент № 68 => 654 654
Сегмент № 69 =>
Сегмент № 70 =>
Сегмент № 71 =>
Сегмент № 72 => 365
Сегмент № 73 =>
Сегмент № 74 => 953 953
Сегмент № 75 => 368
Сегмент № 76 =>
Сегмент № 77 =>
Сегмент № 78 =>
Сегмент № 79 =>
Сегмент № 80 =>
Сегмент № 81 =>
Сегмент № 82 =>
Сегмент № 83 =>
Сегмент № 84 =>
Сегмент № 85 => 378 671
Сегмент № 86 =>
Сегмент № 87 => 673
Сегмент № 88 =>
Сегмент № 89 => 968 382
Сегмент № 90 => 676
Сегмент № 91 =>
Сегмент № 92 =>
Сегмент № 93 =>
Сегмент № 94 => 387
Сегмент № 95 =>
Сегмент № 96 =>
Сегмент № 97 =>
Сегмент № 98 =>
Сегмент № 99 => 978 685
Сегмент №100 => 686 686
Сегмент №101 => 394
Сегмент №102 => 102 102 981 981
Сегмент №103 =>
Сегмент №104 =>
Сегмент №105 => 984 105
Сегмент №106 => 985
Сегмент №107 =>
Сегмент №108 => 694 108
Сегмент №109 =>
Сегмент №110 =>
Сегмент №111 => 697
Сегмент №112 => 698 405 405
Сегмент №113 => 699
Сегмент №114 => 700 114
Сегмент №115 =>
Сегмент №116 =>
Сегмент №117 => 410 410 996 117
Сегмент №118 => 997
Сегмент №119 => 705
Сегмент №120 => 999 706 413
Сегмент №121 =>
Сегмент №122 =>
Сегмент №123 =>
Сегмент №124 =>
Сегмент №125 => 125
Сегмент №126 =>
Сегмент №127 => 713
Сегмент №128 =>
Сегмент №129 =>
Сегмент №130 =>
Сегмент №131 => 131
Сегмент №132 => 718
Сегмент №133 =>
Сегмент №134 => 134
Сегмент №135 => 428 135
Сегмент №136 =>
Сегмент №137 =>
Сегмент №138 =>
Сегмент №139 =>
Сегмент №140 => 726
Сегмент №141 =>
Сегмент №142 =>
Сегмент №143 => 143 143
Сегмент №144 => 437
Сегмент №145 => 438 438 145
Сегмент №146 =>
Сегмент №147 =>
Сегмент №148 =>
Сегмент №149 => 735
Сегмент №150 =>
Сегмент №151 =>
Сегмент №152 =>
Сегмент №153 => 153
Сегмент №154 => 154 447
Сегмент №155 =>
Сегмент №156 =>
Сегмент №157 =>
Сегмент №158 => 451
Сегмент №159 => 745
Сегмент №160 =>
Сегмент №161 => 454 161
Сегмент №162 =>
Сегмент №163 => 456
Сегмент №164 => 457
Сегмент №165 => 751
Сегмент №166 => 752 752 752 166 459
Сегмент №167 => 167
Сегмент №168 => 168
Сегмент №169 => 755
Сегмент №170 => 463
Сегмент №171 => 757 171
Сегмент №172 =>
Сегмент №173 =>
Сегмент №174 =>
Сегмент №175 => 468
Сегмент №176 =>
Сегмент №177 => 177
Сегмент №178 =>
Сегмент №179 =>
Сегмент №180 => 473
Сегмент №181 =>
Сегмент №182 => 475
Сегмент №183 =>
Сегмент №184 => 477
Сегмент №185 =>
Сегмент №186 => 479
Сегмент №187 =>
Сегмент №188 =>
Сегмент №189 => 482
Сегмент №190 => 776
Сегмент №191 =>
Сегмент №192 =>
Сегмент №193 =>
Сегмент №194 =>
Сегмент №195 => 781
Сегмент №196 =>
Сегмент №197 =>
Сегмент №198 =>
Сегмент №199 => 199 492 785
Сегмент №200 =>
Сегмент №201 => 494 494
Сегмент №202 => 788 495
Сегмент №203 => 203
Сегмент №204 => 204
Сегмент №205 => 205 791
Сегмент №206 =>
Сегмент №207 =>
Сегмент №208 =>
Сегмент №209 =>
Сегмент №210 => 210
Сегмент №211 =>
Сегмент №212 => 212
Сегмент №213 =>
Сегмент №214 =>
Сегмент №215 =>
Сегмент №216 => 802 802
Сегмент №217 => 510 217 803 803
Сегмент №218 =>
Сегмент №219 =>
Сегмент №220 => 513 806
Сегмент №221 => 807
Сегмент №222 => 808
Сегмент №223 =>
Сегмент №224 => 810
Сегмент №225 => 518
Сегмент №226 => 226
Сегмент №227 =>
Сегмент №228 =>
Сегмент №229 =>
Сегмент №230 => 523
Сегмент №231 => 524 231 817
Сегмент №232 =>
Сегмент №233 => 819 819
Сегмент №234 => 527
Сегмент №235 => 235
Сегмент №236 => 236
Сегмент №237 =>
Сегмент №238 =>
Сегмент №239 => 239
Сегмент №240 => 826
Сегмент №241 =>
Сегмент №242 =>
Сегмент №243 => 829
Сегмент №244 => 537 537
Сегмент №245 =>
Сегмент №246 => 539
Сегмент №247 => 247
Сегмент №248 =>
Сегмент №249 => 542
Сегмент №250 => 543
Сегмент №251 => 837
Сегмент №252 => 545
Сегмент №253 =>
Сегмент №254 =>
Сегмент №255 =>
Сегмент №256 =>
Сегмент №257 =>
Сегмент №258 =>
Сегмент №259 =>
Сегмент №260 =>
Сегмент №261 =>
Сегмент №262 => 848
Сегмент №263 =>
Сегмент №264 =>
Сегмент №265 =>
Сегмент №266 =>
Сегмент №267 =>
Сегмент №268 =>
Сегмент №269 =>
Сегмент №270 => 563
Сегмент №271 => 857 564
Сегмент №272 => 272
Сегмент №273 => 273 859
Сегмент №274 => 274
Сегмент №275 =>
Сегмент №276 =>
Сегмент №277 =>
Сегмент №278 =>
Сегмент №279 =>
Сегмент №280 =>
Сегмент №281 => 281
Сегмент №282 => 575
Сегмент №283 =>
Сегмент №284 => 577
Сегмент №285 =>
Сегмент №286 =>
Сегмент №287 =>
Сегмент №288 =>
Сегмент №289 => 289 289
Сегмент №290 =>
Сегмент №291 =>
Сегмент №292 =>
Программа показала, что изменяя значение коэффициента максимального заполнения можно добиться увеличение производительности в два раза!

Выводы

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

Ссылки


Print Friendly, PDF & Email

Comments are closed.