Custom order by frequency

Why this matters

Many real lists are ranked by popularity. A shop shows its best-selling items first. A log viewer lists the most common error codes at the top. A search box puts the most used tags first. In each case the rule is not "sort by value". The rule is "sort by how many times each value appeared, and use the value to settle ties".

This is a common programming task, and it has a clear shape. First count the values. Then sort them with a rule that looks at the counts. The sorting part is the same tool you have already seen with std::sort and a comparator. What is new here is that the comparator does not look at the values alone. It looks at a second piece of data, the count, that you built before the sort started.

By the end of this lesson you will be able to take a list such as 4, 6, 2, 2, 6, 4, 4, 4, 9 and produce 4, 4, 4, 4, 2, 2, 6, 6, 9 with C++ code that you can explain line by line.

The idea in plain words

Take a small list of numbers:

4 6 2 2 6 4 4 4 9

Count how many times each number appears. Write the counts in a table by hand:

Now decide the order. The rule has two parts:

1. A value with a higher count comes first.
2. If two values have the same count, the smaller value comes first.

Apply the rule to the table. The value 4 has the highest count, so it goes first. The values 2 and 6 both have a count of 2. The tie is broken by value, and 2 is smaller than 6, so 2 comes before 6. The value 9 has the lowest count, so it goes last.

The final order is 4, 4, 4, 4, 2, 2, 6, 6, 9. Each value appears as many times as it did in the input. Only the order has changed.

Notice that the two steps of the rule are separate. The first step is counting, which turns the list into a table. The second step is sorting, which uses the table to decide the order. Keeping them apart makes the code much easier to read.

Step 1: count with a map

In C++, a convenient way to store a count table is std::map. A map is a container that stores pairs of a key and a value. Here the key is the number from the list and the value is how many times it appeared.

#include <map>
#include <vector>
 
std::vector<int> nums{4, 6, 2, 2, 6, 4, 4, 4, 9};
std::map<int, int> count;
for (int x : nums) {
    ++count[x];
}

The line ++count[x] does two things. When x is not yet a key in the map, count[x] creates that key with the value zero. Then ++ adds one to it. When x is already a key, count[x] finds the existing entry and ++ adds one to it. The result is a table where count[4] is 4, count[6] is 2, and so on.

You can think of count as a notebook with one line per number. Each time a number shows up in the list, you add a tally mark on its line.

Step 2: sort with a comparator that reads the table

A comparator is a function that takes two items and returns true when the first item should come before the second. You have used comparators with std::sort already. The difference here is that the comparator asks the count table for information.

Here is the complete first example:

#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
 
int main() {
    std::vector<int> nums{4, 6, 2, 2, 6, 4, 4, 4, 9};
 
    // Step 1: count how often each value appears.
    std::map<int, int> count;
    for (int x : nums) {
        ++count[x];
    }
 
    // Step 2: most frequent first, ties broken by the smaller value.
    std::sort(nums.begin(), nums.end(), [&count](int a, int b) {
        if (count.at(a) != count.at(b)) {
            return count.at(a) > count.at(b);
        }
        return a < b;
    });
 
    for (int x : nums) {
        std::cout << x << ' ';
    }
    std::cout << '\n';
}

Compile it and run it:

g++ -std=c++20 -Wall -o ex1 ex1.cpp
./ex1

The output is:

4 4 4 4 2 2 6 6 9 

The lambda, which is the nameless function written with [&count](int a, int b) { ... }, does the work. Here is how it reads, one part at a time.

The square brackets [&count] say that the lambda can use the variable count from outside. The & means it uses the same table, not a copy of it.

The lambda receives two numbers, a and b. It first compares their counts. If the counts differ, it returns the answer right away. The number with the bigger count should come first, so count.at(a) > count.at(b) is true when a has more occurrences than b.

If the counts are equal, the first if does not run, and the lambda reaches return a < b;. This is the tie-break. The smaller value comes first.

