Step 5 of 6
Stability and custom comparators
A sort is stable if equal elements keep their original relative order. It sounds like a detail, but it matters whenever the input order means something (arrival time, sign-up order) or when you sort by one key after another.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Order {
std::string id;
int priority;
};
int main() {
// Arrival order: a1 came first, then b2, and so on.
std::vector<Order> q = {{"a1", 2}, {"b2", 1}, {"c3", 2}, {"d4", 1}, {"e5", 2}};
std::stable_sort(q.begin(), q.end(), [](const Order& x, const Order& y) {
return x.priority < y.priority; // strictly less: a valid comparator
});
for (const auto& o : q) std::cout << o.id << "(" << o.priority << ") ";
std::cout << "\n";
}
b2(1) d4(1) a1(2) c3(2) e5(2)
Within each priority, orders are still in arrival order: b2 before d4, and a1, c3, e5 in sequence. std::sort might have mixed them up.
std::sort vs std::stable_sort
std::sort: not stable, usually slightly faster.std::stable_sort: stable. Use it whenever ties must keep their order.
Comparators must be strict
A comparator answers "must a come strictly before b?". For equal elements it must return false both ways. So use < or >, never <= or >=. Breaking this rule is undefined behavior: results can be wrong, and with std::sort it can even read outside the array and crash.
For "highest score first", compare with >: return a.score > b.score;.
Your turn: write void rank(std::vector<Entry>& v) that orders entries by score, highest first. Entries with equal scores must stay in their original (sign-up) order.