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

Обобщенные алгоритмы STL разделяются на четыре большие категории в соответствии с их семантикой. Неизменяющие алгоритмы над последовательностями работают с контейнерами без модификации их содержимого, в то время как изменяющие алгоритмы над последовательностями обычно модифицируют содержимое контейнеров, с которыми они имеют дело. Связанные с сортировкой алгоритмы включают алгоритмы сортировки и слияния, алгоритмы бинарного поиска и операции над множествами, работающие с упорядоченными последовательностями. Наконец, имеется небольшой набор обобщенных числовых алгоритмов. Неизменяющие алгоритмы над последовательностями — это алгоритмы, которые непосредственно не модифицируют контейнеры, с которыми работают. Они включают алгоритмы для поиска элементов в последовательностях, проверки равенства и пересчета элементов последовательности. Это алгоритмы f in d , a d ja c e n t_ f in d , co u n t, f o r _ e a c h , m ism atch, e q u a l и

s e a r c h . Алгоритм a d j a c e n t_ f in d выполняет сканирование последовательности в поисках пары смежных одинаковых элементов. Когда такая пара найдена, алгоритм возвращает итератор, указывающий на первый элемент пары. Алгоритм c o u n t представляет собой неизменяющий алгоритм, сканирующий последовательность для подсчета количества элементов, равных определенному значению. Обобщенный алгоритм f o r _ e a c h применяет функцию f к каждому элементу последовательности. Алгоритмы m ism atch и e q u a l используются для сравнения двух диапазонов. Каждый из них получает три параметра-итератора: f i r s t l , l a s t l и f i r s t 2 . Алгоритм e q u a l возвращает tr u e , если элементы в соответствующих позициях f i r s t l + / и f i r s t 2 + i иравны для всех позиций f i r s t l + iиз диапазона [ f i r s t l ; l a s t l ) , и f a ls e в противном случае. Алгоритм m ism atch возвращает пару итераторов (тип p a ir ) ,11 f i r s t l + in f i r s t 2 + i, которые представляют собой первые позиции последовательностей, где найдены неодинаковые элементы. Если неодинаковых элементов в соответствующих позициях не обнаружено, возвращается пара итераторов l a s t l и f i r s t 2 + ( l a s t l - f i r s t l ) . Для двух данных диапазонов обобщенный алгоритм s e a r c h находит первую позицию в первом диапазоне, с которой вторая позиция входит в первую в качестве подпоследовательности. Этот алгоритм обобщает функции поиска подстрок наподобие библиотечной функции С strstr .

Пример 5.4. Иллюстрация применения обобщенного алгоритма f in d i f

иех05-04.срр" 97а =

#include <iostream>

#include <algorithm>

#include <cassert>

#include <vector>

using namespace std;

// Определение типа унарного предиката:

class GreaterThanSO {

public:

bool operator()(int x) const { return x > 50; }

};

int main()

{

cout << "Иллюстрация применения обобщенного "

<< "алгоритма find_if." << endl ;

// Создание вектора со значениями

// 0, 1, 4, 9, 16, . . . , 144:

vector<int> vectorl;

for (int i = 0; i < 13; ++i)

vectorl.push_back(i * i);

vector<int>::iterator where;

where = find_if(vectorl.begin(), vectorl.e nd(),

GreaterThanSO());

assert (*where == 64);

cout << " -- Ok." << endl;

return 0;

}

Пример 5.5. Иллюстрация применения обобщенного алгоритма

adj a c e n t f in d

"ех05-05.срр" 976 =

#include <iostream>

#include <string>

#include <algorithm>

#include <cassert>

#include <functional>

#include <deque>

using namespace std;

int main()

{

cout << "Иллюстрация применения обобщенного "

<< "алгоритма adjacent_find." << endl;

deque<string> player(5);

deque<string>::iterator i;

// Инициализация дека:

player[0] = "Pele";

player[1] = "Platini";

player[2] = "Maradona";

player[3] = "Maradona";

player[4] = "Rossi";

// Поиск первой пары одинаковых последовательных имен:

i = adjacent_find(player.begin(), player.e n d ());

assert (*i == "Maradona" && *(i+l) == "Maradona");

// Поиск первого имени, лексикографически большего,

// чем следующее за ним:

i = adjacent_find(player.begin(), player.e n d (),

greater<string>());

assert (*i == "Platini" && *(i+l) == "Maradona");

cout << " -- Ok." << endl;

return 0;

}

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

Например, алгоритм u n iq u e удаляет все последовательные дублирующиеся элементы из последовательности. Другие алгоритмы из этой категории копируют, заполнят, генерируют, замещают и т.п. элементы последовательных контейнеров, с которыми работают.

Обобщенные алгоритмы сору и co p y _ b ack w ard используются для копирования элементов из одного диапазона в другой. Вызов copy(firstl/ lastl, first2) копирует элементы из диапазона [ f i r s t l ; l a s t l ) в [ f i r s t 2 ; l a s t 2 ) и возвращает итератор la s t2 , где la s t2 == f i r s t 2 + ( l a s t l - f i r s t l ) . Алгоритм работает в прямом направлении, копируя исходные элементы в порядке f i r s t l , f i r s t l + 1, ..., l a s t l - 1 ,

так что целевой диапазон может перекрываться с исходным, если последний не содержит f i r s t 2. Так, например, со р у может использоваться для сдвига диапазона на одну позицию влево, но не вправо. Обратное верно для алгоритма copy_backw ard: c°py_backward(firstl, lastl, last2) который копирует элементы из диапазона [ f i r s t l ; l a s t l ) в диапазон [ f i r s t 2 ; l a s t 2 ) и возвращает f i r s t 2 , где f i r s t 2 == la s t2 - ( l a s t l - f i r s t l ). Он работает в обратном направлении, копируя исходные элементы в порядке l a s t l - 1 , l a s t l - 2 , ..., f i r s t l . Таким образом, копирование выполняется корректно, если исходный диапазон не содержит l a s t 2.

Пример 5.10. Демонстрация использования обобщенных алгоритмов сору И copy backward

"ех05- 1 0 .срр" 104 =

#include <iostream>

#include <cassert>

#include <algorithm>

#include <vector>

#include <string>

#include <iostream>

using namespace std;

int main()

{

cout << "Демонстрация использования обобщенных "

<< "алгоритмов сору и copy_backward." << endl;

string s ("abcdefghihklmnopqrstuvwxyz");

vector<char> vectorl(s.begin(), s .end());

vector<char> vector2(vectorl.size());

// Копирование vectorl в vector2:

copy(vectorl.begin(), vectorl.e nd(),

vector2.begin( ) ) ;

assert (vectorl == vector2);

// Сдвиг содержимого vectorl влево на 4 позиции:

copy(vectorl.begin() + 4, vectorl.e nd(),

vectorl.begin());

assert (string(vectorl.begin(), vectorl.end()) ==

string("efghihklmnopqrstuvwxyzwxyz"));

// Сдвиг его же вправо на 2 позиции:

copy_backward(vectorl.begin(), vectorl.e nd() - 2,

vectorl.e nd());

assert (string(vectorl.begin(), vectorl.end()) ==

string("efefghihklmnopqrstuvwxyzwx"));

cout << " -- Ok." << endl;

return 0 ;

}

Первый пример copy выполняет копирование содержимого v e c to r l в v e c to r 2. Второй пример иллюстрирует копирование перекрывающихся диапазонов, сдвигая содержимое v e c to r l влево на четыре позиции. Обратите внимание, что после копирования первые четыре символа, ab ed , оказываются потеряны, а последние четыре, wxyz, повторяются в конце дважды. Пример co p y _ b ack w ard выполняет сдвиг на две позиции вправо; такой сдвиг нельзя выполнить при помощи алгоритма сору. В этом случае первые два символа, e f , повторяются в начале строки, а последние два, yz, будут утеряны. Алгоритмы f i l l и f i l l _ n помещают копии данного значения во все позиции диапазона. Вызов fill(first, last, value) помещает l a s t - f i r s t копий v a lu e в [ f i r s t ; l a s t ). Вызов fill_n(first, n, value) помещает n копий v a lu e в [ f i r s t ; f i r s t + n ) . Алгоритм g e n e r a te заполняет диапазон [ f i r s t ; l a s t ) значениями, которые возвращают l a s t - f i r s t последовательных вызовов функции g en (третий параметр алгоритма g e n e r a te ) . Предполагается, что g en не получает никаких аргументов. Обобщенный алгоритм ran d o m _ sh u f f le случайным образом переставляет элементы из диапазона [ f i r s t ; l a s t ), используя для этого функцию, генерирующую псевдослучайные числа. Перестановки, получающиеся при применении алгоритма ran d o m _ sh u f f le , имеют приблизительно равномерное распределение, т.е. вероятность каждой из N\ перестановок диапазона размером N приблизительно равна \/N\ . Обобщенный алгоритм remove удаляет из диапазона те элементы, которые равны определенному значению. Этот алгоритм устойчивый, т.е. он сохраняет относительный порядок остающихся элементов последовательности. Обобщенный алгоритм r e p la c e заменяет элементы в диапазоне, равные некоторому заданному значению, другим значением. Обобщенный алгоритм r o t a t e выполняет циклический сдвиг диапазона. Вызов r o t a t e (f i r s t , m iddle, la s t) циклически сдвигает элементы в диапазоне [ f i r s t ; l a s t ) влево на m id d le - f i r s t позиций. STL предоставляет три обобщенных алгоритма сортировки,— s o r t, p a r t i a l s o r t и s ta b le _ s o r t. Каждый сортирует последовательность с произвольным доступом и размещает результат в том же контейнере, с которым работает. Алгоритм p a r tia l_ _ s o r t требует константного количества дополнительной памяти, s o r t — логарифмического. Они оба по сути являются алгоритмами, работающими “на месте”, в то время как алгоритм s ta b le _ s o r t может потребовать линейного количества дополнительной памяти. В STL входят четыре обобщенных числовых алгоритма: a c c u m u la te , p a r tia l_ s u m , a d ja c e n t_ d if f e r e n c e и in n e r _ j? r o d u c t. В этом разделе мы рассмотрим примеры ис­

пользования каждого из этих алгоритмов. Обобщенный алгоритм a c c u m u la te суммирует значения из указанного диапазона.

49. Функциональные объекты STL. Простые функциональные объекты. Стандартные функциональные объекты. Связыватели std::bind.

Функциональный объект представляет собой любую сущность, которая может быть применена к нулю или большему количеству элементов для получения значения и/или изменения состояния вычислений. В программировании на C++ любая обычная функция отвечает этому определению, но ему же отвечает и объект любого класса (или структуры), который перегружает оператор вызова функции o p e r a to r ().Приведем пример работы функциональных объектов с двумя аргументами функции. Определим шаблонный класс PairSelect, содержащий функцию печати, которая выводит меньший элемент пары в соответствии с определенным нами отношением «меньше чем», задаваемым параметром шаблона. Также в виде параметра шаблона мы зададим тип элементов пары. Следующая программа использует два отношения упорядочения. Они реализованы в виде бинарных предикатов, то есть функций, которые имеют два аргумента и возвращают логическое значение. Наш первый бинарный предикат, LessThan, является шаблоном, поэтому он применим к любому типу, для которого определен оператор < Второй предикат, CompareLastDigits,является обычным, не шаблонным, функциональным классом, который практически совпадает с функциональным классом, определенным в последнем разделепредыдущей главы, только результат его вызова равен true,если последняя цифра первого аргумента меньше, чем у второго, и false - в противном случае.

// funobj3.cpp: Функция operator!) как

// бинарный предикат.

#include <iostream.h>

template <class T>

struct LessThan {

bool operator()(const T &x, const T &y)const

{ return x < y;

}

} ;

struct CompareLastDigits {

bool operator()(int x, int y)const

{ return x % 10 < у % 10;

}

};

Функциональные объекты 141

template <class Т, class Compare>

class PairSelect {

public:

PairSelect(const T &x, const T &y) : a(x), b(y){}

void PrintSmaller()const

{ cout << (Compare()(a, b) ? a : b) « endl;

}

private:

Т а , b ;

} ;

int main()

{ PairSelect<double, LessThan<double> > P (123.4, 98.7);

P.PrintSmaller(); // Вывод: 98.7

PairSelect<int, CompareLastDigits> Q (123, 98);

Q.PrintSmaller(); // Вывод: 123

return 0;

}

Эта программа сначала выводит значение 98.7, потому что оно меньше другого элемента объекта Q - 123.4. После этого она выводит 123, поскольку последняя цифра этого числа - 3 - меньше, чем последняя цифра числа 98. Одно из главных преимуществ заключается в том, что объекты, в отличие от обычных функций, могут хранить дополнительную информацию, которая затем может использоваться обобщенными алгоритмами или контейнерами. Связыватель (binder) применяется для преобразования бинарного функционального объекта в унарный путем связывания аргумента с некоторым определенным значением. В STL это достигается с помощью использования привяжи,которая является одним из видов адаптера функции. Чтобы превратить бинарный предикат в унарный, привязав его второй аргумент, мы используем привязку bind2nd.В нашем примере требуется использовать выражение bind2nd(less<int>(), 100) чтобы указать, что мы хотим считать только значения, меньшие 100. Следующая программа показывает, как это все работает // binder.срр: Использование адаптера bind2nd для подсчета, сколько из элементов массива меньше, чем 100.

♦include <iostream>

♦include <algorithm>

♦include <functional>

using namespace std;

int main()

{ int a [10] = {800, 3, 4, 600, 5, 6, 800, 71, 100, 2},

n = 0;

n = count_if(a, a + 10, bind2nd(less<int>(), 100));

cout << n « endl; // Вывод: 6

return 0;

}

Для п р и вязы ван и я первого аргумента сущ ествует п р и вязка bindXst. К примеру, заменим условие х < 100 эквивалентным условием 100 > х Этого можно добиться, привязав первый операнд у выражения у > х к значению 100. Следовательно, программа binder.срр выдаст тот же результат, если мы заменим вызов c o u n t if на следующий: n = count_if(a, а + 10, bindlst(greater<int>(), 100));