a shot of dev knowledge

Related tags

What is lexicographical_compare() in C++?

The lexicographical_compare(), method of the C++ Algorithm header is used to compare objects (generally.strings). This method helps us determine if the first range [first1, last1) is lexicographically less than the second range [first2, last2). There are two definitions/implementations of the same function:

//First Definition
  template<class Iterator1, class Iterator2>
  bool lexicographical_compare (Iterator1 firststart, Iterator1 
  firstlast,Iterator2 secondstart, Iterator2 secondlast);
//Second Definition
  template<class Iterator1, class Iterator2>
  bool lexicographical_compare (Iterator1 firststart, Iterator1 
  firstlast,Iterator2 secondstart, Iterator2 secondlast, Compare comp);

where:

  • firststart, firstlast, secondstart, and secondlast point to the start and end of the first and second ranges, respectively
  • a user-defined comparison function that takes two input arguments and returns true if the first element is less than the second

Comparison

In the first definition, the function uses the default comparison function and uses the operator < to perform the comparison. In the second definition, the user can pass their own comparison function.

The return type of the function is boolean, and it returns true if the first range is lexicographically lesser than the second range; otherwise, it returns false, even when the two ranges are equal.

The comparison rules observed include:

  1. In two ranges, an element-by-element comparison is performed.

  2. If both ranges are empty, they are lexicographically identical.

  3. If one range is empty and the other is not, then the empty range is lexicographically less than the non-empty range.

  4. The first mismatched element specifies which range is lexicographically larger or smaller than the other.

  5. When one range is a prefix for another, the shorter range is lexicographically smaller.

  6. If two ranges have the same length and contain the same elements, they are lexicographically identical.

Time complexity

The time complexity of the function is linear and is defined as:

2* minimum(lenghtOfFirstRange, lenghtOfSecondRange)

where:

  • lenghtOfFirstRange = firstlast - firststart

  • lenghtOfSecondRange = secondlast - secondstart

Code

Experiment by inputting the two strings in STDIN tab and see how the function works. Input each string followed by the Enter button in the area provided and then execute the code.

#include <iostream>
#include<algorithm> // for lexicographical_compare()
#include <string>
#include <string.h>

using namespace std;

//function to perform comparison and pass in lexicographical_compare()
bool compare(char firstRangeLetter, char secondRangeLetter){
    return toupper(firstRangeLetter) < toupper(secondRangeLetter);
}

int main() {
  
  char firstinput[100];
  char secondinput[100];
  
  cout << "First Input\t";
  cin >> firstinput;
  cout << firstinput << endl;

  cout << "Second Input\t";
  cin >> secondinput;
  cout << secondinput << endl;

   cout << "\n\n--------Using First Function Definition--------\n";
 //First Definition
  if(lexicographical_compare(firstinput, firstinput+strlen(firstinput), secondinput, secondinput+strlen(secondinput))){
        cout << "The first input is lexicographically less than second input\n";    
    }
    else{
        cout << "The first input is not lexicographically less than second input\n";      
    }

 //Second Definition
    cout << "\n--------Using Second Function Definition--------\n";
     if(lexicographical_compare(firstinput, firstinput+strlen(firstinput), secondinput, secondinput+strlen(secondinput),compare)){
        cout << "The first input is lexicographically less than second input\n";    
    }
    else{
        cout << "The first input is not lexicographically less than second input\n";      
    }

}
Enter strings in the stdin tab before executing the code

If the element comparison or the iterator throws an exception, lexicographical_compare() will throw an exception.

Related tags

RELATED COURSES
View all Courses
Related Courses
Related Courses
View all Courses

Keep Exploring