21. Обобщенные алгоритмы в алфавитном порядке

21. Обобщенные алгоритмы в алфавитном порядке

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

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

// следует читать: включая first и все последующие

// элементы до last, но не включая сам last

[ first, last )

Это означает, что диапазон начинается с first и заканчивается last, однако сам элемент last не включается. Если

first == last

то говорят, что диапазон пуст.

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

В объявлении каждого алгоритма подразумевается минимальная поддержка, которую должны обеспечить итераторы (краткое обсуждение пяти категорий итераторов см. в разделе 12.4). Например, алгоритм find(), реализующий однопроходный обход контейнера и выполняющий только чтение, требует итератора чтения InputIterator. Ему также можно передать одно- или двунаправленный итератор или итератор с произвольным доступом. Однако передача итератора записи приведет к ошибке. Не гарантируется, что подобные ошибки (при передаче итератора неподходящей категории) будут обнаружены компилятором, поскольку категории итераторов - это не сами типы, а лишь параметры, которыми конкретизируется шаблон функции.

Некоторые алгоритмы существуют в нескольких вариантах: в одном используется тот или иной встроенный оператор, а в другом - объект-функция или указатель на функцию, реализующие альтернативу этому оператору. Например, алгоритм unique() по умолчанию сравнивает соседние элементы контейнера с помощью оператора равенства, определенного в классе, к которому данные элементы принадлежат. Но если в этом классе нет оператора равенства или мы хотим сравнивать элементы иным способом, то можем передать объект-функцию или указатель на функцию, поддерживающую нужную семантику. Есть и такие алгоритмы, которые выполняют похожие действия, но имеют различные имена. Так, имена предикатных версий алгоритмов всегда заканчиваются на _if, скажем find_if(). Например, есть вариант алгоритма replace(), где используется встроенный оператор равенства, и вариант с именем replace_if(), которому передается предикатный объект-функция или указатель на функцию-предикат.

Алгоритмы, модифицирующие контейнер, обычно также существуют в двух вариантах: один осуществляет модификацию по месту, а второй возвращает копию с внесенными изменениями. Так, есть алгоритмы replace() и replace_copy(). Однако вариант с копированием (его имя всегда содержит слово _copy) имеется не для каждого алгоритма, модифицирующего контейнер. К примеру, для алгоритмов sort() его нет. В таких случаях, если нужно, чтобы алгоритм работал с копией, мы должны создать ее самостоятельно и передать в качестве аргумента.

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

#include algorithm

Для употребления любого из четырех численных алгоритмов: adjacent_difference(), accumulate(), inner_product() и partial_sum() - нужно включить также файл

#include numeric

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

Другое, более подробное, чем в этой книге, описание обобщенных алгоритмов можно найти в работе [MUSSER96], правда, оно несколько отстает от окончательного варианта стандартной библиотеки C++.

Алгоритм accumulate()

template class InputIterator, class Type

Type accumulate(

InputIterator first, InputIterator last,

Type init );

template class InputIterator, class Type,

class BinaryOperation

Type accumulate(

InputIterator first, InputIterator last,

Type init, BinaryOperation op );

Первый вариант accumulate() вычисляет сумму значений элементов последовательности из диапазона, ограниченного парой итераторов [first,last), с начальным значением, которое задано параметром init. Например, если дана последовательность {1,1,2,3,5,8} и начальное значение 0, то результатом работы алгоритма будет 20. Во втором варианте вместо оператора сложения к элементам применяется переданная бинарная операция. Если бы мы передали алгоритму accumulate() объект-функцию times и начальное значение 1, то получили бы результат 240. accumulate() - это один из численных алгоритмов; для его использования в программу необходимо включить заголовочный файл .

#include numeric

#include list

#include functional

#include iostream.h

/*

* выход:

* accumulate()

* работает с последовательностью {1,2,3,4}

*результат для сложения по умолчанию: 10

*результат для объекта-функции plusint: 10

*/

int main()

{

int ia[] = { 1, 2, 3, 4 };

listint,allocator ilist( ia, ia+4 );

int ia_result = accumulate(&ia[0], &ia[4], 0);

int ilist_res = accumulate(

ilist.begin(), ilist.end(), 0, plusint() );

cout "accumulate() "

"работает с последовательностью {1,2,3,4} "

"результат для сложения по умолчанию: "

ia_result " "

"результат для объекта-функции plusint: "

ilist_res

endl;

return 0;

}

Алгоритм adjacent_difference()

template class InputIterator, class OutputIterator

OutputIterator adjacent_difference(

InputIterator first, InputIterator last,

OutputIterator result );

