Любому алгоритму, которому необходим итератор записи, можно передавать также и итераторы других категорий, перечисленных в пунктах 3, 4 и 5;

∙однонаправленный итератор можно использовать для чтения и записи в контейнер, но только в одном направлении обхода (обход в обоих направлениях поддерживается итераторами следующей категории). К числу обобщенных алгоритмов, требующих как минимум однонаправленного итератора, относятся adjacent_find(), swap_range() и replace(). Конечно, любому алгоритму, которому необходим подобный итератор, можно передавать также и итераторы описанных ниже категорий;

∙двунаправленный итератор может читать и записывать в контейнер, а также перемещаться по нему в обоих направлениях. Среди обобщенных алгоритмов, требующих как минимум двунаправленного итератора, выделяются place_merge(), next_permutation() и reverse();

∙итератор с произвольным доступом, помимо всей функциональности, поддерживаемой двунаправленным итератором, обеспечивает доступ к любой позиции внутри контейнера за постоянное время. Подобные итераторы требуются таким обобщенным алгоритмам, как binary_search(), sort_heap() и nthelement().

Упражнение 12.6

Объясните, почему некорректны следующие примеры. Какие ошибки обнаруживаются во

(a)const vector<string> file_names( sa, sa+6 ); vector<string>::iterator it = file_names.begin()+2;

(b)const vector<int> ivec;

fill( ivec.begin(), ivec.end(), ival );

(c)sort( ivec.begin(), ivec.end() );

(d)list<int> ilist( ia, ia+6 );

binary_search( ilist.begin(), ilist.end() );

время компиляции?

(e) sort( ivec1.begin(), ivec3.end() );

Упражнение 12.7

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

12.5. Обобщенные алгоритмы

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

(иногда его называют интервалом с включенной левой границей) обозначается

//читается так: включает первый и все последующие элементы,

//кроме последнего

следующим образом:

[ first, last )

Эта запись говорит о том, что диапазон начинается с элемента first и продолжается до элемента last, исключая последний. Если

first == last

то говорят, что диапазон пуст.

К паре итераторов предъявляется следующее требование: если начать с элемента first и последовательно применять оператор инкремента, то возможно достичь элемента last. Однако компилятор не в состоянии проверить выполнение этого ограничения; если оно нарушается, поведение программы не определено, обычно все заканчивается аварийным остановом и дампом памяти.

В объявлении каждого алгоритма указывается минимально необходимая категория итератора (см. раздел 12.4). Например, для алгоритма find(), реализующего однопроходный обход контейнера с доступом только для чтения, требуется итератор чтения, но можно передать и однонаправленный или двунаправленный итератор, а также итератор с произвольным доступом. Однако передача итератора записи приведет к ошибке. Не гарантируется, что ошибки, связанные с передачей итератора не той категории, будут обнаружены во время компиляции, поскольку категории итераторов – это не собственно типы, а лишь параметры-типы, передаваемые шаблону функции.

Некоторые алгоритмы существуют в нескольких версиях: в одной используется встроенный оператор, а во второй – объект-функция или указатель на функцию, которая предоставляет альтернативную реализацию оператора. Например, unique() по умолчанию сравнивает два соседних элемента с помощью оператора равенства, определенного для типа объектов в контейнере. Но если такой оператор равенства не определен или мы хотим сравнивать элементы иным способом, то можно передать либо объект-функцию, либо указатель на функцию, обеспечивающую нужную семантику. Встречаются также алгоритмы с похожими, но разными именами. Так, предикатные версии всегда имеют имя, оканчивающееся на _if, например find_if(). Скажем, есть алгоритм replace(), реализованный с помощью встроенного оператора равенства, и replace_if(), которому передается объект-предикат или указатель на функцию.

