Лекция 14. Библиотека STL

Библиотека стандартных шаблонов STL (Standard Template Library) — один из тех немногих программных продуктов, чье появление было встречено единодушно всеми профессиональными программистами.

Практически все современные компиляторы Cи++ содержат библиотеку STL. Изначально она настроена на работу практически с любыми данными, что обеспечивается набором шаблонов функций и классов.

Четыре основных компонента составляют структуру STL:

· итераторы — специальные указатели, позволяющие алгоритмам перемещаться по данным контейнера;

· алгоритмы — вычислительные процедуры;

· контейнеры — блоки хранения данных, управления ими и размещения;

· функциональные объекты — инкапсулируют функции в объекте для использования другими компонентами.

Итераторы

Итератор — это некий обобщенный указатель. Обычные указатели языка Cи++ являются частным случаем итераторов, позволяющих работать с различными структурами данных и типами универсальным способом. Любой алгоритм (универсальная вычислительная процедура), принимая в качестве параметров итераторы, при их обработке не задумывается о типе данных, на которые передаваемые итераторы ссылаются.

Итераторы бывают пяти видов:

· входные (input);

· выходные (output);

· однонаправленные (forward);

· двунаправленные (bidirectional);

· произвольного доступа (random access).

Входные итераторы служат для чтения адресуемых данных. Выходные, напротив, адресуют объекты, в которые данные должны быть записаны. Однонаправленные итераторы обладают всеми свойствами входных и выходных, а также могут перемещаться от начала последовательности адресуемых данных в конец. Что касается двунаправленных итераторов, то они не только обладают свойствами однонаправленных, но и способны перемещаться в любом направлении по цепочке данных: как вперед, так и назад. Итераторы произвольного доступа самые универсальные. Они обладают функциональностью всех четырех других итераторов. Кстати говоря, указатели языка Си++ также являются итераторами произвольного доступа.

Библиотека STL построена так, что итератор более старшего типа может быть подставлен вместо младшего. Так, итератор произвольного доступа может заменить двунаправленный, двунаправленный может быть подставлен вместо однонаправленного и т. д.

Применяя итераторы, важно учитывать такой элемент, как индикатор конца диапазона (end-of-range), т. е. элемент, идущий непосредственно за концом цепочки адресуемых итератором данных. Весьма похоже на схему адресации строк в языке Си++, когда признаком конца строки является символ '\0'. Но при работе с итераторами индикатором конца диапазона может быть любое число.

Алгоритмы

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

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

Первый параметр — входной итератор, указывающий на первую цепочку сравниваемых данных. Второй адресует индикатор конца диапазона данных. Третий параметр — вторая цепочка сравниваемых данных. А вот фрагмент сравнения двух векторов (массивов) v1 и v2:

Здесь использованы стандартные методы векторов: begin() возвращает итератор, настроенный на начало цепочки данных, а end() возвращает индикатор выхода за диапазон. Если все элементы векторов попарно равны друг другу, то equal вернет значение «истина» (true).

Отметим, что все алгоритмы можно разделить на две основных категории: те, которые изменяют данные, и те, которые их не изменяют.

Контейнеры

Библиотека STL имеет в своем арсенале элементы, называемые контейнерами. Контейнеры — это объекты, хранящие в себе другие объекты. В STL таких контейнеров десять:

vector —массив с произвольным доступом, чаще всего применяемый в тех случаях, когда надо последовательно добавлять данные в конец цепочки;

list —похож на вектор, но эффективен при добавлении и удалении данных в любое место цепочки;

deque —дек;

set —набор уникальных элементов, отсортированных в определенном порядке (множество);

multiset —то же, что и set, но может содержать повторяющиеся копии;

map —обеспечивает доступ к значениям по ключам;

multimap —то же, что и map, но допускающий повторяющиеся ключи;

stack —стек;

queue —очередь;

priority queue —приоритетная очередь.

Надо отметить, что все алгоритмы работают с методами контейнеров, не вдаваясь в детали их реализации. Так, если алгоритму нужно определить, равен ли один элемент из контейнера другому, он просто вызывает перегруженный оператор сравнения "operator = = ()", реализованный в контейнере.