Custom Comparators — Write custom comparators for sorting (intro) - C Plus Plus

SECTION 1

Historical Context & Motivation

The C++ Standard Template Library was designed from the outset around a powerful idea: algorithms should be decoupled from data structures. Alexander Stepanov, the principal architect of the STL, drew on decades of work in generic programming to create a library where sorting, searching, and transforming could be expressed independently of the container holding the data. A critical enabler of this flexibility is the concept of a comparator — a callable object that defines how two elements relate in an ordering. Without custom comparators, std::sort would be limited to whatever operator< provides, which is often insufficient for real-world applications where sorting criteria vary by context.

1979 • Early Generic Programming

Alexander Stepanov begins formal research into generic programming at GE Research, exploring how to abstract algorithms from their underlying data representations.

1994 • STL Accepted into C++

The ANSI/ISO C++ committee votes to include the STL in the C++ Standard Library. Algorithms like std::sort accept optional comparison functors, establishing the comparator pattern.

1998 • C++98 Standard Published

The first ISO C++ standard formalizes the STL, including strict weak ordering requirements for comparators used in associative containers and sorting algorithms.

2011 • C++11 — Lambdas Arrive

Lambda expressions dramatically simplify writing inline comparators, removing the need for separate functor classes in most cases.

2020 • C++20 — Ranges & Three-Way Comparison

The spaceship operator (<=>) and the Ranges library introduce projection-based sorting and unified comparison categories, building on the comparator foundation.

The fundamental question that custom comparators answer is deceptively simple: How should two elements be ordered when the default ordering is wrong, absent, or context-dependent? Consider sorting a vector of students by GPA descending, or ordering a priority queue of tasks by deadline. The STL provides the algorithmic machinery; you provide the ordering logic via a comparator.

SECTION 2

Core Principles & Definitions

A comparator in C++ is any callable entity that accepts two arguments of the element type and returns a bool. It returns true if the first argument should come before the second in the desired ordering. The STL imposes a precise mathematical requirement on comparators: they must define a strict weak ordering. Violating this requirement leads to undefined behavior — the algorithm may loop infinitely, corrupt memory, or produce incorrect results.

Irreflexivity

A comparator must never report that an element is "less than" itself. Formally, comp(a, a) must return false for every element a.

Asymmetry

If comp(a, b) is true, then comp(b, a) must be false. Two elements cannot each precede the other.

Transitivity

If comp(a, b) and comp(b, c) are both true, then comp(a, c) must also be true.

Transitivity of Equivalence

If neither comp(a, b) nor comp(b, a) is true (a and b are equivalent), and similarly b ≡ c, then a ≡ c must also hold.

✦

KEY TAKEAWAY

Think of a comparator like a referee in a tournament who must decide match outcomes. The referee can declare "A beats B" or "B beats A" or "it's a draw," but the decisions must be consistent: if A beats B and B beats C, the referee cannot claim C beats A. Similarly, the referee can never declare a player loses to themselves. As long as these rules hold, the tournament bracket (sorting algorithm) will always produce a valid ranking.

In practice, C++ supports three main forms for comparators: function pointers, functor classes (classes that overload operator()), and lambda expressions. All three are interchangeable from the algorithm's perspective because the STL uses templates to accept any callable type. Modern C++ strongly favors lambdas for their conciseness and inline readability, though functor classes remain essential when the comparator needs to be passed as a template type parameter, as with std::set or std::priority_queue.

SECTION 3

Visual Explanation — How std::sort Invokes a Comparator

The following diagram illustrates how std::sort interacts with a custom comparator during a single comparison step. The algorithm selects two elements from the range, passes them to the comparator, and uses the boolean result to decide their relative placement. This callback pattern is the essential mechanism that makes STL algorithms customizable.

The sorting algorithm repeatedly invokes the comparator on pairs of elements. Here a descending-GPA lambda returns true when the first student's GPA exceeds the second's, causing higher GPAs to migrate to the front of the vector.

