12. Обобщенные алгоритмы

В нашу реализацию класса Array (см. главу 2) м1 включили функции-члены для поддержки операций min() , max() и sort() . Однако в стандартном классе vector эти, на первый взгляд фундаментальные, операции отсутствуют. Для нахождения минимального или максимального значения элементов вектора следует вызвать один из обобщенных алгоритмов. Алгоритмами они называются потому, что реализуют такие распространенные операции, как min() , max() , find() и sort() , а обобщенными (generic) - потому, что применима: к различным контейнерным типам: векторам, спискам, массивам. Контейнер связывается с применяемым к нему обобщенным алгоритмом посредством пары итераторов (мы говорили о них в разделе 6.5), указывающих, какие элементы следует посетить при обходе контейнера. Специальн1е объекты-функции позволяют переопределить семантику операторов в обобщенных алгоритмах. Итак, в этой главе рассматриваются обобщенные алгоритмы, объекты-функции и итераторы.

12.1. Краткий обзор

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

1. По очереди исследовать каждый элемент.

2. Если элемент равен искомому значению, то вернуть его позицию в коллекции.

3. В противном случае анализировать следующий элемент Повторять шаг 2, пока значение не будет найдено либо пока не будет просмотрена вся коллекция.

4. Если мы достигли конца коллекции и не нашли искомого, то вернуть некоторое значение, показывающее, что нужного элемента нет.

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

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

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

некоторый обобщенный тип для представления позиции элемента внутри контейнера и специального признака на случай, если элемент не найден. Обычно мы возвращаем индекс элемента либо указатель на него. В ситуации, когда поиск неудачен, возвращается -1 вместо индекса или 0 вместо указателя.

template < class Forwardlterator, class Type > Forwardlterator

find( Forwardlterator first, Forwardlterator last, Type value ) {

for ( ; first != last; ++first ) if ( value == *first ) return first; return last;

оператор сравнения для типов хранимых в контейнере элементов:

ForwardIterator (однонаправленный итератор) - это один из пяти категорий итераторов, предопределенных в стандартной библиотеке. Он поддерживает чтение и запись адресуемого элемента. (Все пять категорий рассматриваются в разделе 12.4.)

Алгоритме! достигают независимости от типов за счет того, что никогда не обращаются к элементам контейнера непосредственно; доступ и обход элементов осуществляются только с помощью итераторов. Неизвестны ни фактический тип контейнера, ни даже то, является ли он контейнером или встроенным массивом. Для работы со встроенным типом массива обобщенному алгоритму можно передать не только обычные указатели, но и итераторы. Например, алгоритм find() для встроенного массива элементов типа int можно использовать так:

Обобщенные алгоритмы решают первую проблему, обход контейнера, с помощью абстракции итератора - обобщенного указателя, поддерживающего оператор инкремента для доступа к следующему элементу, оператор разыменования для получения его значения и операторы равенства и неравенства для определения того, совпадают ли два итератора. Диапазон, к которому применяется алгоритм, помечается парой итераторов: first адресует первый элемент, а last - тот, который следует за последним. К самому элементу, адресованному итератором last, алгоритм не применяется; он служит стражем, прекращающим обход. Кроме того, last используется как возвращаемое значение с семантикой отсутствует . Если же значение получено, то возвращается итератор, помечающий позицию найденного элемента.

Имеется по две версии каждого обобщенного алгоритма: в одной для сравнения применяется оператор равенства, а в другой - объект-функция или указатель на функцию, реализующую сравнение. (Объекты-функции рассматриваются в разделе 12.3.) Вот, например, реализация обобщенного алгоритма find() , в котором используется

#include <algoritm> #include <iostream>

int main() {

int search value;

int ia[ 6 ] = { 27, 210, 12, 47, 109, 83 };

cout << enter search value: ; cin >> search value;

int *presult = find( &ia[0], &ia[6], search value );

cout << The value << search value << ( presult == &ia[6]

? is not present : is present )

<< endl;

Если возвращенный указатель равен адресу &ia[6] (который расположен за последним элементом массива), то поиск оказался безрезультатным, в противном случае значение найдено.

Вообще говоря, при передаче адресов элементов массива обобщенному алгоритму мы можем написать

int *presult = find( &ia[0], &ia[6], search value );

int *presult = find( ia, ia+6, search value );

Если бы мы хотели ограничиться лишь отрезком массива, то достаточно было бы модифицировать передаваем1е алгоритму адреса. Так, при следующем обращении к find() просматриваются только второй и третий элементы (напомним, что элементы

искать только среди элементов ia[1] и ia[2]

массива нумеруются с нуля):

int *presult = find( &ia[1], &ia[3], search value );

А вот пример использования контейнера типа vector с алгоритмом find():