Использование стандартной библиотеки шаблонов

Стандартная библиотека шаблонов (STL) поддерживает большинство типовых операций со структурами данных.

В первую очередь нам понадобятся последовательные контейнеры vector, list и deque и их производные (адаптеры) stack и queue, а также ассоциативные контейнеры map, set, multimap, multiset.

Каждому контейнеру соответствует заголовочный файл, который нужно подключать директивой # include.

Контейнеры map и set хранят множества в виде дерева двоичного поиска с автобалансировкой (красно-чёрное дерево). Контейнер set хранит множество ключей, а map — пары < ключ, значение>, причём все ключи в них уникальны. Для множеств с повторениями используются контейнеры multimap и multiset. При просмотре всех этих контейнеров их содержимое выдаётся в виде упорядоченной последовательности (внутренний обход дерева двоичного поиска).

Современные системы программирования на С++ стали поддерживать и контейнеры с множествами в форме хеш-таблиц. Так, например, в библиотеке Visual C++ 2010 имеются контейнеры hash_map и hash_set. В стандарте C++11 эти контейнеры были узаконены под названиями unordered_map и unordered_set. В таком виде они поддерживаются в оболочке Visual C ++ 2012.

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

Подробнее см. [7], с. 295–368, [8], с. 623–702, [10], с. 835–962. Полезно также посмотреть библиотечные файлы в каталоге include компилятора C++: только там содержится исчерпывающая информация о том, какие на самом деле объявляются классы и какие функции-члены они содержат. Информация в литературных источниках, как правило, запаздывает и содержит неточности. Важно и то, что в сообщениях компилятора об ошибках обычно присутствует информация из текстов каталога include, поскольку эти тексты компилируются вместе с программой пользователя. Требуется также знакомство с механизмом шаблонов языка С++.

Практикум по теме

Переделать программу, составленную при выполнении темы «Последовательности», под использование контейнеров из стандартной библиотеки шаблонов.

6.2. Требования к отчёту

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

Контрольные вопросы

1. Что такое стандартный контейнер библиотеки STL? Чем он отличается от обычного объекта?

2. Какой стандартный контейнер можно считать наиболее подходящим для работы с множествами?

3. Можно ли использовать стандартные контейнеры для множеств, на которых не определено отношение полного порядка?

4. Существуют ли ограничения на применение стандартных алгоритмов двуместных операций над множествами в контейнерах?

5. Можно ли реализовать двуместную операцию над множествами в контейнерах без применения стандартного алгоритма?

6. Можно ли выполнять операции над последовательностями для множеств, хранящихся в стандартном контейнере?

7. Можно ли обеспечить поддержку произвольных последовательностей в контейнере для множеств?

8. Какова ожидаемая временная сложность при выполнении стандартным алгоритмом операции объединения двух множеств в стандартных контейнерах set?