Стенли Липпман - Язык программирования C++. Пятое издание

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

unique(beg, end); // использует для сравнения элементов оператор ==

unique(beg, end, comp); // использует для сравнения элементов

// предикат comp

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

У алгоритмов, получающих значение элемента, обычно есть вторая (не перегруженная) версия, получающая предикат (см. раздел 10.3.1) вместо значения. Получающие предикат алгоритмы имеют суффикс _if:

find(beg, end, val); // найти первый экземпляр val в исходном диапазоне

find_if(beg, end, pred); // найти первый экземпляр, для

// которого pred возвращает true

Оба алгоритма находят в исходном диапазоне первый экземпляр заданного элемента. Алгоритм find()ищет указанное значение, а алгоритм find_if()— значение, для которого предикат predвозвратит значение, отличное от нуля.

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

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

reverse(beg, end); // обратить порядок элементов в исходном диапазоне

reverse_copy(beg, end, dest); // скопировать элементы по назначению в

// обратном порядке

Некоторые алгоритмы предоставляют и версии _copy, и _if. Эти версии получают и итератор назначения, и предикат:

// удаляет нечетные элементы из v1

remove_if(v1.begin(), v1.end(),

[](int i) { return i % 2; });

// копирует только четные элементы из v1 в v2; v1 неизменен

remove_copy_if(v1.begin(), v1.end(), back_inserter(v2),

[](int i) { return i % 2; });

Для определения нечетности элемента оба вызова используют лямбда-выражение (см. раздел 10.3.2). В первом случае нечетные элементы удаляются из самой исходной последовательности. Во втором не нечетные (четные) элементы копируются из исходного диапазона в вектор v2.

Упражнение 10.41. Исходя только из имен алгоритмов и их аргументов, опишите действия, выполняемые каждым из следующих библиотечных алгоритмов:

replace(beg, end, old_val, new_val);

replace_if(beg, end, pred, new_val);

replace_copy(beg, end, dest, old_val, new_val);

replace_copy_if(beg, end, dest, pred, new_val);

В отличие от других контейнеров, контейнеры listи forward_listопределяют несколько алгоритмов в качестве членов. В частности, тип listопределяют собственные версии алгоритмов sort(), merge(), remove(), reverse()и unique(). Обобщенная версия алгоритма sort()требует итераторов произвольного доступа. В результате она не может использоваться с контейнерами listи forward_list, поскольку эти типы предоставляют двунаправленные и прямые итераторы соответственно.

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