C++ algorithm: std::lexicographical_compare Function Template

C++ std::lexicographical_compare

The std::lexicographical_compare function in C++ compares two ranges lexicographically. A range is considered lexicographically smaller if it is a prefix of the other or if the first mismatched element in the range is smaller than the corresponding element in the other range. This function is often used to compare strings or to compare containers.

---

Syntax of std::lexicographical_compare

template <class InputIterator1, class InputIterator2>
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
                              InputIterator2 first2, InputIterator2 last2);

template <class InputIterator1, class InputIterator2, class Compare>
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
                              InputIterator2 first2, InputIterator2 last2,
                              Compare comp);

Parameters of std::lexicographical_compare

Parameter	Description
first1, last1	Input iterators defining the first range to compare.
first2, last2	Input iterators defining the second range to compare.
comp (optional)	A binary comparison function that defines the criteria for comparison. Defaults to <.

---

Return Value of std::lexicographical_compare

Returns true if the first range is lexicographically less than the second range, and false otherwise.

---

Examples for std::lexicographical_compare

Example 1: Basic Usage of std::lexicographical_compare

This example demonstrates comparing two arrays lexicographically.

Program

#include <iostream>
#include <algorithm>

int main() {
    char arr1[] = {'a', 'b', 'c'};
    char arr2[] = {'a', 'b', 'd'};

    bool result = std::lexicographical_compare(std::begin(arr1), std::end(arr1), std::begin(arr2), std::end(arr2));

    if (result) {
        std::cout << "Array 1 is lexicographically less than Array 2." << std::endl;
    } else {
        std::cout << "Array 1 is not lexicographically less than Array 2." << std::endl;
    }

    return 0;
}

Explanation:

1. Include the necessary headers: The program includes <iostream> for input/output operations and <algorithm> for the std::lexicographical_compare function.
2. Define two character arrays:
   • arr1: Contains the characters {'a', 'b', 'c'}.
   • arr2: Contains the characters {'a', 'b', 'd'}.
3. Use std::lexicographical_compare to compare the arrays:
   • The function compares the elements of arr1 and arr2 lexicographically (dictionary order).
   • It takes four arguments:
     • std::begin(arr1): Pointer to the beginning of arr1.
     • std::end(arr1): Pointer to the end of arr1.
     • std::begin(arr2): Pointer to the beginning of arr2.
     • std::end(arr2): Pointer to the end of arr2.
   • The function returns true if arr1 is lexicographically less than arr2, and false otherwise.
4. Store the result: The result of the comparison is stored in the result variable (a boolean).
5. Display the result:
   • If result is true, the program outputs: "Array 1 is lexicographically less than Array 2."
   • If result is false, the program outputs: "Array 1 is not lexicographically less than Array 2."

Output:

Array 1 is lexicographically less than Array 2.

Example 2: Using a Custom Comparison Function for std::lexicographical_compare

This example demonstrates comparing two arrays using a custom comparison function:

Program

#include <iostream>
#include <algorithm>

bool case_insensitive_compare(char a, char b) {
    return std::tolower(a) < std::tolower(b);
}

int main() {
    char arr1[] = {'A', 'b', 'c'};
    char arr2[] = {'a', 'B', 'D'};

    bool result = std::lexicographical_compare(std::begin(arr1), std::end(arr1), std::begin(arr2), std::end(arr2), case_insensitive_compare);

    if (result) {
        std::cout << "Array 1 is lexicographically less than Array 2 (case-insensitive)." << std::endl;
    } else {
        std::cout << "Array 1 is not lexicographically less than Array 2 (case-insensitive)." << std::endl;
    }

    return 0;
}

Explanation:

1. Define a custom comparison function:
   • The function case_insensitive_compare compares two characters in a case-insensitive manner by converting them to lowercase using std::tolower.
   • It returns true if the lowercase version of the first character is less than the second, and false otherwise.
2. Call std::lexicographical_compare:
   • This function compares arr1 and arr2 lexicographically (dictionary order).
   • The arguments include:
     • std::begin(arr1): Pointer to the beginning of arr1.
     • std::end(arr1): Pointer to the end of arr1.
     • std::begin(arr2): Pointer to the beginning of arr2.
     • std::end(arr2): Pointer to the end of arr2.
     • case_insensitive_compare: The custom comparison function to perform a case-insensitive comparison.
   • The function returns true if arr1 is lexicographically less than arr2 based on the case-insensitive comparison, and false otherwise.
3. Display the result:
   • If result is true, the program outputs: "Array 1 is lexicographically less than Array 2 (case-insensitive)."
   • If result is false, the program outputs: "Array 1 is not lexicographically less than Array 2 (case-insensitive)."

Output:

Array 1 is lexicographically less than Array 2 (case-insensitive).

---

Exception Handling in std::lexicographical_compare

The std::lexicographical_compare function does not throw exceptions itself. However, the comparison function passed as an argument may throw exceptions, which can be caught and handled appropriately.

Example 1: Exception in Custom Comparison Function

This example demonstrates how exceptions in a custom comparison function are handled:

#include <iostream>
#include <algorithm>
#include <stdexcept>

bool faulty_compare(char a, char b) {
    if (a == 'x' || b == 'x') {
        throw std::runtime_error("Comparison involving 'x' is not allowed.");
    }
    return a < b;
}

int main() {
    char arr1[] = {'a', 'b', 'x'};
    char arr2[] = {'a', 'b', 'd'};

    try {
        bool result = std::lexicographical_compare(std::begin(arr1), std::end(arr1), std::begin(arr2), std::end(arr2), faulty_compare);
        std::cout << "Comparison result: " << result << std::endl;
    } catch (const std::exception& e) {
        std::cerr << "Exception caught: " << e.what() << std::endl;
    }

    return 0;
}

Output:

Exception caught: Comparison involving 'x' is not allowed.