Состав библиотеки алгоритмов

Все алгоритмы библиотеки можно разделить на такие группы [3]:

· немодифицирующие алгоритмы (немутирующие алгоритмы);

· модифицирующие алгоритмы (мутирующие алгоритмы);

· сортировка последовательностей;

· операции с множествами;

· операции с пирамидами (кучей);

· поиск экстремальных значений;

· перестановки в лексикографическом порядке.

Всего в состав этих 7 категорий входит 60 функций.

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

Таблица 1

Немодифицирующие алгоритмы

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

Таблица 2

Модифицирующие алгоритмы

Таблица 3

Сортировка последовательностей

Таблица 4

Операции с множествами

Таблица 5

Операции с пирамидой

Таблица 6

Поиск экстремальных значений

Немодифицирующие алгоритмы

Операция for_each().

template <class InputIterator, class Function>

Function for_each(InputIterator first, InputIterator last, Function f);

Операция for_each() применяет f()  к результату разыменования каждого итератора в диапазоне [first, last) и возвращает f(). Функция должна быть унарной и выполнять доступ к элементам последовательности только на чтение. Функция f() применяется точно last-first раз. Если f() возвращает результат, то он игнорируется. Этот алгоритм рекомендуется применять всякий раз вместо явной записи цикла. Вряд ли меет смысл применять for_each() для накапливания информации об элементах контейнера (см. accumulate), поиска чего-либо в последовательности (см. find и find_if). Если ни одна из специализированных операций не подходит, то используйте for_each() для решения своей частной задачи.

Операция find().

template <class InputIterator, class T>

InputIterator find(InputIterator first, InputIterator last, const T& value);

Операция find() возвращает первый итератор iter в диапазоне [first, last), для которого *iter == value. Если такой итератор не найден – возвращается last.

Операция find_if().

template <class InputIterator, class Predicate>

InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);

Операция find_if() возвращает первый итератор iter в диапазоне [first, last), для которого pred(*iter) == true. Если такой итератор не найден, возвращается last. Другими словами, она находит первый попавшийся элемент последовательности, для которого функция-предикат pred возвратила значение true.

Операция find_first_of().

template<class FwdIt1, class FwdIt2>

FwdIt1 find_first_of(FwdIt1 first1, FwdIt1 last1,

   FwdIt2 first2, FwdIt2 last2);

template<class FwdIt1, class FwdIt2, class Pred>

FwdIt1 find_first_of(FwdIt1 first1, FwdIt1 last1,

   FwdIt2 first2, FwdIt2 last2, Pred pr);

Первый вариант операции находит первое появление такого элемента в последовательности FwdIt1, значение которого равно значению любого элемента из последовательности FwdIt2. Если такое значение найдено, возвращается итератор, указывающий на позицию элемента в первой последовательности FwdIt1. Другими словами, функция определяет такое минимальное N из диапазона [0, last1 - first1), что для некоторого M из диапазона [0, last2 - first2)  выражение *(first1 + N) == *(first2 + M) истинно. Если такое значение не найдено, операция возвращает last1.

Второй вариант операции делает все то же самое, но вместо операции проверки на равенство == используется предикат pr.

Операция adjacent_find().

template <class ForwardIterator>

ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);

template <class ForwardIterator, class BinaryPredicate>

ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last,

    BinaryPredicate binary_pred);

Операция adjacent_find() возвращает первый итератор iter такой, что iter и iter+1 находятся в диапазоне [first, last) и для которого справедливо равенство *iter == *(iter + 1) или, для второго варианта операции, binary_pred(*iter, *(iter + 1)) == true. Если такой итератор iter не найден – возвращается last. Соответствующий предикат применяется, самое большее, max((last - first) - 1, 0) раз.

Операции count() и count_if().

template <class InputIterator, class T, class Size>

size_t count(InputIterator first, InputIterator last, const T& value);

template <class InputIterator, class Predicate, class Size>

size_t count_if(InputIterator first, InputIterator last, Predicate pred);

Операция count() подсчитывает число элементов диапазона [first, last) последовательности, значения которых равны заданному value, и возвращает это число.

Операция count_if() подсчитывает число элементов диапазона [first, last) последовательности, для которых предикат pred возвращает true.

Операция mismatch().

template <class InputIterator1, class InputIterator2>

pair <InputIterator1, InputIterator2> mismatch(InputIterator1 first1,

InputIterator1 last1, InputIterator2 first2);

template <class InputIterator1, class InputIterator2, class BinaryPredicate>

pair <InputIterator1, InputIterator2> mismatch(InputIterator1 first1,

InputIterator1 last1, InputIterator2 first2,

BinaryPredicate binary_pred);

Операция mismatch() последовательно сравнивает соответствующие элементы двух последовательностей с целью поиска отличающихся элементов. Если такие элементы найдены, то возвращается пара итераторов, указывающих на эти элементы. Во втором варианте операции для сравнения используется предикат binary_pred. Если такие элементы не найдены, то возвращается пара last1 и first2 + (last1 - first1). Шаблон pair предназначен для инициализации и хранения двух итераторов, имеющих, возможно, разные типы.

Операция equal().

template <class InputIterator1, class InputIterator2>

bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);

template <class InputIterator1, class InputIterator2, class BinaryPredicate>

bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate binary_pred);

