Mastering Custom Comparators for Sorting Vectors in C++

In C++, the std::sort() function is a powerful tool in the Standard Template Library (STL) that, by default, arranges elements in a given range, such as a vector, in ascending order. However, the true flexibility of std::sort() lies in its ability to utilize custom comparators. A custom comparator is essentially a function that dictates the order in which elements should be sorted, allowing you to define sorting logic beyond the default ascending order. This article delves into how to leverage custom comparators to sort vectors in C++, providing a comprehensive guide with examples.

Consider scenarios where you need to sort data based on specific criteria:

Example 1: Sorting numbers in descending order.

Input: v = {5, 11, 9, 7, 4}
Output: 11 9 7 5 4
Explanation: The vector is sorted from largest to smallest.

Example 2: Sorting numbers based on their remainder when divided by 3.

Input: v = {5, 9, 6, 4, 12, 3}
Output: 9 6 12 3 4 5
Explanation: Elements are arranged according to the ascending order of their remainders after division by 3.

C++ offers three primary methods for declaring custom comparator functions for std::sort(): as a traditional function, as a lambda expression, and as a function object (functor). Let’s explore each of these methods in detail.

Sorting with a Traditional Function Comparator

The most straightforward approach to defining a custom comparator is by using a traditional function. This function must accept two arguments of the same type as the vector elements and return a boolean value. The crucial aspect of this function is its return value: it should return true if the first argument should precede the second in the sorted order, and false otherwise. In simpler terms, it returns true if the elements are already in the desired relative order, and false if they need to be swapped to achieve the correct order.

Example: Sorting in Descending Order using a Traditional Function

// C++ program to sort a vector using a
// custom comparator as traditional function
#include <bits/stdc++.h>
using namespace std;

// Comparator function for descending order
bool compareDescending(int a, int b) {
    // Return true if 'a' should come before 'b' in descending order
    return a > b;
}

int main() {
    vector<int> v = {5, 11, 9, 7, 4};

    // Sort the vector 'v' in descending order using 'compareDescending'
    sort(v.begin(), v.end(), compareDescending);

    for (int i : v) {
        cout << i << " ";
    }
    return 0;
}

Output:

11 9 7 5 4

In this example, compareDescending is our custom comparator function. It takes two integers, a and b, and returns true if a is greater than b. When used with std::sort(), this comparator ensures that the elements are arranged from largest to smallest, resulting in a descending order sort.

Time Complexity: O(n * log n), where n is the number of elements in the vector, which is the standard time complexity for std::sort().
Auxiliary Space: O(log n) due to the recursive nature of typical sort implementations like introsort used in std::sort.

Sorting with a Lambda Expression Comparator

C++ also allows you to define custom comparators using lambda expressions. Lambda expressions are concise, anonymous functions that can be defined directly within the std::sort() function call. They are particularly useful for comparators that are simple and used only in a specific context, avoiding the need to declare a separate named function. The lambda expression for a comparator should have the same signature as a traditional comparator function: taking two parameters and returning a boolean.

Example: Sorting in Descending Order using a Lambda Expression

// C++ program to sort a vector using a custom
// comparator as lambda function
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {5, 11, 9, 7, 4};

    // Sort the vector 'v' in descending order using a lambda comparator
    sort(v.begin(), v.end(), [](int a, int b) {
        return a > b;
    });

    for (int i : v) {
        cout << i << " ";
    }
    return 0;
}

Output:

11 9 7 5 4

Here, the lambda expression [](int a, int b) { return a > b; } is passed directly as the third argument to std::sort(). This lambda function performs the same comparison as our compareDescending function in the previous example, achieving the same descending order sort. Lambda expressions offer a more compact syntax for simple comparators, making the code cleaner and more readable when the comparator logic is straightforward.

Time Complexity: O(n * log n)
Auxiliary Space: O(log n)

Sorting with a Function Object (Functor) Comparator

The third method involves using a function object, also known as a functor, as a custom comparator. A functor is essentially a class or struct that overloads the operator(). When an object of this class is used in a function-call context, it behaves like a function. For custom comparators, the operator() overload should take two arguments and return a boolean value, adhering to the same comparator signature as traditional functions and lambda expressions. Functors are particularly beneficial when the comparator logic is more complex, requires maintaining state, or needs to be reused across different parts of your code.

Example: Sorting by Remainder using a Function Object (Functor)

// C++ program to sort a vector using custom
// comparator as function object
#include <bits/stdc++.h>
using namespace std;

// Custom comparator as a functor
struct RemainderComparator {
    bool operator()(int a, int b) {
        int remainderA = a % 3;
        int remainderB = b % 3;
        return remainderA < remainderB;
    }
};

int main() {
    vector<int> v = {5, 9, 6, 4, 12, 3};

    // Sort vector 'v' based on remainders when divided by 3
    sort(v.begin(), v.end(), RemainderComparator());

    for (int i : v) {
        cout << i << " ";
    }
    return 0;
}

Output:

9 6 12 3 4 5

In this example, RemainderComparator is a functor. Its operator() overload calculates the remainder of each number when divided by 3 and compares these remainders. std::sort() then uses this functor to arrange the vector elements in ascending order of their remainders. Functors provide a way to encapsulate more elaborate comparison logic within a class, enhancing code organization and reusability.

Time Complexity: O(n * log n)
Auxiliary Space: O(log n)

Conclusion

Custom comparators are indispensable for achieving flexible sorting in C++. Whether you choose to implement your comparator as a traditional function for simplicity, a lambda expression for conciseness in localized sorting, or a functor for more complex and reusable comparison logic, understanding these techniques is crucial for effective C++ programming. By mastering custom comparators with std::sort(), you gain fine-grained control over how your data is ordered, enabling you to solve a wider range of sorting problems efficiently and elegantly.