Глава 3. Библиотека стандартных шаблонов (БСШ). Контейнеры

Рассказ о библиотеке стандартных шаблонов необходимо начать с признания того факта, что она представляет собой вершину искусства программирования и в ней используются самые изощренные свойства С++.

Герберт Шилдт. Самоучитель С++, стр. 419

При программировании задач разного типа наиболее распространенными структурами представления данных являются массивы, строки, списки, стеки, множества, деревья и т.д. С появлением технологии ООП, включая такие понятия как классы-шаблоны и функции-шаблоны, возникло желание стандартизировать часто используемые структуры данных – их хранение и обработку – создав набор стандартных классов. Идеология их создания претерпела несколько этапов.

1. Сначала была создана иерархия классов (около 22 классов), в основе которой лежал абстрактный класс Object. Однако применение этих классов оказалось сложным, т.к. их можно было использовать в основном для обработки данных этой же иерархии или порожденных из них. А, например, для применения класса Stack для целых чисел необходимо было из класса Object породить класс Integer, определив 5 виртуальных функций вспомогательного характера.

2. Затем на основе понятия класса-шаблона фирмой Borland была создана библиотека стандартных классов-шаблонов двух уровней FDS (векторы, списки) и ADT(стеки, очереди, множества).

3. С появлением версий языка C++ выше третьей, распространение получила библиотека STL (Standard Template Library), построенная на основе классов-шаблонов.

 

 

Контейнер. Структура БСШ.

 

Контейнерный класс – это класс-шаблон, в котором типы данных объявлены произвольными, а набор операций и функций над ними фиксирован. Таким образом, можно сказать, что контейнер – это объект, предназначенный для хранения и обработки других объектов. Ядро БСШ состоит из следующих основных компонент:

·  контейнеров,

· итераторов,

· алгоритмов,

· распределителей.

Контейнеры – это классы-шаблоны. Для каждого из классов определен набор конструкторов, деструкторы, характерные для класса операции и функции.

Итераторы – это объекты специальных классов, предназначенные для перебора объектов в контейнерах. По своей сути, итератор – это указатель на объекты контейнера. Для каждого класса-шаблона предназначен свой итератор. Действительно, алгоритмы перебора разных объектов отличаются: элементы массива выбираются обычно произвольно с помощью индекса (прямой доступ), а в связанном списке используется последовательный доступ по полю связи, например, p = p –> next. Итераторы позволяют перебирать элементы с начала контейнера или с конца (обратные итераторы).

Алгоритмы – это набор функций-шаблонов, выполняющих однотипную обработку объектов разных контейнеров. Например, сортировку (пирамидальную), слияние, бинарный поиск, поиск максимума и минимума, удаление элементов и т.д. (Всего 66 функций).

Распределители памяти – это объекты специального класса allocator, управляющие процессом выделения памяти для контейнеров.

Для использования того или иного контейнера, надо подключить соответствующую библиотеку.

Перечислим часто используемые контейнеры:

 

 

Контейнер	Назначение	Заголовочный файл
Degue	Двусторонняя очередь (дек)	<degue.h>
List	Линейный двунаправленный список	<list.h>
Queue	Очередь (удаление сначала, добавление – с конца)	<queue.h>
Set	Множество (элементы не повторяются)	<set.h>
Stack	Стек	<stack.h>
vector	Динамический массив	<vector.h>

 

В библиотеку входит также не контейнерный класс string. Для использования функций шаблонов библиотеки надо подключить заголовочный файл <algorithm.h>.

Ниже приведена структура библиотеки стандартных шаблонов БСШ: