// Заполнение списка

...

bubble_sort(l.begin(), l.end(), less<int>()); // сортировать по убыванию

bubble_sort(l.begin(), l.end(), greater<int>()); // сортировать по возрастанию

В примере для указания порядка сортировки используются функторы less и greater. Более подробно функторы STL будут рассмотрены далее.

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

operator+ (int)

operator+= (int)

Operator- (int)

operator-= (int)

Operator- (random access iterator) operator[] (int)

operator < (random access iterator)

operator > (random access iterator)

operator >= (random access iterator)

operator <= (random access iterator)

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

Итераторы произвольного доступа широко применяются в алгоритмах поиска и сортировки. Примером такого алгоритма является бинарный поиск, реализованный следующим шаблоном:

template<class RandomAccessIterator, class T>

RandomAccessIterator binary_search(

RandomAccessIterator first,

RandomAccessIterator last,

const T& value)

{

RandomAccessIterator not_found = last, mid;

while(first != last) {

mid = first + (last - first) / 2;

if (value == *mid) return mid;

if (value < *mid) last = mid; else first = mid + 1;

}

return not_found;

}

При использовании итераторов часто возникает необходимость выяснить, к какой категории относится итератор (например, для выбора наиболее эффективного алгоритма). Эту задачу решают так называемые флаги итераторов (iterator tags).

В STL определены следующие пять таких флагов: input_iterator_tag; output_iterator_tag; forward_iterator_tag; bidirectional_iterator_tag; random_access_iterator_tag. Определяются эти флаги через соответствующие классы с одним пустым конструктором по умолчанию. Ниже приведен класс, определяющий input_iterator_tag (остальные классы аналогичны).

struct input_iterator_tag

{

input_iterator_tag() { ; }

};

Для получения флага итератора используется шаблон-функция iterator_category, которая просто осуществляет вызов конструктора нужного флага итератора. Рассматриваемая функция перегружена и выбор ее варианта осуществляется по типу итератора через параметр. Определение шаблона iterator_category для категории входных итераторов имеет вид:

template <class T, class Distance>

inline input_iterator_tag

iterator_category ( const input_iterator<T, Distance> & )

{

return input_iterator_tag();

}

Пример практического применения флага итератора содержится в следующем фрагменте:

template<class BidirectionalIterator, class T>

inline BidirectionalIterator binary_search (

BidirectionalIterator first, BidirectionalIterator last, const T & value)

{

binary_search(first, last, value, iterator_category(first));

}

В примере приведена функция, реализующая вызов стандартного алгоритма бинарного поиска. Выбор алгоритма в ней осуществляется по категории итератора (четвертый параметр). Если категория итератора есть random_access_iterator, то используется обобщенный алгоритм бинарного поиска; если же категория bidirectional_iterator, то выбирается наиболее эффективный частный алгоритм.

9.4. Алгоритмы

Алгоритмы в STL являются базовыми компонентами, которые производят обобщенные вычисления над контейнерами. Все алгоритмы определяются в виде соответствующих шаблонов функций (или классов) и содержатся в заголовочном файле algorith.h. В зависимости от структуры и характера воздействия на контейнеры выделяются четыре класса алгоритмов:

1. сохраняющие константность последовательные алгоритмы;

2. модифицирующие последовательные алгоритмы;

3. сортирующие алгоритмы;

4. обобщенные численные алгоритмы.

Алгоритмы первого класса не изменяют содержимого контейнеров и обеспечивают последовательную обработку их элементов. Примером алгоритма данного класса является find, который предназначен для поиска значения (объекта) в контейнере. Заголовок шаблона, представляющего рассматриваемый алгоритм, имеет вид.

template <class InputIterator, class T>