Нечто, что может быть вызвано как функция

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

template<class Iter, class Pred>

void print_if(Iter first, Iter last, Pred pred)

{

while(first != last)

{

if (pred(*first))

cout << *first;

++first;

}

}

Эта функция выводит на стандартный вывод элементы последовательность удовлетворяющие некоторому критерию. Функция получает в качестве параметров пару итераторов, которые определяют последовательность [first;last), которую нужно обработать, и предикат, который определяет нужно ли выводит элемент последовательности. В данном случае в качестве предиката используется нечто, что может быть вызвано в качестве функции, параметр которой совпадает с типом элемента обрабатываемой последовательности (или тип элемента последовательности может быть приведен к нему) и возвращающим типbool(или нечто приводимое кbool). Поскольку приведенная функция является шаблоном, то в качествеpredможет может быть использовано все, для чего имеет смысл записьpred(*first), это может быть указатель на функцию или объект, у которого переопределенoperator(), такие объекты называются функторами.

Продемонстрируем это на примере (определим предикат, который возвращает trueтолько для четных чисел)

// Функция предикат

bool isEven_1(int value)

{

return (value % 2) == 0;

}

// Функтор-преликат

class isEven_2

{

public:

isEven_2() {}

bool operator() (int value)

{

return (value % 2) == 0;

}

};

Приведенные функции могут быть использованы следующим образом:

vector<int> VectorOfInt;

int i;

for (i = 0; i < 20; i++)

VectorOfInt.push_back(i);

// Здесь в качестве третьего параметра передается адрес функции-предиката

print_if(VectorOfInt.begin(),VectorOfInt.end(),predicate_1);

// Здесь в качестве третьего параметра передается объект, у которого

// определен operator(), который выполняет роль предиката

print_if(VectorOfInt.begin(),VectorOfInt.end(),predicate_2());

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

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

Алгоритмы сортировки

В этой работе будут рассмотрены различные алгоритмы сортировки и поиска. Все эти алгоритмы имеют по две версии: одна сравнивает элементы с помощью operator<, другая использует критерий сравненияCompare, принимающий пару элементов последовательности и возвращающийboolили нечто приводимое кbool, если первый элемент меньше второго. Последовательность отсортирована относительно критерия сравненияcomp, если для любого итератораi, указывающего на элемент в последовательности, и любого неотрицательного целого числаnтакого, чтоi + nявляется допустимым итератором, указывающим на элемент той же самой последовательности,comp(*( i + n), *i) == false.

Необходимо отметить, что все алгоритмы сортировки требуют итераторов с произвольным доступом к элементам, т.е. с помощью алгоритмов сортировки можно отсортировать содержимое vector,deque, встроенного массива языка С, но нельзя отсортировать содержимоеlist².

Основной характеристикой работы алгоритмов сортировки и поиска является скорость их работы. Для всех рассмотренных алгоритмов скорость выражается количеством операций сравнения, которое необходимо провести. Это количество обычно является функцией, аргумент которой – общее число элементов последовательности. Стандартная библиотека содержит несколько алгоритмов сортировки, это объясняется тем, что в некоторых случаях нет необходимости полностью сортировать последовательность, например, нужно найти 5 максимальных элементов или получить отсортированную только часть последовательности, использовать в этих случаях алгоритм полной сортировки слишком расточительно.