In C++, how do you sort a std::vector of structs by one member using std::sort and a lambda comparator?
answer
- begin, end, and a callable
- true means a goes first
- greater-than for descending
- random-access iterators only
basics
~20 sCall std::sort(v.begin(), v.end(), comp) where comp is a lambda taking two const references and returning true when the first must come before the second, such as a.score > b.score for highest-first. Equal elements end up in no particular order.
solid answer
~40 s`std::sort` from `<algorithm>` takes two random-access iterators and an optional comparator. For a `std::vector<Entry>` you pass `board.begin()`, `board.end()` and a lambda such as `[](const Entry& a, const Entry& b) { return a.score > b.score; }`. The comparator answers one question: must `a` be placed before `b`? Returning `true` for equal elements is wrong, so use `<` or `>`, never `<=` or `>=`. Without a comparator `std::sort` uses `operator<`, which a plain struct does not have. To find an element afterwards, `std::find_if` takes a predicate lambda and returns an iterator to the first match, or `end()` when nothing matches. `std::sort` is not stable: entries with equal scores may come out in any order. It needs random-access iterators, so a `std::list` uses its own `list::sort` member instead.
code
cpp · 23 lines#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Entry {
std::string player;
int score;
};
int main() {
std::vector<Entry> board{{"ana", 870}, {"bo", 990}, {"cy", 640}, {"di", 990}};
// highest score first: return true when a must come before b
std::sort(board.begin(), board.end(),
[](const Entry& a, const Entry& b) { return a.score > b.score; });
auto it = std::find_if(board.begin(), board.end(),
[](const Entry& e) { return e.player == "cy"; });
if (it != board.end())
std::cout << "cy is rank " << (it - board.begin()) + 1 << '\n';
for (const Entry& e : board) std::cout << e.player << ' ' << e.score << '\n';
}go deeper
Write the call from memory: begin, end, and a lambda over two const references that returns true when the first goes before the second. Know that std::find_if returns end() when nothing matches.
Explain why the comparison must be strict, why the sort is not stable, and why std::sort needs random-access iterators so std::list has its own sort member.
Spot comparators that copy expensive members, that use <= or that compare inconsistent keys, and know that such a bug is undefined behaviour rather than a slightly wrong order.
Push teams towards tie-breaking keys or explicit stable sorts wherever output order is user-visible, so results do not change between standard library implementations.
## What std::sort needs `std::sort` lives in `<algorithm>`. Its two everyday overloads are: - `std::sort(first, last)` - orders the half-open range `[first, last)` with `operator<`; - `std::sort(first, last, comp)` - orders it with a **comparator** `comp` you supply. Both take **random-access iterators**, which `std::vector`, `std::array`, `std::deque` and plain arrays provide. A `std::list` does not, so `std::sort(lst.begin(), lst.end())` fails to compile; the list has its own `list::sort` member. The standard requires `O(N log N)` comparisons. ## Writing the comparator A comparator is any callable that takes two elements and returns something convertible to `bool`. The rule is short: return `true` **if and only if the first argument must come before the second**. A lambda is the usual choice because it sits next to the call: ```cpp struct Entry { std::string player; int score; }; std::sort(board.begin(), board.end(), [](const Entry& a, const Entry& b) { return a.score > b.score; }); ``` Points worth saying out loud in an interview: - **Take parameters by `const&`.** Copying a `std::string` member on every comparison is pure waste, and the comparator must not modify its arguments anyway. - **Use a strict comparison.** `a.score > b.score` (highest first) or `a.score < b.score` (lowest first). Writing `>=` or `<=` returns `true` for two equal scores, which breaks the ordering the algorithm relies on; that is undefined behaviour, covered in depth with comparator bugs. - **For a descending sort of plain values** `std::greater<>{}` does the same job: `std::sort(v.begin(), v.end(), std::greater<>{});`. - **For several keys**, compare a `std::tuple` built with `std::tie`: `return std::tie(b.score, a.player) < std::tie(a.score, b.player);` orders by score descending, then name ascending. ## What "sorted" leaves unspecified `std::sort` is **not stable**. Two entries with the same score may appear in either order after the call, and the order may differ between standard library implementations or even between runs on different input. If the order among ties matters - earlier submissions ranking first, say - you need `std::stable_sort` or a tie-breaking second key. ## Finding an element: std::find_if Searching a vector by a member uses `std::find_if`, which takes a **predicate**: a callable with one argument that returns `true` for a match. ```cpp auto it = std::find_if(board.begin(), board.end(), [](const Entry& e) { return e.player == "cy"; }); if (it != board.end()) { /* found */ } ``` It walks the range from the front and returns an iterator to the first element for which the predicate is `true`, or `last` when none is. Always compare against `end()` before dereferencing. `std::find_if` is linear: it does not use the fact that the vector is sorted. On sorted data you search by the sort key with `std::lower_bound` instead, in logarithmic time - but only by that key; finding a player by name in a vector sorted by score is still a linear `find_if`. ## Common mistakes | Mistake | What happens | |---|---| | Comparator uses `<=` or `>=` | Undefined behaviour; can read out of bounds or never return | | Comparator takes `Entry` by value | Correct but copies two strings per comparison | | No comparator on a struct without `operator<` | Compile error inside `<algorithm>` | | `std::sort` on a `std::list` | Compile error: list iterators are bidirectional | | Dereferencing `find_if`'s result unchecked | Undefined behaviour when nothing matched | ## Lambda, function object or function pointer Any of the three works as a comparator, and they differ in what the optimiser can see: - **A lambda** has its own unique closure type, so `std::sort` is instantiated for exactly that comparator and the comparison is usually inlined into the sorting loops. - **A named function object** - a `struct` with `operator()`, or `std::greater<>` - behaves the same way and can be reused across call sites and documented once. - **A function pointer** such as `&compareByScore` makes the comparator a run-time value of type `bool(*)(const Entry&, const Entry&)`; the compiler can inline it only when it can prove which function the pointer holds, so in practice it often stays an indirect call per comparison. Whichever you pick, keep it a pure function of its two arguments: no counters, no logging, no lookups that can change during the sort. A comparator that gives different answers for the same pair on different calls is as broken as one that uses `<=`. ## Putting it together The worked example below sorts a small leaderboard highest-first and reports a player's rank. The rank is the distance from `begin()` plus one, which works because vector iterators support subtraction. Note what the output does **not** promise: two players tied on 990 may print in either order.
- How would you sort the same leaderboard by score descending and then by player name ascending?Compare both keys in one comparator. The compact form builds tuples with `std::tie` and swaps the operands for the descending key: `return std::tie(b.score, a.player) < std::tie(a.score, b.player);`. Tuples compare lexicographically, so the name only decides when scores are equal. Because the second key breaks every tie between distinct players, the result no longer depends on stability.
- Why does std::sort not compile on a std::list, and what do you use instead?`std::sort` requires random-access iterators so it can jump to a pivot and compute distances in constant time; `std::list` only offers bidirectional iterators. The list provides its own member, `lst.sort()` or `lst.sort(comp)`, which relinks nodes instead of moving values and is stable. Alternatively copy into a `std::vector`, sort it, and copy back.
- Using <= in the comparator so equal scores are handled
- Saying std::sort keeps equal elements in their original order
- Calling std::sort on a std::list's iterators
- Using std::find_if to look up the sort key on sorted data
- Dereferencing the result of std::find_if without checking end()