Обобщенные алгоритмы 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));
