if (lexicographical compare(a, a+4, b, b+4))

cout << Lexicographically, a precedes b.\n ;

if (lexicographical compare(b, b+4, a, a+4, greater<int>())) cout <<

Using the greater-than relation, we find:\n b lexicographically precedes a.\n ; return 0;

Результат работы программы показан ниже:

а: 1 3 8 2 Ь: 1 3 9 1

Lexicographically, а precedes b.

Using the greater-than relation, we find:

b lexicographically precedes a.

Если последовательности имеют разную длину, отсутствующий в последовательности элемент предшествует любому присутствующему элементу второй последовательности; например: {1,2} лексикографически предшествует {1,2, -5}, вне зависимости от оператора сравнения.

7.3.12. Генераторы перестановок

bool nextermutation

(Bidirectionallterator first, Bidirectionallterator last); bool next permutation

(Bidirectionallterator first, Bidirectionallterator last. Compare comp); bool prev permutation

(Bidirectionallterator first, Bidirectionallterator last); bool prev per/nutation

(Bidirectionallterator first, Bidirectionallterator last. Compare comp);

Алгоритм next permutation порождает очередную перестановку последовательности. Последовательность вызовов этого алгоритма порождает, если это возможно, перестановки в лексикографическом порядке. Возвращаемое значение типа bool показывает, существует ли следующая перестановка. Это поведение алгоритма становится ясным из следующей программы; она также показывает, как алгоритм prevpermutation порождает предшествующую перестановку:

permgen.срр: Генератор перестановок порождает все перестановки последовательности 12 3.

iinclude <iostream> iinclude <algorithin> using namespace std;

int main()

{ int a[3] = {1, 2, 3), k;

cout Six successive calls to next permutation.\n

Situation before call and value returned by

call:\n ; for (k=0; k<6; k++)

{ copy(a, a+3, ostream iterator<int>(cout, )); bool b = next permutation(a, a+3); cout (b ? true : false ) << endl;

cout <<

Three successive calls to prev permutation.\n Situation before call and value returned by call:\n ; for (k=0; k<3; k++)

{ copy(a, a+3, ostream iterator<int>(cout, )); bool b = prev permutation(a, a+3); cout (b ? true : false ) endl;

return 0;

Начиная с последовательности {1,2,3}, программа выводит содержимое массива а непосредственно перед вызовом функции next permutation. Всего проходит шесть таких вызовов. Первый вызов возвращает true и изменяет последовательность, содержащуюся в а, на {1, 3, 2}, второй вызов также возвращает true и порождает последовательность {2,1,3} и т. д. Как видно из приведенного ниже вывода, перестановки появляются в лексикографическом порядке. Когда а = {3,2,1}, шестой вызов функции next permutation возвращает fabe и помещает в массив исходную последовательность {1, 2, 3}. Функция prev permutation работает в обратном порядке. Она возвращает false, когда изменяет содержимое массива с {1, 2,3} на {3, 2,1}, и true при переходе от {3, 2, 1} к {3,1, 2}, от {3,1, 2} к {2, 3, 1} и т. д.:

Six successive calls to next permutation. Situation before call and value returned by call:

12 3 true

13 2 true 2 13 true 2 3 1 true

3 12 true 3 2 1 false

Three successive calls to prev permutation. Situation before call and value returned by call: 1 2 3 false 3 2 1 true 3 12 true

Кроме рассмотренных нами существуют версии функций next permutation и prev permutation, которые имеют дополнительный параметр для задания операции сравнения.

7.4. Обобщенные численные алгоритмы

Чтобы использовать алгоритмы, обсуждаемые в этом разделе, мы должны написать в программе

♦include <numeric>

если работаем с версией STL, соответствующей проекту стандарта С++. Для HP STL необходимо заменить эту строчку на следующую:

♦include <algo.h>

7.4.1. Накопление

Т accumulate

(Inputlterator first, Inputlterator last, T init); T accumulate

(Inputlterator first, Inputlterator last, T init, BinaryFunction binary op);

В разделе 2.1 мы обсуждали алгоритм accumulate (суммировать, накопить), используя в качестве примера программы accuml.cpp, accuml.cpp и асситЗ.срр. Вспомним, что можно использовать этот алгоритм не только для вычисления суммы последовательности, но и для другого накопления значений элементов, как показано в программах ассит2.срр и асситЗ.срр. Стоит также помнить, что накопленное значение добавляется к значению третьего аргумента.

7.4.2. Скалярное произведение

Т inner product

(Inputlteratorl firstl, Inputlteratorl lastl, InputIterator2 first2, T init); T inner product

(Inputlteratorl firstl, Inputlteratorl lastl, InputIterator2 first2, T init, BinaryFunctionl binary opl, BinaryFunction2 binary op2);