The lambda returns false in every case where a should not come before b. This matters, and the common mistakes section explains why.

Why at and not square brackets

Inside the comparator the code uses count.at(a), not count[a]. The two forms look alike, but they behave differently.

count.at(a) returns the count for a and throws an error if a is not a key in the map. This is a safety check. Every value in nums was counted in step 1, so at never fails here.

count[a] would insert a new key with the value zero if a were missing. Inside a comparator this is a poor habit, because the comparator runs many times and should only read the table, not change it. Using at makes the intent clear: read only.

Second example: sort the letters of a word by frequency

The same method works on characters. Take the word tree. The letter e appears twice, and t and r appear once each. Sorting the letters most frequent first, with ties broken alphabetically, gives e, e, r, t.

#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
 
int main() {
    std::string s = "tree";
    std::unordered_map<char, int> freq;
    for (char c : s) {
        ++freq[c];
    }
 
    std::vector<char> letters(s.begin(), s.end());
    std::sort(letters.begin(), letters.end(), [&freq](char a, char b) {
        if (freq.at(a) != freq.at(b)) {
            return freq.at(a) > freq.at(b);
        }
        return a < b;
    });
 
    std::cout << std::string(letters.begin(), letters.end()) << '\n';
 
    std::string t = "mississippi";
    std::unordered_map<char, int> f2;
    for (char c : t) ++f2[c];
    std::vector<char> l2(t.begin(), t.end());
    std::sort(l2.begin(), l2.end(), [&f2](char a, char b) {
        if (f2.at(a) != f2.at(b)) return f2.at(a) > f2.at(b);
        return a < b;
    });
    std::cout << std::string(l2.begin(), l2.end()) << '\n';
}

The output is:

eert
iiiissssppm

Here the table is an std::unordered_map, which is a hash table. A hash table finds a key quickly by computing a number from it. For a count table of letters, the difference from std::map does not matter much. Both work. std::map keeps its keys in order, while std::unordered_map does not, but the sort does not rely on the order of the table, so either choice is correct.

Look at the second line of output. The word mississippi contains i four times, s four times, p twice, and m once. The letters i and s tie at four, so the tie-break puts i first because i comes before s in the alphabet. The character i has the code 105 and the character s has the code 115, which is why the comparison a < b works on characters directly.

The second part of the example repeats the same steps with new names. Real code usually avoids repeating itself, and the next example packs the same idea into a helper. Here the repetition is kept so you can see every line.

Third example: words, with a count table and pairs

Words are a bigger case. The count table can be a std::map<std::string, int>. Once the counts exist, the program can build a vector of pairs, one pair for each distinct word, and sort the pairs. A pair holds two values side by side, here a word and its count.

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>
 
int main() {
    std::vector<std::string> words{"pear", "kiwi", "apple", "pear", "fig", "apple", "pear", "kiwi"};
 
    std::map<std::string, int> count;
    for (const auto& w : words) {
        ++count[w];
    }
 
    // Turn each distinct word into (word, count) and sort the pairs.
    std::vector<std::pair<std::string, int>> pairs(count.begin(), count.end());
    std::sort(pairs.begin(), pairs.end(), [](const auto& a, const auto& b) {
        if (a.second != b.second) {
            return a.second > b.second;
        }
        return a.first < b.first;
    });
 
    // Write each word back as many times as it appeared.
    std::vector<std::string> result;
    for (const auto& [word, n] : pairs) {
        for (int i = 0; i < n; ++i) {
            result.push_back(word);
        }
    }
 
    for (const auto& w : result) {
        std::cout << w << ' ';
    }
    std::cout << '\n';
}

The output is:

pear pear pear apple apple kiwi kiwi fig 

This version differs in one useful way. The sort works on the distinct words only, four of them in this input, instead of on all eight words. When a list has many repeats, sorting the distinct values is less work. The expansion step at the end then writes each word back out the number of times it appeared.

