Библиотека стандартных шаблонов (stl)

Классы в С++ - прекрасный механизм для создания библиотеки структур данных. С помощью шаблонов классов реализованы специальные библиотеки. В составе С++ реализована встроенная библиотека стандартных шаблонов (STL – standard template library). В ней реализованы наиболее популярные структуры данных и алгоритмы работы с ними. Так как библиотека реализована на шаблонах, то структуры и алгоритмы, находящиеся в ней, применимы почти ко всем типам данных.

Три наиболее важных сущности STL:

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

• алгоритмы – функции для обработки данных, находящихся в контейнерах. В STL алгоритмы представлены в виде шаблонных функций. Но они не являются методами классов-контейнеров. Их можно использовать для обработки своих данных. Это независимые функции, их можно использовать и в массивах, и в собственных контейнерах.

• итераторы – это обобщение концепции указателей, они ссылаются на элементы контейнера. Их можно инкрементировать и они будут последовательно ссылаться на все элементы контейнера.

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

Контейнерcобъектами Алгоритмы Контейнерcобъектами

Контейнеры подразделяются:

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

=ассоциативные – имеют иную организацию данных. Доступ к данным выполняется с помощью ключа. Основой для ассоциативных контейнеров служат сбалансированные деревья поиска. К ассоциативным контейнерам относятся: словари (map), словари с дубликатами (multimap), множества (set), множества с дубликатами (multiset), битовые множества (bitset).Основные контейнерные классы с заголовочными файлами, где они определены:

описания	класс	заголовок
вектор	vector	<vector>
двунаправленный список	list	<list >
двусторонняя очередь	deque	< deque>
стек	stack	< stack>
очередь	queue	< queue>
очередь с приоритетами	priority_ queue	< queue>
словари	map	< map>
словари с дубликатами	multimap	< map>
множество	set	<set>
множество с дубликатами	multiset	<set>
множество битов	bitset	< bitset>