Назначение и архитектура STL

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

В состав STL входят шесть видов компонент: контейнеры, алгоритмы, итераторы, функторы, адаптеры и аллокаторы. Основными из них являются первые три. Контейнеры – это обобщенные (параметризованные) структуры данных, способные хранить и управлять процессом хранения других объектов. Алгоритмы в терминологии STL – это обобщенные вычислительные процедуры, обеспечивающие обработку данных контейнеров различных видов. Итераторы представляют собой абстрактные объекты, позволяющие перемещаться между элементами контейнеров унифицированным способом. Взаимодействие контейнеров, алгоритмов и итераторов можно представлять так, как показано на рисунке 8.

Рис. 8

Последовательные контейнеры

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

К числу последовательных контейнеров относятся векторы (vector), связные списки (linked list), а также двухсторонние очереди (deque – double ended queue).

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

template <class T, template <class U> class Allocator = allocator>

class vector {

...

};

Первый параметр T определяет тип элементов вектора, а второй параметр Allocator инкапсулирует модель памяти программы (использование этого параметра позволяет исключить необходимость изменения реализации вектора при переходе к новой модели памяти).

Чтобы создать вектор в программе, достаточно записать, например:

vector<float> v; // “пустой” вектор

vector<float> w(10); // вектор из 10 нулевых элементов

vector<float> x(5, 3.25); // вектор вида (3.25,3.25,3.25,3.25,3.25)

В результате компилятор инстанцирует класс vector<float>, а при выполнении программы происходит вызов конструктора, который формирует объекты v, w, x класса vector<float>. В дальнейшем в вектор v (или w, или x) можно будет добавить элементы типа float, удалить их, вывести содержимое вектора в поток, определить его длину и т.д. Все эти действия инкапсулированы в классе vector<float>. Например, для определения текущей длины вектора можно использовать компонентную функцию size, вставка элемента в конец вектора выполняется функцией push_back, обращение к заданному элементу осуществляется через операцию operator[], первый и последний элементы возвращаются функциями front и back соответственно, «пустота» вектора проверяется функцией empty.

Названные выше и некоторые другие функции сосредоточены внутри шаблона vector (список его функций можно получить из файла vector.h, где определен этот шаблон); кроме них, вектор могут обрабатывать и глобальные функции, реализующие алгоритмы STL. Однако, для доступа к вектору они должны взаимодействовать с итераторами. Итераторы по сути обобщают понятие указателя и ассоциируются с каждым контейнером, включая и вектор.

В шаблоне vector (и других шаблонах контейнеров) имеются две специальные функции, играющие особую роль для алгоритмов STL. Это функции begin и end. Обе они возвращают итераторы, при этом итератор, возвращаемый функцией begin, указывает на первый элемент вектора, а итератор, возвращаемый функцией end, ссылается за последний элемент вектора (его называют past-the-end-итератором). Вместе указанные итераторы образуют открытый справа диапазон, в котором могут работать алгоритмы. Графически это можно представить так, как показано на рисунке 9.

Рис. 9

Пример

vector<int> v(3);

v[0] = 5;

v[1] = 2;

v[2] = 7;

// определение итераторов

vector<int>::iterator first = v.begin();

vector<int>::iterator last = v.end();