template class InputIterator, class OutputIterator

class BinaryOperation

OutputIterator adjacent_difference(

InputIterator first, InputIterator last,

OutputIterator result, BinaryOperation op );

Первый вариант adjacent_difference() создает новую последовательность, в которой значение каждого элемента, кроме первого, равно разности между текущим и предыдущим элементами исходной последовательности. Например, если дано {0,1,1,2,3,5,8}, то первым элементом новой последовательности будет копия: 0. Вторым - разность первых двух элементов исходной последовательности: 1. Третий элемент равен разности третьего и второго элементов: 1-1=0, и т.д. В результате мы получим последовательность {0,1,0,1,1,2,3}.

Во втором варианте разность соседних элементов вычисляется с помощью указанной бинарной операции. Возьмем ту же исходную последовательность и передадим объект-функцию timesint. Как и раньше, первый элемент просто копируется. Второй элемент - это произведение первого и второго элементов исходной последовательности; он тоже равен 0. Третий элемент - произведение второго и третьего элементов исходной последовательности: 1 * 1 = 1, и т.д. Результат - {0,1,2,6,15,40}.

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

#include numeric

#include list

#include functional

#include iterator

#include iostream.h

int main()

{

int ia[] = { 1, 1, 2, 3, 5, 8 };

listint,allocator ilist(ia, ia+6);

listint,allocator ilist_result(ilist.size());

adjacent_difference(ilist.begin(), ilist.end(),

ilist_result.begin() );

// на выходе печатается:

// 1 0 1 1 2 3

copy( ilist_result.begin(), ilist_result.end(),

ostream_iteratorint(cout," "));

cout endl;

adjacent_difference(ilist.begin(), ilist.end(),

ilist_result.begin(), timesint() );

// на выходе печатается:

// 1 1 2 6 15 40

copy( ilist_result.begin(), ilist_result.end(),

ostream_iteratorint(cout," "));

cout endl;

}

Алгоритм adjacent_find()

template class ForwardIterator

ForwardIterator

adjacent_find( ForwardIterator first, ForwardIterator last );

template class ForwardIterator, class BinaryPredicate

ForwardIterator

adjacent_find( ForwardIterator first,

ForwardIterator last, Predicate pred );

adjacent_find() ищет первую пару одинаковых соседних элементов в диапазоне, ограниченном итераторами [first,last). Если соседние дубликаты найдены, то алгоритм возвращает однонаправленный итератор, указывающий на первый элемент пары, в противном случае возвращается last. Например, если дана последовательность {0,1,1,2,2,4}, то будет найдена пара [1,1] и возвращен итератор, указывающий на первую единицу.

#include algorithm

#include vector

#include iostream.h

#include assert.h

class TwiceOver {

public:

bool operator() ( int val1, int val2 )

{ return val1 == val2/2 ? true : false; }

};

int main()

{

int ia[] = { 1, 4, 4, 8 };

vector int, allocator vec( ia, ia+4 );

int *piter;

vector int, allocator ::iterator iter;

// piter указывает на ia[1]

piter = adjacent_find( ia, ia+4 );

assert( *piter == ia[ 1 ] );

// iter указывает на vec[2]

iter = adjacent_find( vec.begin(), vec.end(), TwiceOver() );

assert( *iter == vec[ 2 ] );

// пришли сюда: все хорошо

cout "ok: adjacent-find() завершился успешно! ";

return 0;

}

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг

7.3.5 Обобщенные Классы

Из книги C++ автора Хилл Мюррей

7.3.5 Обобщенные Классы Очевидно, можно было бы определить списки других типов (classdef*, int, char* и т.д.) точно так же, как был опредлен класс nlist: простым выводом из класса slist. Процесс оределения таких новых типов утомителен (и потому чреват ошиками), но с помощью макросов его можно


Фотографии в порядке

Из книги Журнал «Компьютерра» № 9 от 7 марта 2006 года автора Журнал «Компьютерра»

Фотографии в порядке Автор: Юрий МеркуловКоличество изображений на жестком диске у владельцев цифровых камер растет если не в геометрической, то уж в арифметической прогрессии — точно. И если несколько лет тому назад стоял вопрос о софте для просмотра снимков, то сейчас


Расположить в обратном порядке (Reverse)

Из книги Руководство по стандартной библиотеке шаблонов (STL) автора Ли Менг

Расположить в обратном порядке (Reverse) template ‹class BidirectionalIterator›void reverse(BidirectionalIterator first, BidirectionalIterator last);Для каждого неотрицательного целого числа i‹=(last-first)/2 функция reverse применяет перестановку ко всем парам итераторов first+i, (last-i)-1. Выполняется точно (last-first)/2 перестановок.template


