Custom comparators with lambda for sort/PQ
Scenario
You have a `std::vector<Player>` where `Player` is a struct containing a name and a score. You call `std::sort(players.begin(), players.end())`. The compiler outputs 200 lines of incomprehensible template error garbage.
How do you teach `std::sort` how to compare two custom objects?
Mental model
A Lambda is a disposable, nameless function you write directly inline. A custom comparator is like handing the sorting robot a rulebook: 'When looking at A and B, return true if A should strictly be placed before B.'
STL algorithms and containers rely on the `<` operator by default to sort elements. If your object doesn't have an `operator<`, or if you want to sort by a different rule (e.g., descending order, or sorting by string length), you must provide a Custom Comparator. In modern C++, this is almost exclusively done using Lambda Expressions.
Explanation
**Lambda Basics:**
A lambda expression is an anonymous function defined inline.
Syntax: `[captures] (parameters) { body }`
- **[ ]** (Capture clause): Defines what outside variables the lambda can access.
- **( )** (Parameters): The inputs to the lambda.
- **{ }** (Body): The logic.
**Customizing std::sort:**
`std::sort` takes a 3rd argument: a callable object that takes two arguments (A and B) and returns `true` if A should be placed **strictly before** B.
For example, to sort descending: `std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; });`
To handle tie-breakers (multi-level sorting), you simply add conditional logic: `if (a.score != b.score) return a.score > b.score; return a.name < b.name;`.
**Customizing std::priority_queue:**
Priority Queues are trickier because the comparator is part of the *type signature*. By default, it's a Max-Heap (uses `std::less`). To make a Min-Heap (smallest at top), you use the built-in `std::greater`. If you need a custom struct PQ, you typically pass a `decltype` of your lambda as the template argument, and pass the lambda itself into the constructor.
**Real-world Engineering:**
Lambdas revolutionized C++. They replaced writing dozens of one-off, polluting structs just to satisfy a sorting requirement. You will use lambdas constantly when filtering vectors (`std::erase_if`), sorting API responses by various JSON fields, or configuring priority queues for A* pathfinding.
Code examples
Sorting with Lambdas
#include <vector>
#include <algorithm>
#include <string>
struct Player {
std::string name;
int score;
};
int main() {
std::vector<Player> players = {{"Alice", 50}, {"Bob", 90}, {"Charlie", 10}};
// Sort descending by score using a lambda.
// Returns true if 'a' should come BEFORE 'b'.
std::sort(players.begin(), players.end(), [](const Player& a, const Player& b) {
return a.score > b.score;
});
// players is now: Bob (90), Alice (50), Charlie (10)
return 0;
}Passing `const Player&` avoids expensive copies. Returning `a.score > b.score` tells the sort algorithm to put higher scores first.
Min-Heap Priority Queue
#include <queue>
#include <vector>
int main() {
// Standard PQ is a Max-Heap.
// To make a Min-Heap, we must specify the container (vector)
// and provide the std::greater comparator.
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
minHeap.push(10);
minHeap.push(2);
minHeap.push(50);
// Top is now 2, not 50.
return 0;
}`std::greater` is a built-in functor that reverses the default `<` comparison, turning the Max-Heap into a Min-Heap.
Key points
- Lambdas are inline rules: Use `[](const Type& a, const Type& b) { return ...; }` to inject custom logic into STL algorithms.
- Never return true for equality: Comparators must use strict inequalities (`<` or `>`). Never use `<=` or `>=`.
Common mistakes
- Returning true for equal elements (Strict Weak Ordering): A comparator must return `true` ONLY if `a` is strictly placed before `b`. If `a` and `b` are equal, it MUST return `false`. If you write `return a >= b;`, `std::sort` will invoke Undefined Behavior (often crashing with a segmentation fault) because it violates the mathematical rules of "Strict Weak Ordering".
Recall questions
- What does a custom comparator function need to return for `std::sort`?
- What are the three parts of a basic C++ lambda expression signature?
- What happens if your custom comparator returns `true` when the two elements are exactly equal?
Questions & answers
An interviewer asks you to sort an array of strings by their length (shortest to longest). How do you do this using `std::sort`?
You provide a lambda comparator: `std::sort(vec.begin(), vec.end(), [](const string& a, const string& b) { return a.length() < b.length(); });`
Approach: Apply lambdas to override default sorting behavior (which would sort strings alphabetically).
A team member wants to sort a vector of `std::pair<int, int>` such that the first elements are ascending, but if they are equal, the second elements are descending. How would you write the lambda?
```cpp [](const std::pair<int, int>& a, const std::pair<int, int>& b) { if (a.first != b.first) return a.first < b.first; return a.second > b.second; } ``` This handles the primary and secondary sort conditions while maintaining strict weak ordering.
Approach: Demonstrate how to write multi-level sorting logic in a lambda.