Every _if algorithm and every sort takes a callable. Getting that callable right is most of the work, and two of its rules are enforced by nothing at all.

The four things that can be a predicate

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

// A free function.
bool is_even(int x) { return x % 2 == 0; }

// A function object (functor): a class with operator(). It can hold state.
struct Above {
    int threshold;
    bool operator()(int x) const { return x > threshold; }
};

// A stateful predicate used with an algorithm — see the warning below.
struct CountingIsEven {
    int* calls;
    bool operator()(int x) const { ++*calls; return x % 2 == 0; }
};

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8};

    std::cout << "free function:  " << std::count_if(v.begin(), v.end(), is_even) << "\n";
    std::cout << "lambda:         "
              << std::count_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; }) << "\n";
    std::cout << "function object:" << std::count_if(v.begin(), v.end(), Above{5}) << "\n";

    // std::function can hold any of the three, at a run-time cost.
    std::function<bool(int)> pred = is_even;
    std::cout << "std::function:  " << std::count_if(v.begin(), v.end(), pred) << "\n";
    pred = Above{5};
    std::cout << "reassigned:     " << std::count_if(v.begin(), v.end(), pred) << "\n";

    int calls = 0;
    std::count_if(v.begin(), v.end(), CountingIsEven{&calls});
    std::cout << "predicate called " << calls << " times for " << v.size() << " elements\n";
    return 0;
}

free function:  4
lambda:         4
function object:3
std::function:  4
reassigned:     3
predicate called 8 times for 8 elements

A free function is the simplest, and cannot carry state.

A lambda is an unnamed function object written at the call site. Module 14 covers it properly.

A function object is a class with operator(). Above{5} holds its threshold as a member, which is how it parameterises the test — this is what lambdas generate for you behind the scenes.

std::function is a type-erased wrapper that can hold any of them and be reassigned at run time. That flexibility costs an indirect call the compiler usually cannot inline. Use it when you genuinely need to store or swap callables, not as a habit — lesson 14.4 measures the difference.

The rule nobody enforces: a predicate must not have side effects

CountingIsEven above worked and reported 8 calls for 8 elements. That is std::count_if, which happens to make exactly one pass. You may not rely on that.

The standard says an algorithm may copy your predicate, may call it any number of times, and may call it in any order. A predicate that mutates state is therefore unspecified:

// int seen = 0;
// std::count_if(v.begin(), v.end(), [&](int x) { ++seen; return x > 0; });
//
// `seen` may not equal v.size(). The algorithm is entitled to copy the
// lambda — and if it captured by value rather than reference, the copy's
// count is thrown away entirely.

The failure is worse for std::sort, which really does copy comparators around. If you want to count something, use std::count_if's return value, or a for loop, and keep the predicate pure.

The same rule explains a subtle thing about std::remove_if: your predicate is called on elements in an unspecified order, and possibly on elements that have already been moved from. Predicates read; they do not write.

Comparators, and the strict weak ordering

A comparator answers "does a come before b?" — and it must be a strict weak ordering:

| Rule | Means | |---|---| | Irreflexive | comp(a, a) is always false | | Antisymmetric | if comp(a, b) then !comp(b, a) | | Transitive | if comp(a, b) and comp(b, c) then comp(a, c) | | Transitivity of equivalence | if a and b are equivalent, and b and c are, then a and c are |

Break any of them and the behaviour is undefined — not "a wrong order", but genuinely undefined. The classic failure:

// std::sort(v.begin(), v.end(), [](int a, int b) { return a <= b; });   // WRONG

<= is not irreflexive: comp(a, a) is true, so the sort believes every element comes before itself. libstdc++'s introsort then runs its inner pointer off the end of the array, and the result is a segmentation fault or silent memory corruption — not a mis-sorted vector.

Use <, never <=. If you find yourself wanting <=, you want !comp(b, a) instead.

The other frequent break is a comparator that reads a field which can be NaN. Every comparison involving NaN is false, including NaN < NaN, so transitivity collapses. Filter or handle NaN before sorting floating-point data.

Multi-key sorting

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

struct Employee {
    std::string name;
    std::string department;
    int salary;
};

int main() {
    std::vector<Employee> staff = {
        {"Dara",     "eng",   90},
        {"Bopha",    "sales", 70},
        {"Chanthou", "eng",   90},
        {"Kosal",    "sales", 85},
        {"Maria",    "eng",   75},
    };

    // Sort by salary descending. std::sort is NOT stable, so the relative
    // order of the two 90s is unspecified.
    auto by_salary = staff;
    std::sort(by_salary.begin(), by_salary.end(),
              [](const Employee& a, const Employee& b) { return a.salary > b.salary; });
    std::cout << "sort by salary: ";
    for (const auto& e : by_salary) std::cout << e.name << " ";
    std::cout << "\n";

    // stable_sort preserves the input order within equal keys.
    auto stable = staff;
    std::stable_sort(stable.begin(), stable.end(),
                     [](const Employee& a, const Employee& b) { return a.salary > b.salary; });
    std::cout << "stable_sort:    ";
    for (const auto& e : stable) std::cout << e.name << " ";
    std::cout << "\n";

    // Multi-key: department ascending, then salary descending, then name.
    auto multi = staff;
    std::sort(multi.begin(), multi.end(),
              [](const Employee& a, const Employee& b) {
                  if (a.department != b.department) return a.department < b.department;
                  if (a.salary != b.salary) return a.salary > b.salary;
                  return a.name < b.name;
              });
    std::cout << "multi-key:      ";
    for (const auto& e : multi) std::cout << e.name << "(" << e.department << "," << e.salary << ") ";
    std::cout << "\n";

    // The tuple trick: std::tie compares lexicographically for you.
    auto tied = staff;
    std::sort(tied.begin(), tied.end(),
              [](const Employee& a, const Employee& b) {
                  return std::tie(a.department, a.name) < std::tie(b.department, b.name);
              });
    std::cout << "std::tie:       ";
    for (const auto& e : tied) std::cout << e.name << " ";
    std::cout << "\n";
    return 0;
}

