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, andsecondlastpoint 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:
-
In two ranges, an element-by-element comparison is performed.
-
If both ranges are empty, they are lexicographically identical.
-
If one range is empty and the other is not, then the empty range is lexicographically less than the non-empty range.
-
The first mismatched element specifies which range is lexicographically larger or smaller than the other.
-
When one range is a prefix for another, the shorter range is lexicographically smaller.
-
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 Definitionif(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 Definitioncout << "\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 the input below
If the element comparison or the iterator throws an exception, lexicographical_compare() will throw an exception.
RELATED TAGS
CONTRIBUTOR
Shanzay Gauhar