Программирование на Visual C++. Архив рассылки
Шрифт:
Каждый контейнер реализует определённый тип итераторов. При этом выбирается наиболее функциональный тип итератора, который может быть эффективно реализован для данного контейнера. "Эффективно" означает, что скорость выполнения операций над итератором не должна зависеть от количества элементов в контейнере. Например, для вектора реализуется итератор с произвольным доступом, а для списка – двунаправленный. Поскольку скорость выполнения операции [] для списка линейно зависит от его длины, итератор с произвольным доступом для списка не реализуется.
Вне зависимости от фактической организации контейнера (вектор, список, дерево) хранящиеся в нём элементы можно рассматривать как последовательность. Итератор первого элемента
Кроме обычных итераторов в STL существуют обратные итераторы (reverse iterator). Обратный итератор отличается тем, что просматривает последовательность элементов в контейнере в обратном порядке. Другими словами, операции + и – у него меняются местами. Это позволяет применять алгоритмы как к прямой, так и к обратной последовательности элементов. Например, с помощью функции find можно искать элементы как "с начала", так и "с конца" контейнера.
Каждый класс контейнера, реализованный в STL, описывает набор типов, связанных с контейнером. При написании собственных контейнеров следует придерживаться этой же практики. Вот список наиболее важных типов:
• value_type — тип элемента
• size_type — тип для хранения числа элементов (обычно size_t)
• iterator — итератор для элементов контейнера
• key_type — тип ключа (в ассоциативном контейнере)
Помимо типов можно выделить набор функций, которые реализует почти каждый контейнер в STL. Они не требуются для взаимодействия с алгоритмами, но их реализация улучшает взаимозаменяемость контейнеров в прграмме. Если, к примеру, какой-то контейнер реализует набор характерных для списка функций, то его можно будет вставить в программу вместо списка, изменив в ней всего одну строчку. Список основных функций приведён в таблице.
| Функция | Описание |
|---|---|
| begin, end | Возвращают итераторы начала и конца прямой последовательности. |
| rbegin, rend | Возвращают итераторы начала и конца обратной последовательности. |
| front, back | Возвращают ссылки на первый и последний элемент, хранящийся в контейнере. |
| push_back, pop_back | Позволяют добавить или удалить последний элемент в последовательности. |
| push_front, pop_front | Позволяют добавить или удалить первый элемент в последовательности. |
| size | Возвращает количество элементов в контейнере. |
| empty | Проверяет, есть ли в контейнере элементы. |
| clear | Удаляет из контейнера все элементы. |
| insert, erase | Позволяют вставить или удалить элемент(ы) в середине последовательности. |
Мы уже установили две важные вещи. Во-первых, алгоритмы предназначены для манипулирования элементами контейнера. Во-вторых, любой алгоритм рассматривает содержимое контейнера как последовательность, задаваемую итераторами первого и следующего за последним элементов. Итераторы обеспечивают интерфейс между контейнерами и алгоритмами, благодаря чему и достигается гибкость и универсальность
Каждый алгоритм использует итераторы определённого типа. Например, алгоритм простого поиска (find) просматривает элементы подряд, пока нужный не будет найден. Для такой процедуры вполне достаточно итератора ввода. С другой стороны, алгоритм более быстрого двоичного поиска (binary_search) должен иметь возможность переходить к любому элементу последовательности, и поэтому требует итератора с произвольным доступом. Вполне естественно, что вместо менее функционального итератора можно передать алгоритму более функциональный, но не наоборот.
Все стандартные алгоритмы описаны в файле algorithm, в пространстве имён std.
Помимо уже рассмотренных элементов в STL есть ряд второстепенных понятий, с которыми следует познакомиться.
Аллокатор (allocator) – это объект, отвечающий за распределение памяти для элементов контейнера. С каждым стандартным контейнером связывается аллокатор (его тип передаётся как один из параметров шаблона). Если какому-то алгоритму требуется распределять память для элементов, он обязан делать это через аллокатор. В этом случае можно быть уверенным, что распределённые объекты будут уничтожены правильно.
В состав STL входит стандартный класс allocator (описан в файле xmemory). Именно его по умолчанию используют все контейнеры, реализованные в STL. Однако никто не мешает вам реализовать собственный. Необходимость в этом возникает очень редко, но иногда это можно сделать из соображений эффективности или в отладочных целях.
Многие алгоритмы получают в качестве параметра различные функции. Эти функции используются для сравнения элементов, их преобразования и т. д. Рассмотрим следующий шаблон функции.
Что такое CmpFn? Естественнее всего предположить, что это указатель на функцию. Однако вызов функции по указателю – операция довольно долгая. В нашем примере вызов займёт больше времени, чем выполнение всех остальных инструкций в функции max. Проблема в том, что при таком подходе к передаче функции её не удаётся объявить как встроенную (inline).
Вместо указателя на функцию можно передать в max объект любого класса с перегруженным оператором . При этом operator можно объявить как встроенный, что при большом количестве обращений к max даст очевидный выигрыш в производительности.
Таким образом, объекты-функции используются в целях оптимизации
Термин "предикат" довольно часто фигурирует в книгах по STL. В действительности предикат – это просто функция (в частности объект-функция), которая возвращает bool. Различают унарные и бинарные предикаты. Унарные получают один параметр, бинарные – два.
Предикаты широко используются в STL. Унарные предикаты используются для задания подмножества элементов контейнера, удовлетворяющих некоторому условию. Например, функция count_if считает количество элементов последовательности, для которых заданный унарный предикат возвращает true. Бинарные предикаты чаще всего используются для сравнения двух элементов.
Адаптер (adapter) – это класс, который не реализует собственную функциональность, а вместо этого предоставляет альтернативный интерфейс к функциональности другого класса.