Начнем с простого примера, демонстрирующего некоторые алгоритмы STL и принципы их использования;

stl/algol.cpp #include <iostrea[n> include <vectQr> #1nclude <algorithm> using namespace std;

int mainO {

vector<int> coll; vector<int>::iteratQr pos;

Вставка элементов от 1 до 6 в произвольном порядке coll.push back(2) coll,push back(5) coll,push back(4) coll .push back(l) coll .push back(6) coll.push back(3)

Поиск и вывод минимального и максимального элементов

pos = min element (coll.beginO. coU.endO);

cout min: *pos endl;

pos = max element (coll.beginO. coll.endO):

cout max: *pos endl;

Сортировка всех элементов sort (coll.beginO. coll.endO):

Поиск первого элемента со значением, равным 3 pos = find (coll.beginO. coll.endO, Интервал 3): Значение

Перестановка найденного элемента со значением 3 и всех последующих элементов в обратном порядке, reverse (pos. coll .endO);

Вывод всех элементов

for (pos=coll .beginO; pos!=coll .endO; ++po5) { cout *pos :

cout endl;

Чтобы использовать алгоритмы в программе, необходимо включить в нее заголовочный файл <algorithm>:

Iinclude <algorithm>

Первые два алгоритма называются min element() и max element(). При вызов им передаются два параметра, определяющих интервал обрабатываемых элемен тов. Чтобы обработать все содержимое контейнера, просто используйте вызов! beginO и end(). Алгоритмы возвращают итераторы соответственно для миннмаль ного и максимального элементов. Таким образом, в показанной ниже команд алгоритм min element() возвращает позицию минимального элемента (если такн: элементов несколько, алгоритм возвращает позицию первого из них):

pos = [nin element (coll.beginC). coll.endO):

Следующая команда выводит найденный элемент: cout min: *pos endl:

Разумеется, поиск и вывод можно объединить в одну команду:

cout *[n1n element(coll .beginO.coll .endO.endO) endl;

Следующим вызывается алгоритм sort(). Как нетрудно догадаться по названию, этот алгоритм сортирует элементы в интервале, определяемом двумя аргументами. Как обычно, вы можете задать собственный критерий сортировки. По умолчанию сортировка осуществляется с использованием оператора <. Таким образом, следующая команда сортирует все элементы контейнера по возрастанию:

sort (coll .beginO. coll.endO):

В конце концов элементы вектора будут расположены в следующем порядке:

1 2 3 4 5 6

Алгоритм find() ищет значение в заданном интервале. В нашем примере во всем контейнере ищется первый элемент со значением 3:

pos = find (coll .beginO. coll.endO. Интервал 3): Значение

Если поиск оказался успешным, алгоритм find() возвращает итератор, установленный на первый найденный элемент. В случае неудачи возвращается итератор} для позиции за концом интервала, определяемым вторым переданным аргументом. В нашем примере значение 3 находится в третьем элементе, поэтому pos ссылается на третий элемент coll.

Последним вызывается алгоритм reverse(), который переставляет элементы переданного интервала в обратном порядке. В аргументах передается третий элемент, найденный алгоритмом find(), н конечный итератор:

reverse (pos. coll.endO);

В результате вызова переставляются элементы от третьего до последнего. Результат работы программы выглядит так:

min: 1 max: 6 1 2 6 5 4 3

Интервалы

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

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

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

[начало,конец) [начало.иоиеи1

В книге используется первый вариант.

Концепция полуоткрытых интервалов обладает рядом достоинств, упоминавшихся на с. 96 (эта концепция проста ц не требует специальной обработки пустых коллекций). Тем не менее у нее также есть недостатки. Рассмотрим следующий пример:

stl/findi.срр #1nclude <iostream> #include <list> Iinclude <algorithm> using namespace std:

int mainO {

list<int> coll; list<int>::iterator pos;

Вставка элементов от 20 до 40 for (int i=20: i<=40: ++i) { coll.pLJSh back(1):