Алгоритм lexicographical_compare()

Алгоритм lexicographical_compare()

template class InputIterator1, class InputIterator2

bool

lexicographical_compare(

InputIterator1 first1, InputIterator1 last1,

InputIterator1 first2, InputIterator2 last2 );

template class InputIterator1, class InputIterator2,

class Compare

bool

lexicographical_compare(

InputIterator1 first1, InputIterator1 last1,

InputIterator1 first2, InputIterator2 last2,

Compare comp );

lexicographical_compare() сравнивает соответственные пары элементов из двух последовательностей, ограниченных диапазонами [first1,last1) и [first2,last2). Сравнение продолжается, пока не будет найдена первая пара различных элементов, не достигнута пара [last1,last2] или хотя бы один из элементов last1 или last2 (если последовательности имеют разные длины). При обнаружении первой пары различных элементов алгоритм возвращает:

если меньше элемент первой последовательности, то true, иначе false;

если last1 достигнут, а last2 нет, то true;

если last2 достигнут, а last1 нет, то false;

если достигнуты и last1, и last2 (т.е. все элементы одинаковы), то false. Иными словами, первая последовательность лексикографически не меньше второй.

Например, даны такие последовательности:

string arr1[] = { "Piglet", "Pooh", "Tigger" };

string arr2[] = { "Piglet", "Pooch", "Eeyore" };

В них первая пара элементов одинакова, а вторая различна. Pooh считается больше, чем Pooch, так как c лексикографически меньше h (такой способ сравнения применяется при составлении словарей). В этом месте алгоритм заканчивается (третья пара элементов не сравнивается). Результатом сравнения будет false.

Во втором варианте алгоритма вместо оператора сравнения используется предикатный объект:

#include algorithm

#include list

#include string

#include assert.h

#include iostream.h

class size_compare {

public:

bool operator()( const string &a, const string &b ) {

return a.length() = b.length();

}

};

int main()

{

string arr1[] = { "Piglet", "Pooh", "Tigger" };

string arr2[] = { "Piglet", "Pooch", "Eeyore" };

bool res;

// на втором элементе получаем false

// Pooch меньше Pooh

// на третьем элементе тоже получили бы false

res = lexicographical_compare( arr1, arr1+3,

arr2, arr2+3 );

assert( res == false );

// получаем true: длина каждого элемента ilist2

// меньше либо равна длине соответственного

// элемента ilist1

list string, allocator ilist1( arr1, arr1+3 );

list string, allocator ilist2( arr2, arr2+3 );

res = lexicographical_compare(

ilist1.begin(), ilist1.end(),

ilist2.begin(), ilist2.end(), size_compare() );

assert( res == true );

cout "ok: lexicographical_compare завершился успешно! ";

}