return 15 < х;

int mainO { int a[] = { 10. 20. 30 }: const s1ze t SIZE = sizeof a / sizeof a[0]: ofstream outfCints.out ): remove copy if(a. a + SIZE.

ostream iterator<int>(outf. \n ). gtl5):

} III:-

Потоковый итератор ввода позволяет алгоритму прочитать исходные данные из потока ввода. Для этого конструктор и операторная функция operator++() читают следующий элемент из базового потока, а перегруженная операторная функция operator* О возвращает ранее прочитанное значение. Поскольку исходный интервал в алгоритмах задается двумя указателями, объект istreamjterator можно сконструировать двумя способами:

: C06:CopyIntsFromFile.cpp

Использование потокового итератора ввода

linclude <algorithm>

linclude <fstream>

linclude <iostream>

linclude <iterator>

linclude ../require.h

using namespace std:

bool gtl5(int x) { return 15 < x;

int mainO { ofstream inf( somelnts.dat ): ints 1 3 47 5 84 9 : ints.closeO:

ifstream inf( somelnts.dat ); assure(inf. someInts.dat ): remove copy i f(i stream i terator<i nt>(i nf).

i streamjterator<i nt>().

ostream iterator<int>(cout. \n ). gtl5):

} III:-

Первый аргумент replace copyJf() связывает объект istreamjterator с файловым потоком ввода, содержащим данные типа int. Второй аргумент использует конструктор по умолчанию класса istreamjterator. Этот вызов конструирует istreamJterator() в особом состоянии, обозначающем конец файла. Таким образом, когда первый итератор достигает конца физического файла, он становится равным значению istreamJterator<int>(), и работа алгоритма корректно заверщается. Обратите внимание: в этом примере мы полностью обощлись без явного объявления массива.

Сложность алгоритмов

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

Объекты функций

в приводившихся примерах неоднократно встречалась функция gtl5(). Как нетрудно заметить, польза от такой функции весьма невелика. Если порог сравнения бу-

Или в математической записи - 0(п log п). Это означает, что при больших значениях п количество сравнений растет прямо пропорционально функции /(и) = п log п.

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

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

size t п = countJfCa. a+SIZE. gtl5);

Поскольку алгоритм countJf() должен просмотреть каждый элемент ровно один раз, стандарт указывает, что количество операций сравнения должно соответствовать количеству элементов в интервале. Аналогичная спецификация установлена для алгоритма сору().

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

int* р = find(a. а + SIZE. 20);

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

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

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

Разве что с нежелательным применением глобальных переменных.

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

дет определяться другой величиной, придется определять функции gt20(), gt25() и т. д. Определять несколько одинаковых функций не только скучно, но и неразумно, потому что все необходимые значения известны на момент написания программы.

Более того, из этого следует, что для управления поиском не могут использоваться данные времени выполнения, а такое ограничение неприемлемо. Для решения проблемы необходим способ передачи информации предикатам во время выполнения программы. Например, было бы удобно определить функцию больше , которая инициализируется произвольным значением. К сожалению, это значение не может передаваться при вызове, поскольку унарные предикаты (к числу которых относится наша функция gtl5()) применяются к каждому элементу интервала по отдельности и получают только один параметр.

Как обычно, выход из положения основан на создании абстракции. Здесь нужна абстракция, которая бы работала, как функция, хранила информацию состояния и вызывалась с нужным количеством параметров. Такая абстракция называется объектом функции.

Объект функции представляет собой экземпляр класса с перегруженным оператором вызова функции (). Этот оператор позволяет использовать объект в традиционном синтаксисе вызова функции. Как и любой другой объект, объект функции инициализируется конструкторами. Ниже приведен объект функции, который может использоваться вместо gtl5():

: C06:GreaterThanN.cpp linclude <iostreani> using namespace std;

class gt n { int value; public:

gt n(int val) : value(val) {} bool OperatorO (int n) { return n > value:

int mainO { gt n f(4):

cout f(3) endl; Выводит 0 (для false) cout f(5) endl; Выводит 1 (для true) } III:-

Фиксированная величина для сравнения (4) передается при создании объекта функции. Затем компилятор интерпретирует выражение f(3) как вызов следующей функции:

f.operatorOO):

Команда возвращает значение выражения 3 > value, ложное при value = 4, как в нашем примере.

Поскольку такие сравнения применимы и к другим типам, помимо int, было бы логично определить gt n() в виде шаблона класса. Впрочем, вам не придется делать