The comparator takes const auto& parameters. The word auto tells the compiler to work out the type from the pair it receives, so the same lambda works for any pair type. The const & means the lambda reads each pair without copying it and without changing it.

The loop for (const auto& [word, n] : pairs) is a structured binding. It takes each pair and gives its two parts the names word and n. Without it, the same code would be pair.first and pair.second. Both forms are correct. The structured binding reads more clearly when the names are meaningful.

Check the tie in the output. The words apple and kiwi both appear twice. The tie-break puts apple first, because apple comes before kiwi alphabetically. The word fig appears once, so it comes last.

Which version to use

The first example is the smallest. Use it when the values are numbers and you only need the sorted list. The second example is a good model for characters in a string. The third example is the one to reach for when the values are longer, such as words, or when you want the distinct values and their counts as an intermediate result. The pair form is also useful when you later need to print the counts, because the counts are already stored next to each value.

Fourth example: records counted by one field

Real data is rarely a list of plain numbers. A log is a list of records, and each record has several fields. The method stays the same. Pick the one field that defines a value, count that field, and let the comparator read the count through the field.

Suppose each log event has an error code and a message. The task is to list the events so that the most common error code comes first.

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>
 
struct Event {
    std::string code;
    std::string message;
};
 
int main() {
    std::vector<Event> events{
        {"E42", "disk full"},
        {"E17", "timeout"},
        {"E42", "disk full"},
        {"E08", "bad input"},
        {"E17", "timeout"},
        {"E99", "unknown"},
        {"E17", "timeout"},
    };
 
    std::map<std::string, int> count;
    for (const auto& e : events) {
        ++count[e.code];
    }
 
    std::sort(events.begin(), events.end(), [&count](const Event& a, const Event& b) {
        if (count.at(a.code) != count.at(b.code)) {
            return count.at(a.code) > count.at(b.code);
        }
        return a.code < b.code;
    });
 
    for (const auto& e : events) {
        std::cout << e.code << ' ' << e.message << '\n';
    }
}

The output is:

E17 timeout
E17 timeout
E17 timeout
E42 disk full
E42 disk full
E08 bad input
E99 unknown

The code E17 appears three times, so its three events come first. The code E42 appears twice, and it comes next. The codes E08 and E99 each appear once, and the smaller code E08 comes first.

The comparator takes whole records now, so it reads a.code and b.code instead of the values themselves. Everything else is the same. The count table is keyed by the code, and the tie-break compares codes.

Notice what the sort does not guarantee. Two events with the same code are equal under this comparator, so their order after the sort is not promised. In this output it does not matter, because events with the same code also have the same message. If the original order of equal records must be kept, use std::stable_sort, which keeps equal items in their original order. The stability lesson in the sorting module explains that choice.

Mistakes to watch for

Mistake 1: comparing counts but not breaking ties

The most common error is to write the comparator with only the count test:

std::sort(nums.begin(), nums.end(), [&count](int a, int b) {
    return count.at(a) > count.at(b);
});

This compiles, and it sorts by frequency. But ties are left to chance. The C++ standard does not promise any particular order for items that compare as equal in std::sort. Here is what one run of this version printed for the same list:

4 4 4 4 6 2 2 6 9 

The two 6s and the two 2s appear in a different order from the first example, where the 2s came first. The output looks reasonable, but it is not the rule the program was meant to follow. A different compiler or a different list can change the tie order again. When a tie-break is part of the rule, it must be written into the comparator.

Mistake 2: adding || to a comparator

Some people try to write the whole rule as one line:

return count.at(a) > count.at(b) || a < b;

This looks shorter, but it does not express the rule. It says that a smaller value comes first even when its count is lower. Run it on the list 1, 2, 2, 2, 1, where the value 2 appears three times and the value 1 appears twice:

1 2 2 2 1 