sort by salary: Dara Chanthou Kosal Maria Bopha 
stable_sort:    Dara Chanthou Kosal Maria Bopha 
multi-key:      Chanthou(eng,90) Dara(eng,90) Maria(eng,75) Kosal(sales,85) Bopha(sales,70) 
std::tie:       Chanthou Dara Maria Bopha Kosal 

std::sort and std::stable_sort produced identical output here. That is not a guarantee — it is the trap. With five elements libstdc++ falls back to insertion sort, which happens to be stable, so the difference does not appear.

The multi-key form is the shape to learn: compare the first key, and only if it ties move to the next. Note that the last comparison has no if — the final key must decide, or equal elements have no defined order.

std::tie builds a tuple of references, and tuples compare lexicographically. It expresses the same thing in one line, and it is much harder to get wrong than a chain of ifs. The limitation is that every key must sort in the same direction; mixing ascending and descending needs the explicit form, or negating a numeric key.

Where stability actually shows

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

struct Item {
    int key;
    int original_index;
};

int main() {
    // 40 elements, only 2 distinct keys — so there is plenty for an unstable
    // sort to reorder within each group.
    std::vector<Item> data;
    for (int i = 0; i < 40; ++i) {
        data.push_back({i % 2, i});
    }

    auto unstable = data;
    auto stable = data;
    std::sort(unstable.begin(), unstable.end(),
              [](const Item& a, const Item& b) { return a.key < b.key; });
    std::stable_sort(stable.begin(), stable.end(),
                     [](const Item& a, const Item& b) { return a.key < b.key; });

    bool same = std::equal(unstable.begin(), unstable.end(), stable.begin(),
                           [](const Item& a, const Item& b) {
                               return a.original_index == b.original_index;
                           });
    std::cout << "sort and stable_sort agree: " << std::boolalpha << same << "\n";

    std::cout << "stable_sort, first 8 original indices:   ";
    for (int i = 0; i < 8; ++i) std::cout << stable[i].original_index << " ";
    std::cout << "\n";
    std::cout << "std::sort,   first 8 original indices:   ";
    for (int i = 0; i < 8; ++i) std::cout << unstable[i].original_index << " ";
    std::cout << "\n";
    return 0;
}

sort and stable_sort agree: false
stable_sort, first 8 original indices:   0 2 4 6 8 10 12 14 
std::sort,   first 8 original indices:   0 26 24 28 22 20 30 18 

There it is. Forty elements and two distinct keys, and std::sort scrambled the within-group order completely: 0 26 24 28 22 20 30 18 where the input order was 0 2 4 6 8 10 12 14.

Both results are correct — every key-0 element precedes every key-1 element in both. They differ only in the order of elements the comparator considers equal, which std::sort is free to choose.

This is why "sort by department, then sort again by salary" is a bug. The second sort discards the first's work unless it is stable_sort. Either use stable_sort for the second pass, or write one multi-key comparator — the latter is faster and says what you mean.

std::stable_sort costs extra memory (it allocates a temporary buffer) and is somewhat slower. Pay for it when the order of equal elements is meaningful; otherwise std::sort.

Ready-made function objects

<functional> provides the common ones, and the C++14 transparent forms deduce their types:

// std::less<>{}          a < b        (the default everywhere)
// std::greater<>{}       a > b        descending
// std::plus<>{}          a + b        for std::accumulate
// std::multiplies<>{}    a * b
// std::negate<>{}        -a
//
// std::sort(v.begin(), v.end(), std::greater<>{});     // descending, no lambda
// std::priority_queue<int, std::vector<int>, std::greater<int>> minheap;

Note the empty <>: std::greater<> deduces the argument type at the call, while std::greater<int> fixes it. Prefer the empty form except where a template parameter demands the explicit one, as std::priority_queue does.

Projections, the C++20 shortcut

The ranges versions take a projection — a member pointer saying which field to compare — so the common case needs no comparator at all:

// std::ranges::sort(staff, {}, &Employee::salary);          // by salary, ascending
// std::ranges::sort(staff, std::greater{}, &Employee::name); // by name, descending
// std::ranges::max_element(staff, {}, &Employee::salary);

{} means "the default comparator". Lesson 13.9 covers ranges properly; this one line is the feature people miss most.

Try it

Checkpoint

• A predicate can be a free function, a lambda, a function object, or a std::function.
• A function object holds state in members; that is what a capturing lambda compiles to.
• std::function is reassignable at run time and costs an indirect call — do not use it by habit.
• A predicate must be pure: an algorithm may copy it and call it any number of times, in any order.
• A comparator must be a strict weak ordering: irreflexive, antisymmetric, transitive.
• Using <= is undefined behaviour and typically crashes inside the sort, not in your code.
• NaN breaks transitivity — handle it before sorting floating-point data.
• Multi-key: compare each key in turn; the last comparison has no if.
• std::tie compares lexicographically but only in one direction; negate a key to reverse it.
• std::sort and std::stable_sort can agree at small n and diverge completely at larger n.
• Chained stable_sorts from least to most significant key is a real technique, at 3× the cost.
• C++20 projections (std::ranges::sort(v, {}, &T::field)) remove most comparators entirely.