Стандартная библиотека шаблонов (STL)

 

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

С точки зрения программиста, STL содержит подборку различных типов коллекций для различных целей, а также поддерживает ряд алгоритмов для работа с этими коллекциями. Эти коллекции являются разновидностями реализации динамического массива (вектор, дек), линейного списка (список) и бинарного дерева (множество, отображение, мультиотображение). Все компоненты STL оформлены в виде шаблонов и поэтому могут использоваться с произвольными тирами элементов.

 

 

Компоненты STL

Работа STL основана на взаимодействии разных структурных компонентов, среди которых центральное место занимают контейнеры, итераторы и алгоритмы.

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

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

Интерфейс итераторов имеет много общего с интерфейсом обычных указателей. Увеличение итератора производится оператором ++, а для обращения к значению, на которое ссылается оператор, используется оператор *. Таким образом, итератор можно рассматривать как своего рода умный указатель, который преобразует команду «перейти к следующему элементу» в конкретные действия, необходимые для конкретного типа контейнера.

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

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

Концепция STL основана на разделении данных и операций. Данные находятся под управлением контейнерных классов, а операции определяются адаптируемыми алгоритмами. Итераторы выполняют функции "клея", связывающего эти два компонента. Благодаря им любой алгоритм может работать с любым контейнером (рис. 9.1).

 

Рис. 9.1. Компоненты STL

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

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

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

 

 

Контейнеры

Контёйнерные классы (или проще — контейнеры) управляют коллекциями элементов. Для разных потребностей программиста в STL предусмотрены разные типы контейнеров (рис, 9.2).

 

Рис. 9.2. Типы контейнеров STL

 

Контейнеры делятся на две категории.

Последовательные контейнеры представляют собой упорядоченные коллекции, в которых каждый элемент занимает определенную позицию. Позиция зависит от времени и места вставки, но не связана со значением элемента. Например, если последовательно присоединить шесть элементов к концу существующей коллекции, эти элементы будут следовать в порядке их занесения. STL содержит три стандартных класса последовательных контейнеров: vector (вектор), deque (дек) и list (список).

Ассоциативные контейнеры представляют собой отсортированные коллекции, в которых позиция элемента зависит от его значения по определенному критерию сортировки. После занесения шести элементов в коллекцию порядок их следования будет определяться только их значениями. Последовательность вставки значения не имеет. STL содержит три стандартных класса ассоциативных контейнеров: set (множество), mullet (мультимножество), mар (отображение) и multimap (мультиотображение).

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

Автоматическая сортировка элементов в ассоциативных контейнерах не означает, что эти контейнеры специально предназначены для сортировки элементов. С таким же успехом можно отсортировать элементы последовательного контейнера. Основным достоинством автоматической сортировки является более высокая эффективность поиска. В частности, программист всегда может воспользоваться двоичным поиском, для которого характерна логарифмическая, а не линейная сложность. Таким образом, автоматическая сортировка является только (полезным) «побочным эффектом» реализации ассоциативного контейнера, спроектированного с расчетом на повышение эффективности.