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

Алгоритмы, получающие один параметр beg2, подразумевают , что последовательность, начинающаяся с элемента, указанного итератором beg2, имеет такой же размер, как и диапазон, обозначенный итераторами begи end.

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

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

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, вполне применимы со списками, но ценой производительности. Эти алгоритмы меняют элементы в исходной последовательности. Список может "поменять" свои элементы, поменяв ссылки на элементы, а не перемещая значения этих элементов. В результате специфические для списка версии этих алгоритмов могут обеспечить намного лучшую производительность, чем соответствующие обобщенные версии.

Эти специфические для списка функции приведены в табл. 10.6. В ней нет обобщенных алгоритмов, которые получают соответствующие итераторы и выполняются одинаково эффективно как для других контейнеров, так и для контейнеров listи forward_list.

Предпочтительней использовать алгоритмы-члены классов listи forward_list, а не их обобщенные версии.

Таблица 10.6. Алгоритмы-члены классов listи forward_list

Алгоритм-член splice()

Типы списков определяют также алгоритм splice(), описанный в табл. 10.7. Этот алгоритм специфичен для списочных структур данных. Следовательно, обобщенная версия этого алгоритма не нужна.