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

Для каждого описанного выше варианта перестановки можно выяснить, какой из них должен располагаться прежде, а какие после него. Например, варианте перестановки bca можно сказать, что предыдущим для нее будет вариант bac, а следующим — cab. Для варианта abc нет предыдущего, а для варианта cba — последующего варианта перестановки.

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

Для осуществления перестановки нужна возможность перебора последовательности вперед и назад, поэтому им требуются двунаправленные итераторы.

is_permutation(beg1, end1, beg2)

is_permutation(beg1, end1, beg2, binaryPred)

Алгоритмы возвращают значение true, если во второй последовательности есть вариант перестановки с тем же набором элементов, что и в первой последовательности, для которой элементы в варианте перестановки и в исходной последовательности равны. Первая версия сравнивает элементы, используя оператор ==; вторая использует заданный предикат binaryPred.

next_permutation(beg, end)

next_permutation(beg, end, comp)

Если последовательность уже находится в последнем варианте перестановки, алгоритм next_permutation() переупорядочивает последовательность так, чтобы она соответствовала самой младшей версии, и возвращает значение false. В противном случае последовательность преобразуется в следующий вариант перестановки и возвращает значение true. Первая версия использует для сравнения элементов оператор < типа элемента, а вторая — указанную функцию сравнения.

prev_permutation(beg, end)

prev_permutation(beg, end, comp)

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

А.2.8. Алгоритмы набора для отсортированных последовательностей

Алгоритмы набора реализуют присущие набору операции, применяемые для отсортированной последовательности. Не следует путать эти алгоритмы с функциями библиотечного контейнера set (набор). Они обеспечивают присущее набору поведение на базе обычного последовательного контейнера (например, vector, list и т.д.) или другой последовательности (например, потока ввода).

Поскольку эти алгоритмы обрабатывают элементы последовательно, им требуются итераторы ввода. За исключением алгоритма includes всем им необходим итератор вывода. Алгоритмы возвращают итератор dest, увеличенный так, чтобы указывать на следующий элемент после последнего записанного.

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

includes(beg, end, beg2, end2)

includes(beg, end, beg2, end2, comp)

Возвращает значение true, если каждый элемент во второй последовательности содержится в исходной последовательности. В противном случае возвращает значение false.

set_union(beg, end, beg2, end2, dest)

set_union(beg, end, beg2, end2, dest, comp)

Создает сортируемую последовательность элементов, которые находятся в обеих последовательностях. Элементы, которые находятся в обеих последовательностях, записываются в указанную итератором dest результирующую последовательность в одном экземпляре.

set_intersection(beg, end, beg2, end2, dest)

set_intersection(beg, end, beg2, end2, dest, comp)

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

set_difference(beg, end, beg2, end2, dest)

set_difference(beg, end, beg2, end2, dest, comp)

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

set_symmetric_difference(beg, end, beg2, end2, dest)

set_symmetric_difference(beg, end, beg2, end2, dest, comp)

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

А.2.9. Минимальные и максимальные значения

Эти алгоритмы используют при сравнении либо оператор < для типа элемента, либо заданную функцию сравнения. Алгоритмы первой группы работают со значениями, а не с последовательностями. Алгоритмы второй группы получают последовательность, обозначенную итераторами ввода.

min(val1, val2)

min(val1, val2, comp)

min(init_list)

min(init_list, comp)

max(val1, val2)

max(val1, val2, comp)

max(init_list)

max(init_list, comp)

Эти алгоритмы возвращают минимум или максимум значений val1 и val2 либо значений из списка initializer_list. Тип аргументов должен точно совпадать. Аргументы и тип возвращаемого значения являются ссылками на константы, а значит, объекты не копируются.

minmax(val1, val2)

minmax(val1, val2, comp)

minmax(init_list)

minmax(init_list, comp)

Возвращают пару (см. раздел 11.2.3), член first которой содержит меньшее из предоставленных значений, а член second — большее. Версия со списком initializer_list возвращает пару, член first которой содержит наименьшее значение в списке, a second — наибольшее.

min_element(beg, end)

min_element(beg, end, comp)

max_element(beg, end)

max_element(beg, end, comp)

minmax_element(beg, end)

minmax_element(beg, end, comp)

Алгоритмы min_element() и max_element() возвращают итераторы на наименьший и наибольший элементы в исходной последовательности соответственно. Алгоритм minmax_element возвращает пару, член first которой содержит наименьший элемент, а член second — наибольший.

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

lexicographical_compare(beg1, end1, beg2, end2)

lexicographical_compare(beg1, end1, beg2, end2, comp)

Алгоритм возвращает значение true, если первая последовательность лексикографически меньше второй. В противном случае возвращается значение false. Если одна последовательность короче второй и все ее элементы совпадают с соответствующими элементами более длинной последовательности, то более короткая последовательность лексикографически меньше. Если размер последовательностей совпадает и совпадают соответствующие элементы, то ни одна из них лексикографически не меньше другой.

А.2.10. Числовые алгоритмы

Числовые алгоритмы определены в заголовке numeric. Этим алгоритмам требуются итераторы ввода; если алгоритм осуществляет запись в вывод, он использует итератор вывода для получателя.

accumulate(beg, end, init)

accumulate(beg, end, init, binaryOp)

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

inner_product(beg1, end1, beg2, init)

inner_product(beg1, end1, beg2, init, binOp1, binOp2)

Возвращает сумму элементов, полученных как произведение двух последовательностей. Обе последовательности обрабатываются совместно и элементы из каждой последовательности умножаются. Результат умножения суммируется. Исходное значение суммы определяет init. Тип init определяет тип возвращаемого значения.

Первая версия использует операторы умножения (*) и сложения (+) элементов. Вторая версия применяет заданные бинарные операторы, используя первый оператор вместо суммы и второй вместо умножения.

partial_sum(beg, end, dest)

partial_sum(beg, end, dest, binaryOp)

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

adjacent_difference(beg, end, dest)

adjacent_difference(beg, end, dest, binaryOp)

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