Алекс Jenter - Программирование на Visual C++. Архив рассылки

• Контейнер – это хранилище объектов (как встроенных, так и определённых пользователем типов). Простейшие виды контейнеров (статические и динамические массивы) встроены непосредственно в язык C++. Кроме того, стандартная библиотека включает в себя реализации таких контейнеров, как вектор (vector), список (list), очередь (deque), ассоциативный массив (map), множество (set), и некоторых других.

• Алгоритм – это функция для манипулирования объектами, содержащимися в контейнере. Типичные примеры алгоритмов – сортировка и поиск. В STL реализовано порядка 60 алгоритмов, которые можно применять к различным контейнерам, в том числе к массивам, встроенным в язык C++.

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

Рассмотрим эти концепции более подробно.

Итераторы используются для доступа к элементам контейнера так же, как указатели – для доступа к элементам обычного массива. Как мы знаем, в языке C++ над указателями можно выполнять следующий набор операций: разыменование, инкремент/декремент, сложение/вычитание и сравнение. Соответственно, любой итератор реализует все эти операции или некоторое их подмножество. Кроме того, некоторые итераторы позволяют работать с объектами в режиме "только чтение" или "только запись", тогда как другие предоставляют доступ и на чтение, и на запись. В зависимости от набора поддерживаемых операций различают 5 типов итераторов, которые приведены в следующей таблице.

Итератор с произвольным доступом реализует полный набор операций, применимых к обычным указателям.

Как мы уже знаем, контейнер предназначен для хранения объектов. Хотя внутреннее устройство контейнеров очень сильно различается, каждый контейнер обязан предоставить строго определённый интерфейс, через который с ним будут взаимодействовать алгоритмы. Этот интерфейс обеспечивают итераторы. Каждый контейнер обязан иметь соответствующий ему итератор (и только итератор). Важно подчеркнуть, что никакие дополнительные функции-члены для взаимодействия алгоритмов и контейнеров не используются. Это сделано потому, что стандартные алгоритмы должны работать в том числе со встроенными контейнерами языка C++, у которых есть итераторы (указатели), но нет ничего, кроме них. Таким образом при написании собственного контейнера реализация итератора – необходимый минимум.

Каждый контейнер реализует определённый тип итераторов. При этом выбирается наиболее функциональный тип итератора, который может быть эффективно реализован для данного контейнера. "Эффективно" означает, что скорость выполнения операций над итератором не должна зависеть от количества элементов в контейнере. Например, для вектора реализуется итератор с произвольным доступом, а для списка – двунаправленный. Поскольку скорость выполнения операции [] для списка линейно зависит от его длины, итератор с произвольным доступом для списка не реализуется.

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

Кроме обычных итераторов в STL существуют обратные итераторы (reverse iterator). Обратный итератор отличается тем, что просматривает последовательность элементов в контейнере в обратном порядке. Другими словами, операции + и – у него меняются местами. Это позволяет применять алгоритмы как к прямой, так и к обратной последовательности элементов. Например, с помощью функции find можно искать элементы как "с начала", так и "с конца" контейнера.