Start learning free

LESSON 262 OF 667 · PAIRS, SORTING & BUILT-INS

Custom Sorting in C++: sort with a Lambda

Lesson Read the full explanation

TL ; DR:

To sort by your own rule, give sort a lambda. It gets two items and returns true when the first one goes first.


vector<int> nums = {25, 13, 5, 41, 33};

sort(nums.begin(), nums.end(),
     [](int a, int b) {
         if (a % 10 != b % 10) {
             return a % 10 < b % 10;
         }
         return a < b;
     });
// 41 13 33 5 25

vector<int> scores = {70, 95, 82};

sort(scores.begin(), scores.end(), [](int a, int b) { return a > b; });
// 95 82 70

Full lesson:

The sort function puts a vector in order. Give it the vector's begin() and end(). Numbers go from small to large, and text from A to Z.

Sometimes you need another order. The shortest word may have to come first, or the highest score.

Then add a third value, a lambda. A lambda is a small function written right where you need it. It has no name. It starts with []. Then come its parameters and its body.

The lambda gets two items, a and b. It returns true when a must go before b. The sort function calls it again and again, on two items at a time.

  • Shortest first: the body returns a.size() < b.size().
  • High to low: the body returns a > b.

A parameter like const string& a lets the lambda read a string without copying it.

For two rules, check the first rule. Use the second one only on a tie, as the if above does.

Above, the first rule compares the last digits, a % 10 and b % 10. Numbers with the same last digit then go from small to large.

On two strings, < and > compare them from A to Z.

Use < or > in the lambda. Never use <= or >=. Two equal items must give false both ways. Otherwise sort can crash.

The sort function doesn't keep equal items in their old order. Add a second rule when ties matter.

It also changes the vector itself. To keep the original, sort a copy. The line vector<string> copy = words; makes one.

Your task

A pet shop sells toys. Their prices are in prices. Sort prices from high to low.

The shop's pets are in names. Sort names by their last letter, in alphabetical order. Names with the same last letter go from A to Z.

The code already prints both, one item per line.

Expected output:

30
12
8
5
Bella
Luna
Bo
Coco
Max
Rex
STEP 1 OF 4
    Ctrl + Enter to check

    C++ · PAIRS, SORTING & BUILT-INS

    Custom Sorting in C++, explained

    Why custom sorting

    Called with just begin() and end(), sort puts numbers from small to large and strings from A to Z. Often you need another order: the highest price first, the shortest word first, or names ordered by their last letter. For that, sort takes a third argument, your own rule.

    The rule is a lambda: a small function with no name, written right where you need it. It starts with [], then come the parameters and the body in braces. The lambda gets two items, a and b, and returns true when a must go before b. sort calls it again and again, on two items at a time, until the vector is in order.

    One rule

    vector<int> scores = {70, 95, 82};
sort(scores.begin(), scores.end(), [](int a, int b) { return a > b; });

    The vector now holds 95 82 70. Bigger first means returning a > b; smaller first means a < b. For strings, a.size() < b.size() puts the shortest word first. A parameter written as const string& a lets the lambda read a string without copying it.

    Two rules

    For two rules, check the first rule, and use the second one only on a tie:

    vector<int> nums = {25, 13, 5, 41, 33};

sort(nums.begin(), nums.end(),
     [](int a, int b) {
         if (a % 10 != b % 10) {
             return a % 10 < b % 10;
         }
         return a < b;
     });

    The numbers come out as 41 13 33 5 25. The first rule compares last digits. Numbers with the same last digit (13 and 33, or 5 and 25) then go from small to large.

    Things to know

    • Use < or > in the lambda, never <= or >=. Two equal items must give false both ways, or sort can misbehave and even crash.
    • sort doesn't keep equal items in their old order. Add a second rule when ties matter.
    • It changes the vector itself. To keep the original, sort a copy. With words = {"pear", "fig", "apple"}, the line vector<string> copy = words; makes one. After sorting copy by size, words still reads pear fig apple and copy reads fig pear apple.
    • In a file of your own, add #include <algorithm>, <vector> and <string> for these examples.

    The lesson's task

    A pet shop has toy prices {12, 5, 30, 8} and pets {"Rex", "Luna", "Bella", "Max", "Bo", "Coco"}. Sort the prices from high to low. Sort the names by their last letter in alphabetical order, with names that share a last letter going from A to Z.

    1. For the prices, call sort with prices.begin(), prices.end() and a lambda that returns a > b.
    2. For the names, the lambda needs two rules, so give it a body in braces, closed by });. The last letter sits at the last index, one less than the size: a[a.size() - 1]. Store the two last letters in lastA and lastB.
    3. If they differ, return lastA < lastB. On two chars, < is true when the first letter comes first in the alphabet.
    4. Otherwise return a < b. Max and Rex both end in x, and this puts Max first.
    class Solution {
public:
    void mainFunction() {
        vector<int> prices = {12, 5, 30, 8};
        vector<string> names = {"Rex", "Luna", "Bella", "Max", "Bo", "Coco"};

        sort(prices.begin(), prices.end(), [](int a, int b) { return a > b; });
        for (int price : prices) {
            cout << price << endl;
        }

        sort(names.begin(), names.end(), [](const string& a, const string& b) {
            char lastA = a[a.size() - 1];
            char lastB = b[b.size() - 1];
            if (lastA != lastB) {
                return lastA < lastB;
            }
            return a < b;
        });
        for (string name : names) {
            cout << name << endl;
        }
    }
};

    The prices print as 30, 12, 8, 5. The names end in a (Bella, Luna), o (Bo, Coco) and x (Max, Rex), so they print as:

    Bella
Luna
Bo
Coco
Max
Rex

    Common mistakes

    • Mixing up the direction. > puts big values first, < puts small values first.
    • Skipping the tie rule. Without it, names with the same last letter can come out in any order.
    • Using <=. An item that "goes before itself" breaks the rules sort relies on.
    • Taking the last letter of an empty string. size() - 1 is unsigned, so on an empty string it wraps to a huge number. Here every name has letters.

    Key takeaways

    • sort(v.begin(), v.end(), lambda) sorts v in place; the lambda returns true when its first argument goes first.
    • For several rules, return early on the first rule that decides, and fall through to the next rule on a tie.
    • Use strict comparisons, and sort a copy when you need to keep the original.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free