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

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

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

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

Компоненты STL

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

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

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

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

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

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

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

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

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

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

ния. Контейнеры и алгоритмы унифицируются для произвольных типов и классов соответственно.

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

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

Контейнеры

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

Вектор

Множество

<---

--->

Список

Отображение

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

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

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