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

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

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

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

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

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

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

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

Каждый класс контейнера, реализованный в STL, описывает набор типов, связанных с контейнером. При написании собственных контейнеров следует придерживаться этой же практики. Вот список наиболее важных типов:

• value_type — тип элемента

• size_type — тип для хранения числа элементов (обычно size_t)

• iterator — итератор для элементов контейнера

• key_type — тип ключа (в ассоциативном контейнере)

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

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

Каждый алгоритм использует итераторы определённого типа. Например, алгоритм простого поиска (find) просматривает элементы подряд, пока нужный не будет найден. Для такой процедуры вполне достаточно итератора ввода. С другой стороны, алгоритм более быстрого двоичного поиска (binary_search) должен иметь возможность переходить к любому элементу последовательности, и поэтому требует итератора с произвольным доступом. Вполне естественно, что вместо менее функционального итератора можно передать алгоритму более функциональный, но не наоборот.

Все стандартные алгоритмы описаны в файле algorithm, в пространстве имён std.

Помимо уже рассмотренных элементов в STL есть ряд второстепенных понятий, с которыми следует познакомиться.

Аллокатор (allocator) – это объект, отвечающий за распределение памяти для элементов контейнера. С каждым стандартным контейнером связывается аллокатор (его тип передаётся как один из параметров шаблона). Если какому-то алгоритму требуется распределять память для элементов, он обязан делать это через аллокатор. В этом случае можно быть уверенным, что распределённые объекты будут уничтожены правильно.