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

У алгоритмов, получающих значение элемента, обычно есть вторая (не перегруженная) версия, получающая предикат (см. раздел 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.5.3

Упражнение 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);

10.6. Алгоритмы, специфические для контейнеров

В отличие от других контейнеров, контейнеры 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 

Эти функции возвращают void. lst.merge(lst2) lst.merge(lst2, comp) Объединяет элементы списков lst2 и lst. Оба списка должны быть отсортированы. Элементы из списка lst2 удаляются, и после объединения список lst2 оказывается пустым. Возвращает тип void. В первой версии используется оператор <, а во второй — указанная функция сравнения lst.remove(val) lst.remove_if(pred) При помощи функции lst.erase() удаляет каждый элемент, значение которого равно переданному значению, или для которого указанный унарный предикат возвращает значение, отличное от нуля lst.reverse() Меняет порядок элементов списка lst на обратный lst.sort() lst.sort(comp) Сортирует элементы списка lst, используя оператор < или другой заданный оператор сравнения lst.unique() lst.unique(pred) При помощи функции lst.erase() удаляет расположенные рядом элементы с одинаковыми значениями. Вторая версия использует заданный бинарный предикат Алгоритм-член splice()

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

Таблица 10.7. Аргументы алгоритма-члена splice() классов list и forward_list

lst.splice(аргументы) или flst.splice_after(аргументы) (p, lst2) p — итератор на элемент списка lst или итератор перед элементом списка flst. Перемещает все элементы из списка lst2 в список lst непосредственно перед позицией p или непосредственно после в списке flst. Удаляет элементы из списка lst2. Список lst2 должен иметь тот же тип, что и lst (или flst), и не может быть тем же списком (p, lst2, p2) p2 — допустимый итератор в списке lst2. Перемещает элемент, обозначенный итератором p2, в список lst или элемент после обозначенного итератором p2 в списке flst. Список lst2 может быть тем же списком, что и lst или flst (p, lst2, b, е) b и е обозначают допустимый диапазон в списке lst2. Перемещает элементы в заданный диапазон из списка lst2. Списки lst2 и lst (или flst) могут быть тем же списком, но итератор p не должен указывать на элемент в заданном диапазоне Специфические для списка функции, изменяющие контейнер

Большинство специфических для списков алгоритмов подобны (но не идентичны) их обобщенным аналогам. Но кардинально важное различие между специфическими и обобщенными версиями в том, что специфические версии изменяют базовый контейнер. Например, специфическая версия алгоритма remove() удаляет указанные элементы. Специфическая версия алгоритма unique() удаляет второй и последующий дубликаты элемента.

Аналогично алгоритмы merge() и splice() деструктивны к своим аргументам. Например, обобщенная версия функции merge() запишет объединенную последовательность по заданному итератору назначения; две исходных последовательности останутся неизменны. Специфическая для списка функция merge() разрушит заданный список — элементы будут удаляться из списка аргумента по мере их объединения в объект, для которого был вызван аргумент merge(). После объединения элементы из обоих списков продолжают существовать, но принадлежат уже одному списку.

Упражнения раздела 10.6

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

Резюме

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