Notice that the algorithm and the comparator are entirely independent units. The algorithm knows nothing about GPAs, names, or student records — it only sees true or false. This separation of concerns is the hallmark of generic programming: you write the ordering policy once, and the STL handles all the element movement, partitioning, and recursion internally.

SECTION 4

How Comparators Work — Three Forms

Form 1: Function Pointer

The simplest form is a standalone function that takes two const references and returns a bool. When you pass its name to std::sort, the compiler decays it to a function pointer. This approach is straightforward but cannot capture state from an enclosing scope, limiting its flexibility.

FUNCTION POINTER COMPARATOR

bool cmpDescending(const Student& a, const Student& b) { return a.gpa > b.gpa; } std::sort(v.begin(), v.end(), cmpDescending);

The third argument to std::sort is the name of the function, which decays to a pointer of type bool(*)(const Student&, const Student&).

Form 2: Functor Class

A functor (function object) is a class or struct that overloads operator(). Because it is a type, it can be passed as a template argument to containers like std::set<T, Compare> or std::priority_queue<T, Container, Compare>. Functors can also hold state — for example, a threshold value — making them more powerful than plain function pointers.

FUNCTOR CLASS COMPARATOR

struct CmpByGPA { bool operator()(const Student& a, const Student& b) const { return a.gpa > b.gpa; } }; std::sort(v.begin(), v.end(), CmpByGPA{});

The const qualifier on operator() is important: it signals that the comparator does not modify internal state during comparison, which enables the algorithm to copy or move it freely.

Form 3: Lambda Expression

Since C++11, lambda expressions provide the most concise syntax for defining comparators inline. Under the hood, the compiler generates an anonymous functor class, so lambdas and functors are semantically equivalent. Lambdas can capture variables from the enclosing scope by value or reference, enabling context-dependent comparisons. For most uses of std::sort, lambdas are the idiomatic choice in modern C++.

LAMBDA COMPARATOR

std::sort(v.begin(), v.end(), [](const Student& a, const Student& b) { return a.gpa > b.gpa; });

The capture list [] is empty here because no external variables are needed. To sort relative to a cutoff, you could capture a threshold: [cutoff](const Student& a, const Student& b) { ... }.

⚠

Common Pitfall

Using <= instead of < (or >= instead of >) violates irreflexivity because comp(a, a) would return true. This is undefined behavior in the STL and can crash your program. Always use strict inequality operators in comparators.

SECTION 5

Comparator Forms at a Glance

Choosing the right comparator form depends on the context in which it will be used. The diagram below provides a decision flowchart, and the subsequent table offers a side-by-side comparison of the three forms along key dimensions.

Decision flowchart for selecting a comparator form. Functor classes are required when the comparator must be specified as a template type parameter. Lambdas are preferred everywhere else.

Feature	Function Pointer	Functor Class	Lambda
Syntax verbosity	Moderate	High (separate class)	Low (inline)
Can capture state	No	Yes (data members)	Yes (capture list)
Usable as template type arg	Yes (via decltype)	Yes (natural)	Awkward (unique type)
Inline optimization	Unlikely (indirect call)	Likely (type known)	Likely (type known)
Reusable across files	Yes	Yes	No (local scope)

Comparison of three comparator forms across practical dimensions

SECTION 6

Worked Example — Multi-Key Sorting

Suppose you have a std::vector<Student> where each Student has a std::string name and a double gpa. The goal is to sort students by GPA in descending order, and when two students share the same GPA, sort them alphabetically by name in ascending order.

Multi-Key Custom Sort on Student Records

1
Step 1 — Define the Data Structure

We define a simple struct to represent each student: struct Student { std::string name; double gpa; };. This struct has no built-in comparison operator, so std::sort without a comparator would fail to compile.
2
Step 2 — Identify the Ordering Logic

The primary key is GPA (descending), so if a.gpa > b.gpa, student a comes first. The secondary key is name (ascending): if GPAs are equal, a.name < b.name determines precedence.
3
Step 3 — Write the Lambda Comparator

We combine both keys using an if statement. A cleaner idiom uses std::tie to leverage lexicographic tuple comparison:

