Каталог алгоритмов STL

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

Хотя во многих книгах при описании алгоритмов указывается полный синтаксис объявления щаблона, мы этого делать не будем. Предполагается, что вы уже достаточно хорощо разбираетесь в шаблонах, а смысл аргументов щаблона достаточно очевиден из объявлений функций. Необходимые типы итераторов описываются именами типов аргументов. Надеемся, в такой форме материал будет проще восприниматься, а полное описание при необходимости можно найти в заголовочном файле соответствующего щаблона.

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

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

Например, в реализации STLPort на базе SGI STL, которая входит в Borland С++ Builder версии 6 и в компилятор Digital Mars.

int mainO { const int SZ = 9: vector<string> vs(SZ); Заполнение вектора случайными строками: generateCvs.beginO. vs.endO. NumStringGenO): copy(vs.begin(). vs.endO.

ostream iterator<string>(cout. \t )): cout endl: vector<double> vd:

transform(vs.beginO. vs.endO. back inserter(vd).

compose(ptr fun(atof). mem fun ref(istring::c str))): copy(vd.begin(). vd.endO.

ostream iterator<double>(cout. \t )): cout endl: } /:-

Как и прежде, ключевое слово typename сообщает компилятору, что указанный член класса является вложенным типом.

В некоторых реализациях композиция объектов функций поддерживается как расщирение. Вероятно, комитет по стандартизации С++ включит поддержку этих возможностей в следующую версию стандарта С++.

Итераторы ввода (Inputlterator). Итератор ввода поддерживает только чтение элементов в прямом направлении (от начала к концу интервала) при помощи операторов ++ и *. Состояние итератора проверяется операторами == и !=.

Итераторы вывода (Outputlterator). Итератор вывода поддерживает только запись элементов в прямом направлении при помощи операторов ++ и *. С другой стороны, состояние итераторов вывода не может проверяться операторами == и !=; предполагается, что элементы просто передаются в приемник, и проверка конечного условия не обязательна. Другими словами, считается, что контейнер, на который ссылается Outputlterator, может принять бесконечное число объектов. Это необходимо для того, чтобы тип Outputlterator мог использоваться с потоками ostream (через ostreamjterator), но на практике также часто применяются итераторы вставки, вроде возвращаемых функцией backjnserter().

Невозможно определить, ссылаются ли разные итераторы ввода или вывода на один и тот же интервал, поэтому такие итераторы не могут использоваться совместно. Просто представьте себе поддержку потоков istream и ostream на уровне итераторов, и смысл итераторов Inputlterator и Outputlterator станет предельно ясен. Также стоит заметить, что Inputlterator и Outputlterator относятся к категории обобщенных итераторов. Другими словами, когда вы видите Inputlterator или Outputlterator в аргументах шаблонных алгоритмов STL, это означает, что вместо них можно подставить любой более сложный тип итератора.

Прямой итератор (Forwardlterator). Через итератор Inputlterator можно только читать, через итератор Outputlterator - только записывать, но ни один из них не позволяет одновременно читать и модифицировать интервал. Прямые итераторы снимают это ограничение; они по-прежнему позволяют перебирать элементы только в прямом направлении оператором ++, но при этом поддерживают как чтение, так и запись. Два прямых итератора, принадлежащих к одному интервалу, можно сравнить между собой. Так как прямые итераторы поддерживают чтение и запись, они могут использоваться вместо итераторов Inputlterator и Outputlterator.

Двусторонний итератор (Bidirectionallterator). Фактически двусторонний итератор представляет собой прямой итератор с возможностью перемещения в обратном направлении. Иначе говоря, Bidirectionallterator поддерживает все операции Forwardlterator, но при этом дополнительно поддерживает оператор -.

Итератор произвольного доступа (RandomAccessIterator). Итераторы произвольного доступа поддерживают все операции обычных указателей: сложение и вычитание целочисленных смещений для перехода вперед и назад на несколько позиций (вместо одной), индексирование оператором [], вычитание одного итератора из другого, сравнение итераторов операторами <, > и т. д. Если вы программируете процедуру сортировки или что-нибудь в этом роде, вам не удастся создать эффективный алгоритм без итераторов произвольного доступа.

Типы параметров шаблонов обозначаются одним из перечисленных имен итераторов (иногда с добавлением суффикса 1 или 2, чтобы было проше различать аргументы). В списке также могут присутствовать другие аргументы, как правило - объекты функцир!.

При описании групп элементов, передаваемых операции, часто применяется математическое обозначение интервалов. Квадратная скобка означает, что граница входит в интервал, а круглая скобка - что граница исключается из интервала. Интервал определяется двумя итераторами: первый указывает на начальный элемент, а второй - в позицию за концом интервала , то есть за последним элементом. Поскольку элемент за последним никогда не используется, такой интервал можно выразить в виде [firstlast), где first - итератор, указывающий на начальный элемент, а last - итератор, установленный в позицию за последним элементом.

В большинстве книг и описаний алгоритмов STL алгоритмы классифицируются по их побочным эффектам: неизменяющие алгоритмы оставляют элементы интервала в прежнем состоянии, изменяющие алгоритмы модифицируют их, и т. д. Такие описания базируются в основном на базовом поведении или реализации алгоритма, то есть подаются с точки зрения разработчика. На практике подобные классификации особой пользы не приносят, поэтому мы будем разделять алгоритмы в соответствии с решаемыми задачами. Что именно вы хотите сделать: найти элемент или набор элементов, выполнить операцию с каждым элементом, подсчитать элементы, заменить элементы и т. д.? Это поможет вам быстрее найти нужный алгоритм.

Если над объявлениями функций не указан другой заголовок (например, <utility> или <numeric>), функция объявляется в <algorithm>. Кроме того, все алгоритмы принадлежат пространству имен std.

Вспомогательные инструменты для создания примеров

Начнем с создания вспомогательных инструментов, которые будут использоваться для демонстрации работы алгоритмов. В следующих примерах задействованы генераторы, определенные ранее в файле Generators.h, а также представленные далее шаблоны.

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

: СОб:PrintSequence.h

Вывод содержимого любого интервала

fifndef PRINTSEQUENCE.H

fdefine PRINTSEQUENCEJ

find ude <algorithni>

findude <iostream>

findude <iterator>

tempiate<typename Iter>

void printCIter first. Iter last, const char* nm - , const char* sep - \n , std::ostream& os - std::cout) { if(nm !- 0 && *nm != \0) OS nm : sep: typedef typename