I have forgotten
my Password

Or login with:

  • Facebookhttp://facebook.com/
  • Googlehttps://www.google.com/accounts/o8/id
  • Yahoohttps://me.yahoo.com
ComputingStlAlgorithmsMin Max

lexicographical_compare

Returns whether a range is lexicographically less than another range.

Definition

The lexicographical_compare() algorithm is defined in the standard header <algorithm> and in the nonstandard backward-compatibility header <algo.h>.

Interface

#include <algorithm>
template < class InputIterator1, class InputIterator2 >
   bool lexicographical_compare(
      InputIterator1 first1,
      InputIterator1 last1,
      InputIterator2 first2,
      InputIterator2 last2
   );
template < class InputIterator1, class InputIterator2, class BinaryPredicate >
   bool lexicographical_compare(
      InputIterator1 first1,
      InputIterator1 last1, 
      InputIterator2 first2, 
      InputIterator2 last2,
      BinaryPredicate comp
   );

Parameters:
Parameter Description
first1 An input iterator addressing the position of the first element in the first range to be compared
last1 An input iterator addressing the position one past the final element in the first range to be compared
first2 An input iterator addressing the position of the first element in the second range to be compared
last2 An input iterator addressing the position one past the final element in the second range to be compared
comp User-defined predicate function object that defines sense in which one element is less than another. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied

Description

Lexicographical_compare checks if the first range [first1, last1) is lexicographically less than the second range [first2, last2).

The first version compares objects using operator< and the second compares objects using a function object comp.

Lexicographical comparison has the following properties:
  • Two ranges are compared element by element
  • The first mismatching element defines which range is lexicographically less or greater than the other
  • If one range is a prefix of another, the shorter range is lexicographically less than the other
  • If two ranges have equivalent elements and are of the same length, then the ranges are lexicographically equal
  • An empty range is lexicographically less than any non-empty range
  • Two empty ranges are lexicographically equal

Return Value

Returns true if the first range is lexicographically less than the second range; otherwise returns false.

Complexity

The complexity is linear; performs at most 2 * min(last1 - first1, last2 - first2) comparisons.
Example:

Example - lexicographical_compare algorithm
Problem
The following program demonstrates how to use lexicographical_compare() function.
Workings
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
 
using namespace std;
 
// Return whether second element is twice the first
bool twice ( int elem1, int elem2 )
{
   return 2 * elem1 < elem2;
}
 
int main( )
{
   vector <int> v1, v2;
   list <int> L1;
   vector <int>::iterator Iter1, Iter2;
   list <int>::iterator L1_Iter, L1_inIter;
 
   int i;
   for ( i = 0 ; i <= 5 ; i++ )
     v1.push_back( 5 * i );
   int ii;
   for ( ii = 0 ; ii <= 6 ; ii++ )
     L1.push_back( 5 * ii );
 
   int iii;
   for ( iii = 0 ; iii <= 5 ; iii++ )
     v2.push_back( 10 * iii );
 
   cout << "Vector v1 = ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")" << endl;
 
   cout << "List L1 = ( " ;
   for ( L1_Iter = L1.begin( ) ; L1_Iter!= L1.end( ) ; L1_Iter++ )
      cout << *L1_Iter << " ";
   cout << ")" << endl;
 
   cout << "Vector v2 = ( " ;
   for ( Iter2 = v2.begin( ) ; Iter2 != v2.end( ) ; Iter2++ )
      cout << *Iter2 << " ";
      cout << ")" << endl;
 
   // Self lexicographical_comparison of v1 under identity
   bool result1;
   result1 = lexicographical_compare (v1.begin( ), v1.end( ),
                  v1.begin( ), v1.end( ) );
   if ( result1 )
      cout << "Vector v1 is lexicographically_less than v1." << endl;
   else
      cout << "Vector v1 is not lexicographically_less than v1." << endl;
 
   // lexicographical_comparison of v1 and L2 under identity
   bool result2;
   result2 = lexicographical_compare (v1.begin( ), v1.end( ),
                  L1.begin( ), L1.end( ) );
   if ( result2 )
      cout << "Vector v1 is lexicographically_less than L1." << endl;
   else
      cout << "Vector v1 is lexicographically_less than L1." << endl;
 
   bool result3;
   result3 = lexicographical_compare (v1.begin( ), v1.end( ),
                  v2.begin( ), v2.end( ), twice );
   if ( result3 )
      cout << "Vector v1 is lexicographically_less than v2 "
           << "under twice." << endl;
   else
      cout << "Vector v1 is not lexicographically_less than v2 "
           << "under twice." << endl;
  return 0;
}
Solution
Output:

Vector v1 = ( 0 5 10 15 20 25 )
List L1 = ( 0 5 10 15 20 25 30 )
Vector v2 = ( 0 10 20 30 40 50 )
Vector v1 is not lexicographically_less than v1.
Vector v1 is lexicographically_less than L1.
Vector v1 is not lexicographically_less than v2 under twice.
References