auto cmp = [](const Student& a, const Student& b) { // Negate GPA for descending; name ascending is natural return std::tie(b.gpa, a.name) < std::tie(a.gpa, b.name); };
4
Step 4 — Apply the Comparator to std::sort

Pass the lambda as the third argument to std::sort:

std::sort(students.begin(), students.end(), cmp);
5
Step 5 — Verify the Output

Given the input {"Alice",3.8}, {"Bob",3.9}, {"Carol",3.8}, {"Dave",4.0}, the sorted order is Dave (4.0), Bob (3.9), Alice (3.8), Carol (3.8). Notice Alice precedes Carol because 'A' < 'C' alphabetically, resolving the GPA tie.

Output: Dave 4.0 → Bob 3.9 → Alice 3.8 → Carol 3.8

💡

The std::tie Trick

Using std::tie to build tuples of references enables lexicographic comparison for free. To reverse the sort direction for a specific key, swap the positions of a and b for that key within the tuple. This is more maintainable than writing nested if chains for multi-key sorts.

SECTION 7

Strengths, Limitations & Common Mistakes

Aspect	Strengths	Limitations / Pitfalls
Flexibility	Sort any type by any criteria — no need to modify the class itself	Complex comparators can become hard to read and verify for correctness
Performance	Lambdas and functors are typically inlined by the compiler, yielding zero-overhead abstraction	Function pointers may inhibit inlining, adding indirect-call overhead per comparison
Correctness	The strict weak ordering contract is well-documented and enforced by sanitizers in debug mode	Using ≤ or ≥ instead of < or > violates irreflexivity and causes undefined behavior
Reusability	Functors and named functions can be shared across translation units	Lambdas have unique, unnamed types; difficult to store in data structures or pass across API boundaries
Container compatibility	Functors naturally serve as template type arguments for ordered containers	Passing a lambda type to std::set or std::map requires decltype and constructor arguments

Trade-offs when using custom comparators in C++

✦

KEY TAKEAWAY

Custom comparators follow the same principle as plug-in modules in a signal-processing pipeline: the pipeline (STL algorithm) handles the data flow and orchestration, while the plug-in (your comparator) defines the domain-specific decision logic. This modularity means you can swap ordering strategies without rewriting or even recompiling the algorithm. However, just as a faulty plug-in can corrupt an audio pipeline, a comparator that violates strict weak ordering can corrupt your data.

SECTION 8

Connection to Advanced Theory

Custom comparators are the foundation upon which several advanced C++ features are built. Understanding comparators positions you to work with ordered associative containers, priority queues, and the C++20 Ranges library's projections and custom views. The table below maps introductory comparator concepts to their advanced counterparts.

Introductory Concept	Advanced Extension
Lambda comparator for std::sort	Projections in std::ranges::sort — sort by a member without writing a comparator at all
Functor class as Compare template argument	Transparent comparators (std::less<>) enabling heterogeneous lookup in std::set
Strict weak ordering requirement	Three-way comparison (operator<=>) and comparison categories (strong_ordering, weak_ordering, partial_ordering)
Multi-key sort via std::tie	Defaulted operator<=> that auto-generates all six comparison operators from member declarations
Custom ordering for std::priority_queue	Policy-based data structures (e.g., pb_ds) and custom allocator-aware ordered containers

Mapping introductory comparator concepts to advanced C++ features

As you progress, you will find that comparators are not limited to sorting. They underpin std::lower_bound, std::upper_bound, std::merge, std::nth_element, and many other algorithms. The consistent interface — a binary predicate returning bool — means that mastering comparators once pays dividends across the entire STL.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain why a comparator that uses <= instead of < violates the strict weak ordering requirement. Which specific property is broken, and what could happen at runtime?

Show answer

Using <= violates the irreflexivity property because comp(a, a) returns true (since a ≤ a is always true), whereas a strict weak ordering demands comp(a, a) == false. At runtime, this constitutes undefined behavior: std::sort may infinite-loop during partitioning (since the pivot element appears to be both less than and equal to itself), read out of bounds, or produce a silently incorrect result. Debug builds with sanitizers like _GLIBCXX_DEBUG will catch this and abort with a diagnostic.

Question 2: BASIC CALCULATION

Write a lambda comparator that sorts a std::vector<int> in descending order. Show the complete call to std::sort. For the input {3, 1, 4, 1, 5, 9}, what is the output?

Show answer

The complete code is: std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; });. The comparator returns true when the first argument is greater, placing larger values earlier. Applied to the input {3, 1, 4, 1, 5, 9}, the output is {9, 5, 4, 3, 1, 1}. Note the use of strict > rather than >= to maintain a valid strict weak ordering.

