Home / C++ / Custom comparators and sorting

C++ PROGRAMMING · 14 MIN STUDY

Custom comparators and sorting

Sort records and custom data using strict weak ordering, comparator functions, and lambdas.

Learning objectives

  • Write a comparator for custom records.
  • Explain the strict weak ordering requirement.
  • Choose between sort and stable_sort.
  • Sort by multiple fields without fragile comparison logic.

Prerequisites: understand std::vector, iterators, functions, and basic lambda expressions. Review Vectors, STL algorithms, and Lambda expressions first. Examples use C++17.

Sorting simple values

#include <algorithm>
#include <functional>
#include <vector>
std::vector<int> numbers{8, 3, 6, 1};
std::sort(numbers.begin(), numbers.end()); // ascending
std::sort(numbers.begin(), numbers.end(), std::greater<int>{}); // descending

Include <algorithm> for sorting and <functional> for standard function objects such as std::greater.

What a comparator means

A comparator answers: should the left element appear before the right element? It does not answer whether the values are equal. For ascending order, a < b is a suitable comparison.

#include <algorithm>
#include <string>
#include <vector>
struct Student {
    std::string name;
    int score;
};
std::vector<Student> students{{"Ada", 95}, {"Linus", 88}};
std::sort(students.begin(), students.end(),
    [](const Student& a, const Student& b) {
        return a.score > b.score; // higher score first
    });

Strict weak ordering

Standard sorting algorithms require a strict weak ordering. For beginner use, remember three practical rules: an element must not compare before itself; comparisons must be consistent; and equivalence must behave consistently. Do not use <= or >= as a sorting comparator because they say an element comes before itself.

Sort by multiple fields

std::sort(students.begin(), students.end(),
    [](const Student& a, const Student& b) {
        if (a.score != b.score) return a.score > b.score;
        return a.name < b.name;
    });

This orders higher scores first and breaks ties by name in ascending order. The comparator uses the second field only when the first field ties.

Using std::tie

#include <tuple>
std::sort(students.begin(), students.end(),
    [](const Student& a, const Student& b) {
        return std::tie(a.score, a.name) > std::tie(b.score, b.name);
    });

This example sorts both fields in descending order. If you need mixed directions, use explicit comparisons so the intent stays clear.

sort versus stable_sort

std::sort is not stable: equivalent elements may change relative order. std::stable_sort preserves their original relative order. Both perform O(n log n) comparisons; stable_sort may use extra memory.

Common mistakes

  • Using a.score >= b.score and violating strictness.
  • Forgetting a tie-breaker when deterministic ordering matters.
  • Writing a comparator whose result changes while sorting.
  • Assuming sort preserves the order of equal elements.

Practice

  1. Sort words by length, then alphabetically.
  2. Sort products by price ascending and rating descending.
  3. Explain why return a <= b; is invalid for sorting.
  4. When would stable_sort be useful?
Show solutions
  1. Compare lengths first; if equal, compare strings with <.
  2. Compare price first; for equal prices, compare rating with >.
  3. It reports an element as ordered before itself when both arguments are equal.
  4. When the original order among equivalent elements carries useful meaning.

Summary

Comparators define the order expected by sorting algorithms. Keep them consistent and strict, and use explicit tie-breaking for multi-field records.

References