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

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

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

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

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

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

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

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

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

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

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

Контейнеры

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

Вектор

Множество

<---

Список

Отображение

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

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

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

жит три стандартных класса последовательных контейнеров: vector (вектор), deque (дек) и list (список).

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

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

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

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

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

В STL поддерживаются следующие разновидности последовательных контейнеров: О векторы; О деки; О списки.

Библиотека NIHCL (National Institute of Healths Class Library) была одной нз первых библиотек классов, написанных на С++.