Алгоритмы, модифицирующие контейнер, к которому они применяются, обычно имеют две версии: одна преобразует содержимое контейнера по месту, а вторая возвращает копию исходного контейнера, в которой и отражены все изменения. Например, есть алгоритмы replace() и replace_copy() (имя версии с копированием всегда заканчивается на _copy). Однако не у всех алгоритмов, модифицирующих контейнер, имеется такая версия. К примеру, ее нет у алгоритма sort(). Если же мы хотим, чтобы сортировалась копия, то создать и передать ее придется самостоятельно.

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

#include <algorithm>

accumulate(), inner_product() и partial_sum() – включить также заголовок

#include <numeric>

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

12.5.1. Алгоритмы поиска

Тринадцать алгоритмов поиска предоставляют различные способы нахождения определенного значения в контейнере. Три алгоритма equal_range(), lower_bound() и upper_bound() выполняют ту или иную форму двоичного поиска. Они показывают, в

adjacent_find(), binary_search(), count(),count_if(), equal_range(), find(), find_end(), find_first_of(), find_if(), lower_bound(),

какое место контейнера можно вставить новое значение, не нарушая порядка сортировки. upper_bound(), search(), search_n()

12.5.2. Алгоритмы сортировки и упорядочения

Четырнадцать алгоритмов сортировки и упорядочения предлагают различные способы упорядочения элементов контейнера. Разбиение (partition) – это разделение элементов контейнера на две группы: удовлетворяющие и не удовлетворяющие некоторому условию. Так, можно разбить контейнер по признаку четности/нечетности чисел или в зависимости от того, начинается слово с заглавной или со строчной буквы. Устойчивый (stable) алгоритм сохраняет относительный порядок элементов с одинаковыми значениями или удовлетворяющих одному и тому же условию. Например, если дана последовательность:

{ "pshew", "honey", "Tigger", "Pooh" }

то устойчивое разбиение по наличию/отсутствию заглавной буквы в начале слова генерирует последовательность, в которой относительный порядок слов в каждой категории сохранен:

{ "Tigger", "Pooh", "pshew", "honey" }

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

inplace_merge(), merge(), nth_element(), partial_sort(), partial_sort_copy(), partition(), random_shuffle(), reverse(), reverse_copy(), rotate(), rotate_copy(), sort(), stable_sort(),

ассоциативным контейнерам, таким, как множество (set) или отображение (map).) stable_partition()

12.5.3. Алгоритмы удаления и подстановки

Пятнадцать алгоритмов удаления и подстановки предоставляют различные способы замены или исключения одного элемента или целого диапазона. unique() удаляет одинаковые соседние элементы. iter_swap() обменивает значения элементов,

copy(), copy_backwards(), iter_swap(), remove(), remove_copy(), remove_if(),remove_if_copy(), replace(), replace_copy(), replace_if(), replace_copy_if(), swap(), swap_range(), unique(),

адресованных парой итераторов, но не модифицирует сами итераторы. unique_copy()

12.5.4. Алгоритмы перестановки

Рассмотрим последовательность из трех символов: {a,b,c}. Для нее существует шесть различных перестановок: abc, acb, bac, bca, cab и cba, лексикографически упорядоченных на основе оператора “меньше”. Таким образом, abc – это первая перестановка, потому что каждый элемент меньше последующего. Следующая перестановка – acb, поскольку в начале все еще находится a – наименьший элемент последовательности. Соответственно перестановки, начинающиеся с b, предшествуют тем, которые начинаются с с. Из bac и bca меньшей является bac, так как последовательность ac лексикографически меньше, чем ca. Если дана перестановка bca, то можно сказать, что предшествующей для нее будет bac, а последующей – cab. Для перестановки abc нет предшествующей, а для cba – последующей.

next_permutation(), prev_permutation()

12.5.5. Численные алгоритмы

Следующие четыре алгоритма реализуют численные операции с контейнером. Для их

использования необходимо включить заголовочный файл <numeric>.

accumulate(), partial_sum(), inner_product(), adjacent_difference()

12.5.6. Алгоритмы генерирования и модификации

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

fill(), fill_n(), for_each(), generate(),generate_n(), transform()

12.5.7. Алгоритмы сравнения