Comparators in STL

A comparator in C++ is a function or function object that defines a custom sorting order. Comparators are commonly used with standard library algorithms like sort, qsort, priority_queue, and others, where the default ordering (usually ascending) is not sufficient, and a custom sorting criterion is needed.

What is a Comparator?

In the context of C++, a comparator is a binary predicate, which means it is a function or function object that takes two arguments (often of the same type) and returns a boolean value. The return value indicates whether the first argument should be ordered before the second. The criteria for ordering can be anything: numerical order, lexicographical order, custom-defined order, etc. For sorting purposes, the function usually returns true if the first argument should come before the second, according to some custom criteria.

Return Value:

• true: Indicates that the first argument should be ordered before the second. In simple if you don't want to do swap return true.
• false: Indicates that the first argument should not be ordered before the second (i.e., it could be equal or greater depending on the logic). In simple if you want to do swap return false.

Why Use Comparators?

• Custom Sorting: Allows you to define how elements are compared, enabling sorting based on specific criteria, such as descending order, sorting by multiple attributes, or sorting complex data structures.
• Flexibility: Provides the flexibility to reuse standard algorithms with different comparison logic without rewriting the algorithms themselves.

Types of Comparators

1. Function Pointers
2. Lambda Expressions
3. Function Objects (Functors)

Let's explore each type with examples.

1️⃣ Function Pointers:

A function pointer can be used as a comparator by defining a function that returns a boolean value indicating the order of two elements.

Example: Sorting Integers in Descending Order:

#include <iostream>
#include <vector>
#include <algorithm>

// Function pointer comparator
bool compareDescending(int a, int b) {
    return a > b; // Sort in descending order
}

int main() {
    std::vector<int> numbers = {5, 2, 8, 1, 3};

    // Using sort with a function pointer comparator
    std::sort(numbers.begin(), numbers.end(), compareDescending);

    for (int num : numbers) {
        std::cout << num << " "; // Output: 8 5 3 2 1
    }
    std::cout << std::endl;

    return 0;
}

Explanation of Comparator Function Logic:

1. Function Definition: bool compareDescending(int a, int b):
   • This function takes two integers a and b as arguments.
2. Comparison Logic:
   • The function returns true if a > b.
   • This means that when std::sort calls this function, if a is greater than b, it will place a before b in the sorted order.
3. Sorting Execution:
   • std::sort uses this comparator function to determine the order of every pair of elements in the vector.
   • For every pair (a, b), it checks if compareDescending(a, b) returns true or false:
     • If true, a is placed before b.
     • If false, a is placed after b.

Detailed Step-by-Step Process

Let's walk through the sorting process step-by-step with the vector {5, 2, 8, 1, 3}.

1. Initial State:
   • The vector is unsorted: {5, 2, 8, 1, 3}.
2. First Iteration (Comparing all elements):
   • Compare 5 and 2: compareDescending(5, 2) returns true (5 > 2). No change needed.
   • Compare 2 and 8: compareDescending(2, 8) returns false (2 < 8). Swap 2 and 8. Vector becomes {5, 8, 2, 1, 3}.
   • Compare 2 and 1: compareDescending(2, 1) returns true (2 > 1). No change needed.
   • Compare 1 and 3: compareDescending(1, 3) returns false (1 < 3). Swap 1 and 3. Vector becomes {5, 8, 2, 3, 1}.
3. Second Iteration (Comparing after the first iteration):
   • Compare 5 and 8: compareDescending(5, 8) returns false (5 < 8). Swap 5 and 8. Vector becomes {8, 5, 2, 3, 1}.
   • Compare 5 and 2: compareDescending(5, 2) returns true (5 > 2). No change needed.
   • Compare 2 and 3: compareDescending(2, 3) returns false (2 < 3). Swap 2 and 3. Vector becomes {8, 5, 3, 2, 1}.
4. Subsequent Iterations:
   • Continue comparing and swapping based on the comparator function until the entire vector is sorted.
5. Final State:
   • The vector is sorted in descending order: {8, 5, 3, 2, 1}.

2️⃣ Lambda Expressions:

Lambda expressions provide a concise way to define comparators inline without needing separate functions. They are often preferred for their simplicity and readability.

Example: Sorting Strings by Length:

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

int main() {
    std::vector<std::string> words = {"apple", "banana", "kiwi", "strawberry"};

    // Using sort with a lambda expression as a comparator
    std::sort(words.begin(), words.end(), [](const std::string& a, const std::string& b) {
        return a.length() < b.length(); // Sort by string length in ascending order
    });

    for (const std::string& word : words) {
        std::cout << word << " "; // Output: kiwi apple banana strawberry
    }
    std::cout << std::endl;

    return 0;
}

Explanation:

• Lambda Expression: [](const std::string& a, const std::string& b) { return a.length() < b.length(); } defines a lambda function that takes two strings and returns true if the first string is shorter than the second.

3️⃣ Function Objects (Functors)

A function object or functor is a class or struct that overloads the operator() to allow an instance of the class to be called as a function. Functors are more flexible than function pointers and lambdas because they can hold state.

Example: Sorting by Custom Rule with a Functor:

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

// Functor comparator
struct CompareByLastChar {
    bool operator()(const std::string& a, const std::string& b) const {
        return a.back() < b.back(); // Compare based on the last character of the strings
    }
};

int main() {
    std::vector<std::string> words = {"apple", "banana", "kiwi", "strawberry"};

    // Using sort with a functor comparator
    std::sort(words.begin(), words.end(), CompareByLastChar());

    for (const std::string& word : words) {
        std::cout << word << " "; // Output: banana apple kiwi strawberry
    }
    std::cout << std::endl;

    return 0;
}

Explanation:

• Functor: The struct CompareByLastChar defines a custom sorting criterion based on the last character of each string.
• Operator Overloading: The operator() function is overloaded to compare the last character of two strings.