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

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

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

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

#include <set>

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

Класс 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, comp> ar(first, last, Сomp);

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

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

Деструктор (уничтожает объект класса 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.
Приведем пример задачи.
Программа 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

Какой можно из этого сделать вывод? Не стоит использовать множество (или мультимножество) для получения элементов из других последовательностей в цикле поэлементно (поскольку на каждом шаге производится автоматическая сортировка). Необходимо получать последовательность целиком при создании объекта 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

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

Ссылки


Print Friendly, PDF & Email

Comments are closed