Question 3: INTERMEDIATE

Given struct Event { std::string name; int priority; double time; };, write a comparator that sorts events by priority (highest first), breaking ties by time (earliest first). Use the std::tie idiom.

Show answer

The comparator is: auto cmp = [](const Event& a, const Event& b) { return std::tie(b.priority, a.time) < std::tie(a.priority, b.time); };. To sort by priority descending, we place b.priority in the left tuple and a.priority in the right — effectively reversing the comparison for that key. For time ascending, a.time goes on the left in both tuples (natural order). The < on tuples performs lexicographic comparison, checking priority first and only consulting time when priorities are equal.

Question 4: APPLIED

You are building a task scheduler. Tasks have a deadline (int, lower is sooner) and a weight (int, higher is more important). Define a functor class TaskCompare suitable for use with std::priority_queue<Task, std::vector<Task>, TaskCompare>. The most urgent task (earliest deadline, breaking ties by highest weight) should be at the top.

Show answer

Since std::priority_queue is a max-heap by default — it places the element for which the comparator returns true at the bottom — we need to invert our logic. The functor should return true when the first task is LESS urgent, so that less-urgent tasks sink:

struct TaskCompare { bool operator()(const Task& a, const Task& b) const { return std::tie(a.deadline, b.weight) > std::tie(b.deadline, a.weight); } };

. Here, a later deadline (larger number) or a lower weight makes a task less urgent, so it returns true for that task, pushing it down the heap. The most urgent task naturally rises to the top.

Question 5: CRITICAL THINKING

Consider a comparator that sorts strings by length first (shortest to longest), and for strings of equal length, by lexicographic order. Someone proposes: [](const std::string& a, const std::string& b) { return a.size() <= b.size() && a < b; }. Identify all correctness issues with this comparator, explain which strict weak ordering properties are violated, and provide a corrected version.

Show answer

There are two major issues. First, the comparator violates irreflexivity in a subtle way: for a string s, s.size() <= s.size() is true, and s < s is false, so comp(s, s) returns false — this particular case is actually safe. However, the second and more critical issue is that the logic is fundamentally flawed: the && operator means a longer string is never considered "less than" a shorter one even if its lexicographic order would demand it for equal-length strings. More importantly, two strings of different lengths can both return false for comp(a,b) and comp(b,a), making them equivalent, but this equivalence is not transitive across different lengths. The corrected version separates the keys: [](const std::string& a, const std::string& b) { if (a.size() != b.size()) return a.size() < b.size(); return a < b; }. Alternatively, return std::tie(a.size(), a) < std::tie(b.size(), b); — noting that comparing the full strings in the tie is slightly less efficient but correct.

SUMMARY

Summary

A custom comparator is a callable object that defines a strict weak ordering over elements, enabling STL algorithms like std::sort to order any data type by any criteria. The ordering must satisfy four properties: irreflexivity, asymmetry, transitivity, and transitivity of equivalence. Violating any of these causes undefined behavior.

Comparators come in three forms: function pointers (simple but cannot capture state), functor classes (essential for container template parameters like std::set and std::priority_queue), and lambda expressions (the modern default for inline use). For multi-key sorting, the std::tie idiom provides clean lexicographic comparison, and swapping the positions of a and b within the tuple reverses the sort direction for that key. Mastering comparators is foundational to effective use of the entire STL.