(3.32) Как заставить службы (service) запускаться в определённом порядке?

Из книги Win2K FAQ (v. 6.0) автора Шашков Алексей

(3.32) Как заставить службы (service) запускаться в определённом порядке? Для этого служит ключ в реестре под названием DependOnService. Найти его можно в ветке относящейся к службе HKLMSystemCurrentControlSetServisesИмя службы Присвойте этому ключу имя службы которая должна стартовать раньше. Если


Ошибка 0x000000E3: а с винчестером все в порядке?

Из книги Очень хороший самоучитель пользователя компьютером. Как самому устранить 90% неисправностей в компьютере и увеличить его возможности автора Колисниченко Денис Николаевич

Ошибка 0x000000E3: а с винчестером все в порядке? Сбой файловой системы NTFS. Жесткий диск «посыпался»? Нужно сделать диагностику жесткого диска. Возможно, придется переформатировать жесткий


47. Определяйте и инициализируйте переменные-члены в одном порядке

Из книги Стандарты программирования на С++. 101 правило и рекомендация автора Александреску Андрей

47. Определяйте и инициализируйте переменные-члены в одном порядке РезюмеПеременные-члены всегда инициализируются в том порядке, в котором они объявлены при определении класса; порядок их упоминания в списке инициализации конструктора игнорируется. Убедитесь, что в


Пример 9-14. Подстановка параметров и сообщение о "порядке использования"

Из книги Искусство программирования на языке сценариев командной оболочки автора Купер Мендель

Пример 9-14. Подстановка параметров и сообщение о "порядке использования" #!/bin/bash# usage-message.sh: ${1?"Порядок использования: $0 ARGUMENT"}# Сценарий завершит свою работу здесь, если входные аргументы отсутствуют,#+ со следующим сообщением.# usage-message.sh: 1: Порядок использования: usage-message.sh


Глава 5 У АРТИСТОВ ВСЁ В ПОРЯДКЕ

Из книги Дело о реформе копирайта автора Энгстрём Кристиан

Глава 5 У АРТИСТОВ ВСЁ В ПОРЯДКЕ Как будут зарабатывать артисты? "Но как же будут зарабатывать артисты?" — вопрос, который нам, Пиратам, чаще всего задают в спорах о реформе копирайта и легализации файлообмена.10 лет назад на этот вопрос трудно было ответить, и лишь немногие


11.1.7. Сортировка а обратном порядке

Из книги Linux и UNIX: программирование в shell. Руководство разработчика. автора Тейнсли Дэвид

11.1.7. Сортировка а обратном порядке Если необходимо отсортировать строки не по возрастанию, а по убыванию, задайте опцию -r:$ sort -r video.txtToy Story:HK:239:3972The H111:KL:63:2972Star Wars:HK:301:4102Boys in Company С:HK:192:2192Aliens:HK:532:4892Alien:HK:119:1982A Few Good


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

Из книги C++ для начинающих автора Липпман Стенли

6.6.3. Обобщенные алгоритмы Операции, описанные в предыдущих разделах, составляют набор, поддерживаемый непосредственно контейнерами vector и deque. Согласитесь, что это весьма небогатый интерфейс и ему явно не хватает базовых операций find(), sort(), merge() и т.д. Планировалось


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

Из книги QT 4: программирование GUI на С++ автора Бланшет Жасмин

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


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

Из книги Описание языка PascalABC.NET автора Коллектив РуБоард

12.5. Обобщенные алгоритмы Первые два аргумента любого обобщенного алгоритма (разумеется, есть исключения, которые только подтверждают правило) – это пара итераторов, обычно называемых first и last, ограничивающих диапазон элементов внутри контейнера или встроенного массива,


12.6. Когда нельзя использовать обобщенные алгоритмы

Из книги автора

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


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

Из книги автора

Обобщенные алгоритмы В заголовочном файле <QtAlgorithms> объявляются глобальные шаблонные функции, которые реализуют основные алгоритмы для контейнеров. Большинство этих функций работают с итераторами в стиле STL.Заголовочный файл STL <algorithm> содержит более полный набор


Обобщенные типы

Из книги автора

Обобщенные типы Обобщенные типы: обзор Обобщенным типом (generic) называется шаблон для создания класса, записи или интерфейса, параметризованный одним или несколькими типами. Класс (запись, интерфейс) образуется из шаблона класса (записи, интерфейса) подстановкой