A 1 comes first, even though 2 is the most frequent value, and the other 1 ends the list. The safe form is the one in the examples: compare counts first, and only if they match, compare values. The lesson on bad comparator bugs covers the rules a comparator must follow.

Mistake 3: using square brackets on a read-only table

If the table is passed in as const, which is a common way to say "read only", then [] does not compile. Suppose the table is read through a const reference, and the comparator uses square brackets:

const auto& view = count;
std::sort(nums.begin(), nums.end(), [&view](int a, int b) {
    if (view[a] != view[b]) {
        return view[a] > view[b];
    }
    return a < b;
});

Here is a real error from g++ 15 for a full program with this comparator, with the first lines shown:

bad.cpp: In lambda function:
bad.cpp:14:19: error: passing 'const std::map<int, int>' as 'this' argument discards qualifiers [-fpermissive]
   14 |         if (view[a] != view[b]) {
      |                   ^

The message says that operator[] can change the map, so it cannot be called on a constant map. The fix is to use at, which only reads. The message is long, but the important words are const std::map and operator[]. When you see them, look for a square bracket on a table that was declared const.

Mistake 4: sorting the list you are counting

It is tempting to count and sort in one loop, or to count inside the comparator. Counting inside the comparator is a bug. The comparator runs many times during the sort, so the counts would be added again and again, and the result would not match the list. Count first, in a loop that finishes before the sort begins.

Mistake 5: reversing the direction by accident

Changing > to < in the count test gives the least frequent values first. This is correct when you want that order, but it is easy to do by accident. Check the output on a small list that you know by heart. If the most common value is at the end, the direction is reversed.

Practice

Exercise 1. Use the first example on the list 5, 1, 5, 3, 1, 5. Write the output before you run the code.

Show the answer

Count the values. The value 5 appears three times, the value 1 appears twice, and the value 3 appears once. Most frequent first gives 5, 5, 5, then 1, 1, then 3. The output is 5 5 5 1 1 3. The program prints exactly that.

Exercise 2. Change the first example so the least frequent value comes first, and ties are still broken by the smaller value. Use the same list as Exercise 1.

Show the answer

Flip the count test to count.at(a) < count.at(b). The value 3 has the lowest count, so it comes first. Then the 1s, then the 5s. The output is 3 1 1 5 5 5. The tie-break line stays the same.

Exercise 3. Sort the letters of the word banana most frequent first, ties broken alphabetically.

Show the answer

The letter a appears three times, n twice, and b once. The sorted letters are a, a, a, n, n, b. Written as a string, the output is aaannb. Using the second example's code with banana as the input gives this result.

Exercise 4. Write a program that reads one sentence, counts the words, and prints the two most common distinct words. Use the pair method from the third example. Break ties alphabetically. Test it on the cat and the dog and the bird.

Show the answer

The word the appears three times and and appears twice. The other words appear once each. The two most common distinct words are the and and, and the program prints the and. To read the sentence, split on spaces. A simple way is to add a space to the end of the text, then walk over each character and collect letters until a space appears. This is a practical method for practice, although a real program might use std::istringstream instead.

Exercise 5. Find the bug in this comparator and explain what goes wrong.

std::sort(nums.begin(), nums.end(), [&count](int a, int b) {
    return count.at(a) >= count.at(b);
});

Show the answer

The >= operator returns true when two items have equal counts. A comparator must return false for equal items. With >=, the sort can ask whether an item comes before an equal item and get true. That breaks the rule the sort relies on, and the standard says the result is undefined, so the sort may give a wrong order or read outside the vector. The fix is to use > and add the tie-break, as in the first example.

Summary

• Build a count table first, using a map or an unordered map and ++count[x].
• Sort with a comparator that compares counts first, and compares values only when the counts are equal.
• Use at inside the comparator because it only reads the table.
• Writing the tie-break into the comparator makes the order fixed. Relying on the sort to keep ties in order does not.
• Sorting distinct values with their counts is less work than sorting every repeated item, and it fits when the output needs the counts too.