Программирование. Принципы и практика использования C++ Исправленное издание

Страуструп Бьерн

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

[b:e]

, а вторая — только одним итератором

b2

, который считается началом последовательности, содержащей элементы, количество которых достаточно для выполнения алгоритма, например, столько же, сколько элементов в первой последовательности:

[b2:b2+(e–b)]

.

Некоторые алгоритмы, такие как

sort

, используют итераторы произвольного доступа, а многие другие, такие как

find

, только считывают элементы с помощью однонаправленного

итератора.

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

Б.5.1. Немодицифирующие алгоритмы для последовательностей

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

Предотвратить модификацию элементов операцией, передаваемой алгоритму

for_each

, невозможно; это считается приемлемым. Передача операции, изменяющей проверяемые ею элементы, другим алгоритмам (например, count или

==

) недопустима.

Рассмотрим пример правильного использования алгоритма.

bool odd(int x) { return x&1; }

int n_even(const vector<int>& v) // подсчитывает количество четных

// чисел в v

{

return v.size–count_if(v.begin,v.end,odd);

}

Б.5.2. Алгоритмы, модифицирующие последовательности

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

Алгоритм

shuffle

перетасовывает последовательность точно так же, как перетасовывается колода карт; иначе говоря, после перетасовки элементы следуют в случайном порядке, причем смысл слова “случайно” определяется распределением, порожденным датчиком случайных чисел.

Следует подчеркнуть, что эти алгоритмы не знают, являются ли их аргументы контейнерами, поэтому не могут добавлять или удалять элементы. Таким образом, такой алгоритм, как

remove

, не может уменьшить длину входной последовательности, удалив (стерев) ее элементы; вместо этого он передвигает эти элементы к началу последовательности.

typedef vector<int>::iterator VII;

void print_digits(const string& s, VII b, VII e)

{

cout << s;

while (b!=e) { cout << *b; ++b; }

cout << '\n';

}

void ff

{

int a[] = { 1,1,1,2,2,3,4,4,4,3,3,3,5,5,5,5,1,1,1 };

vector<int> v(a,a+sizeof(a)/sizeof(int));

print_digits("all: ",v.begin, v.end);

vector<int>::iterator pp = unique(v.begin,v.end);

print_digits("head: ",v.begin,pp);

print_digits("tail: ",pp,v.end);

pp=remove(v.begin,pp,4);

print_digits("head: ",v.begin,pp);

print_digits("tail: ",pp,v.end);

}

Результат

приведен ниже.

all: 1112234443335555111

head: 1234351

tail: 443335555111

head: 123351

tail: 1443335555111

Б.5.3. Вспомогательные алгоритмы

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

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

uninitialized_fill

и

uninitialized_copy

, должны иметь встроенный тип или быть неинициализированными.

Б.5.4. Сортировка и поиск

Сортировка и поиск относятся к категории фундаментальных алгоритмов. В то же время потребности программистов довольно разнообразны. Сравнение по умолчанию выполняется с помощью оператора

<

, а эквивалентность пар значений

a

и

b

определяется условием

!(a<b)&&!(b<a)

, а не оператором

==

.

Рассмотрим следующий пример:

vector<int> v;

list<double> lst;

v.push_back(3); v.push_back(1);

v.push_back(4); v.push_back(2);

lst.push_back(0.5); lst.push_back(1.5);

lst.push_back(2); lst.push_back(2.5); // список lst упорядочен

sort(v.begin,v.end); // сортировка вектора v

vector<double> v2;

merge(v.begin,v.end,lst.begin,lst.end,back_inserter(v2));