Операция equal() возвращает true, если две последовательности равного размера имеют тождественные элементы, или значение false, если встречаются хотя бы два отличающихся элемента. Для проверки тождественности используется операция == или предикат binary_pred. Если число элементов последовательностей разное, то операция возвращает false.

Операция search().

template <class ForwardIterator1, class ForwardIterator2>

ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,

ForwardIterator2 first2, ForwardIterator2 last2);

template <class ForwardIterator1, class ForwardIterator2,

class BinaryPredicate>

ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,

ForwardIterator2 first2, ForwardIterator2 last2,

BinaryPredicate binary_pred);

Операция search() предназначена для поиска в последовательности [first1,last1) первой подпоследовательности, идентичной другой последовательности [first2,last2). Для проверки идентичности используется операция == или предикат binary_pred.

Операция find_end().

template<class FwdIt1, class FwdIt2>

FwdIt1 find_end(FwdIt1 first1, FwdIt1 last1,

   FwdIt2 first2, FwdIt2 last2);

template<class FwdIt1, class FwdIt2, class Pred>

FwdIt1 find_end(FwdIt1 first1, FwdIt1 last1,

   FwdIt2 first2, FwdIt2 last2, Pred pr);

Операцияfind_end() похожа на операцию search(), но отыскивает в последовательности [first1,last1) последнее появление подпоследовательности, идентичной другой последовательности [first2,last2). Для проверки идентичности используется операция == или предикат binary_pred.

Операция search_n()

template<class FwdIt, class Dist, class T>

FwdIt search_n(FwdIt first, FwdIt last, Dist Count, const T& val);

template<class FwdIt, class Dist, class T, class Pred>

FwdIt search_n(FwdIt first, FwdIt last, Dist Count, const T& val, Pred pr);

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

Пример программы, иллюстрирующей некоторые немодифицирующие алгоритмы

// AlgTest.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include "AlgTest.h"

#include <Conio.h>

#include <algorithm> // for_each, find, find_if

#include <vector>

#include <functional> // unary_function

//…

using namespace std;

const int VectorSize =5;

//Print – простейший объект-функция, выполняющая вывод аргумента на монитор

template <class T>

class Print : public unary_function<T, void>

{

public:

void operator()(T& arg1) { cout<< arg1<<' '; }

};

// GreaterThanTwo – объект-функция (предикат), которая возвращает

// значение true, если аргумент превышает значение 2

template <class T>

class GreaterThanTwo : public unary_function<T, bool>

{

public:

bool operator()(T& arg1)

{ return (arg1>2); }

};

// ShowElement – шаблонная функция, печатающая значение итератора itor,

// указывающего на элемент последовательности Container. Если значение

// итератора "законечное", то функция выводит строку "Last element!"

template <class Container, class Iterator>

void ShowElement(Container & c, Iterator & itor)

{

if(itor!= c.end()) cout<<*itor; else cout<<"Last element!";

}

int _tmain(int argc, TCHAR* argv[], TCHAR* envp[])

{

int nRetCode = 0;

// initialize MFC and print and error on failure

if (!AfxWinInit(::GetModuleHandle(NULL), NULL, ::GetCommandLine(), 0))

{

       // TODO: change error code to suit your needs

       _tprintf(_T("Fatal Error: MFC initialization failed\n"));

       nRetCode = 1;

}

Print <int> DoPrint;

vector <int> vInt(VectorSize);

typedef vector <int>::iterator Itor;

for(int i=0; i<VectorSize; i++)vInt[i]=i;

Itor first = vInt.begin();

Itor last = vInt.end();

// вывести все элементы последовательности с помощью for_each

// и объекта-функции DoPrint

cout<<"Test method for_each()\n";

for_each(first,last,DoPrint); // 0 1 2 3 4

cout<<endl;

// найти первый элемент вектора, значение которого равно 2

Itor retItor=find(first,last,2);

cout<<"find(first,last,2)=";

ShowElement(vInt,retItor); //find(first,last,2)=2

cout<<endl;

// найти первый элемент вектора, значение которого равно 10

retItor=find(first,last,10);

cout<<"find(first,last,10)=";

ShowElement(vInt,retItor); //find(first,last,10)=Last element!

cout<<endl;

// найти первый элемент вектора, значение которого больше 2

GreaterThanTwo <int> isGreaterThanTwo;

retItor=find_if(first,last,isGreaterThanTwo);

cout<<"find_if(first,last,isGreaterThanTwo)=";

ShowElement(vInt,retItor);//find_if(first,last,isGreaterThanTwo)=3

cout<<endl;

// подсчитать число элементов вектора, значение которых равно 3

int retSize=count(first,last,3);

cout<<"count(first,last,3)="<<retSize<<endl; //count(first,last,3)=1

// подсчитать число элементов вектора, значение которых больше 2

retSize=count_if(first,last,isGreaterThanTwo);

cout<<"count_if(first,last,isGreaterThanTwo)="<<retSize<<endl;

//count_if(first,last,isGreaterThanTwo)=2

_getch();

return nRetCode;

}

//вывод программы:

//0 1 2 3 4

//find(first,last,2)=2

//find(first,last,10)=Last element!

//find_if(first,last,isGreaterThanTwo)=3

//count(first,last,3)=1

//count_if(first,last,isGreaterThanTwo)=2