Multisets and counted maps

Why this matters

Many real collections hold the same value more than once. A shop has three tickets at 50 rupees and two at 80. A warehouse holds five boxes of the same part. A class has four students with the same exam score. In each case the program must answer questions such as "how many copies are left?", "remove one copy", or "what is the smallest value still in stock?".

A plain set cannot hold a value twice, so it does not fit. A plain vector can hold duplicates, but finding the copies and removing one of them takes a search through the whole list each time. C++ offers two standard ways to handle repeated values in an ordered way. The first is std::multiset, which stores every copy as its own element. The second is a map from each value to a count, which is the same idea as a counter. This lesson shows both, the mistakes that come from each, and how to choose between them.

The lesson on hash maps and the one on ordered maps and sets already covered map and set. This lesson assumes you know that a map stores key and value pairs, and that a set stores each value once.

In Java, the same job is usually done with TreeMap<Integer, Integer>, which stores a value and its count in sorted order. The code in this lesson is C++ only.

The idea: one element per copy

A multiset is a sorted container that allows duplicates. Each copy is its own element. If you insert the value 12 three times, the multiset holds three elements that all equal 12. The elements are kept in sorted order, just as in a set, so the smallest value is always first.

Think of a box of identical coins. Each coin is a separate thing in the box, but they all have the same value. A multiset works like that box. Counting coins means counting the items in the box. Taking one coin out means removing one item.

Here is a small program. It inserts six prices and then prints the count of 12 and the sorted list.

#include <iostream>
#include <set>
using namespace std;
 
int main() {
    multiset<int> prices = {12, 8, 12, 5, 12, 8};
    cout << "size " << prices.size() << '\n';
    cout << "copies of 12: " << prices.count(12) << '\n';
    cout << "sorted:";
    for (int p : prices) cout << ' ' << p;
    cout << '\n';
}

The output is:

size 6
copies of 12: 3
sorted: 5 8 8 12 12 12

The size is 6 because the multiset has six elements. The count call returns how many elements equal 12. The loop prints the elements in sorted order, so the two 8s appear together and the three 12s appear together.

The count function does not just look up one element. It finds the block of equal values and counts them, so its cost grows with the number of copies. For a block of 3 copies, that is a few steps. For a block of 100 000 copies, it is 100 000 steps. Keep this in mind when a value has many copies.

Removing one copy at a time

The most common task with repeated values is removing one copy. A multiset has two erase forms that look alike and behave very differently.

erase(value) removes every element equal to the value. erase(iterator) removes only the element the iterator points to. An iterator is an object that points to one element inside a container, as a bookmark points to one page of a book.

To remove one copy, find one copy first and erase that position:

auto it = prices.find(12);
if (it != prices.end()) prices.erase(it);

The find call returns an iterator to one element equal to 12, or prices.end() if there is none. The check against end() is needed, because end() is not a real element. Erasing it is an error.

The next program adds the removal and then shows what erase(value) does. It continues from the first program.

#include <iostream>
#include <set>
using namespace std;
 
int main() {
    multiset<int> prices = {12, 8, 12, 5, 12, 8};
 
    auto it = prices.find(12);
    if (it != prices.end()) prices.erase(it);
    cout << "after one removal, copies of 12: " << prices.count(12) << '\n';
 
    prices.erase(8);
    cout << "after erase(8): size " << prices.size() << '\n';
    for (int p : prices) cout << ' ' << p;
    cout << '\n';
}

The output is:

after one removal, copies of 12: 2
after erase(8): size 3
 5 12 12

After the first removal, two 12s are left. The call erase(8) removed both 8s, so the size dropped from 5 to 3. If the goal was to remove one 8, this call is wrong, and the program gives no error to show the mistake.

Trace the first removal on the sorted list 5 8 8 12 12 12. find(12) returns an iterator to the first 12 in the sorted order. Erasing that position leaves 5 8 8 12 12. The removed element is one copy, and the other copies stay where they are.

Looking at a block of copies

Because the copies are next to each other in sorted order, a multiset can find the whole block quickly. equal_range(value) returns two iterators. The first points to the first copy of the value, and the second points one place past the last copy. distance counts the steps between them.

The next example uses this to find the smallest value that has at least two copies. The loop jumps from one distinct value to the next. upper_bound(*it) returns an iterator to the first element that is larger than the current value. This skips all the copies of the current value in one step, so the loop never looks at the same value twice.

#include <iostream>
#include <set>
using namespace std;
 
int main() {
    multiset<int> ms = {4, 9, 4, 7, 9, 9, 1};
 
    for (auto it = ms.begin(); it != ms.end(); it = ms.upper_bound(*it)) {
        if (ms.count(*it) >= 2) {
            cout << "first repeated value: " << *it << '\n';
            break;
        }
    }
 
    auto [lo, hi] = ms.equal_range(9);
    cout << "copies of 9 from equal_range: " << distance(lo, hi) << '\n';
}

The output is:

first repeated value: 4
copies of 9 from equal_range: 3

The sorted list is 1 4 4 7 9 9 9. The loop starts at 1. The count of 1 is one, so it moves to upper_bound(1), which points to the first 4. The count of 4 is two, so the loop stops and prints 4. Without the upper_bound jump, the loop would step through the second 4 and waste time on it.

The equal_range line returns the block of 9s. The distance between its two iterators is 3, which matches the three copies.

Buying the cheapest ticket within a budget

The third example combines the parts above with one more call. A customer has a budget of 45 rupees and wants the cheapest ticket that costs at least that much, or the nearest ticket above the budget. The question is not "is 45 in the stock?". It is "what is the first price at or above 45?".

lower_bound(value) returns an iterator to the first element that is not less than the value. In a sorted multiset, that is the first element equal to the value, or the first element above it. If every element is smaller, it returns end(). The function buy_cheapest_within uses lower_bound, reads the price, and erases that one position, so the stock goes down by one copy.

#include <iostream>
#include <set>
using namespace std;
 
// Buys the cheapest ticket priced at or above the budget.
// Returns the price bought, or -1 when every ticket costs less.
int buy_cheapest_within(multiset<int>& prices, int budget) {
    auto it = prices.lower_bound(budget);
    if (it == prices.end()) return -1;
    int price = *it;
    prices.erase(it);
    return price;
}
 
int main() {
    multiset<int> prices = {50, 20, 50, 80, 20, 20};
    cout << "bought: " << buy_cheapest_within(prices, 45) << '\n';
    cout << "bought: " << buy_cheapest_within(prices, 45) << '\n';
    cout << "bought: " << buy_cheapest_within(prices, 45) << '\n';
    cout << "bought: " << buy_cheapest_within(prices, 90) << '\n';
    cout << "left:";
    for (int p : prices) cout << ' ' << p;
    cout << '\n';
}

The output is:

bought: 50
bought: 50
bought: 80
bought: -1
left: 20 20 20

The sorted stock starts as 20 20 20 50 50 80. The first call with budget 45 skips the three 20s, because they are below the budget. It returns the first 50 and erases it, leaving 20 20 20 50 80. The second call returns the other 50. The third call skips the 20s and returns 80, because no 50 is left. The fourth call asks for a ticket at 90 or more. Nothing is that expensive, so the function returns -1 and removes nothing.

A hash set or hash map cannot answer this question quickly, because it has no order. The sorted multiset answers it in O(log n) time (explained below), and the erase at the returned position costs about the same. This is the main reason to choose an ordered container over a hash container when the program needs "the nearest value above" or "the smallest value at least".

The function returns -1 as a signal, which is a common pattern in small programs. A larger program would return std::optional<int>, which holds either a value or nothing, so the caller cannot mistake -1 for a price.

A counted map

A multiset stores one element per copy. If one value has a million copies, the multiset holds a million elements. A counted map stores each distinct value once, together with a count. It is a std::map<int, int>: the key is the value, and the number is how many copies there are.

The counted map is useful when the number of copies is large, or when the program only needs the distinct values and their counts. A shop that stores 500 tickets at one price needs one entry in the map, not 500 elements.

The next program is a small ticket stock. Each price is a key, and the count is the number of tickets left at that price.

#include <initializer_list>
#include <iostream>
#include <map>
using namespace std;
 
// Removes one ticket at this price. Returns false if none is left.
bool sell_one(map<int, int>& stock, int price) {
    auto it = stock.find(price);
    if (it == stock.end()) return false;
    if (--it->second == 0) stock.erase(it);
    return true;
}
 
int main() {
    map<int, int> stock;
    for (int price : {50, 20, 50, 80, 20, 20}) ++stock[price];
 
    for (const auto& [price, n] : stock) cout << price << " x" << n << '\n';
 
    cout << "sell 20: " << sell_one(stock, 20) << '\n';
    cout << "sell 80: " << sell_one(stock, 80) << '\n';
    cout << "sell 80: " << sell_one(stock, 80) << '\n';
 
    cout << "left:\n";
    for (const auto& [price, n] : stock) cout << price << " x" << n << '\n';
}

The output is:

20 x3
50 x2
80 x1
sell 20: 1
sell 80: 1
sell 80: 0
left:
20 x2
50 x2

The line ++stock[price] adds one to the count for that price. If the price is not yet in the map, stock[price] creates the entry with a count of 0 and then the ++ makes it 1. This is the same idea as the word counting from the hash map lessons.

The function sell_one shows the full pattern for removing one copy from a counted map:

1. Find the key. If it is missing, there is nothing to remove.
2. Subtract one from the count.
3. If the count is now 0, erase the key. This step is easy to forget, and it is the subject of the next section.

Trace the calls. The stock starts as 20 with three tickets, 50 with two, and 80 with one. Selling at 20 leaves two. The first sale at 80 leaves zero, so the key 80 is erased and the map holds two keys. The second sale at 80 finds no key, so it returns 0 and prints sell 80: 0.

Choosing between the two

Both structures keep values in sorted order and both can remove one copy. They differ in what they store and how much memory they use.

Use a multiset when each copy is a separate thing that needs its own identity, or when the code naturally works with the copies one by one. Use a counted map when the number of copies is large, or when only the counts matter. A counted map is also easier to print as a summary, because each distinct value appears once.

Both are ordered, so both can answer "what is the smallest value?" by looking at the first element or the first key. Both also cost O(log n) time for a single insert, lookup or erase, where n is the number of elements or distinct keys. Big-O notation says how the cost grows with the size of the input. O(log n) grows slowly: doubling the size adds one more step.

The unordered version, unordered_multiset, exists, but it does not keep the copies in order. Use it only when order does not matter.

Common mistakes

Erasing by value when one copy was meant

The most common error is erase(value) when the program meant to remove one copy. This removes every copy. The second program in the removal section showed this. The program printed after erase(8): size 3 because both 8s were removed. The fix is to find one copy and erase that iterator.

A small check makes the difference clear. For the multiset {2, 2, 2}, erase(2) leaves nothing:

multiset<int> twos = {2, 2, 2};
twos.erase(2);
cout << "size after erase(2): " << twos.size() << '\n';

The output is size after erase(2): 0.

Leaving a zero count in the map

If sell_one did not erase the key when the count reached 0, the map would still hold 80 with a count of 0. The program would still print 80 x0 in its listing, and size() would count the key. A count of 0 means the value is not there, so the key must be erased. Keep the erase step, as in the code above.

Reading a missing key creates it

operator[] on a map inserts the key if it is missing. A read such as stock[99] looks harmless, but it adds the key with a count of 0. This program checks the effect:

#include <iostream>
#include <map>
using namespace std;
 
int main() {
    map<int, int> stock = {{20, 2}, {50, 1}};
    cout << "size before lookup: " << stock.size() << '\n';
    int n = stock[99];
    cout << "count for 99: " << n << '\n';
    cout << "size after lookup: " << stock.size() << '\n';
}

The output is:

size before lookup: 2
count for 99: 0
size after lookup: 3

To read a count without changing the map, use find, which does not insert, or at, which throws an exception if the key is missing.

Storing a struct in a multiset without a comparison

A multiset keeps its elements in sorted order, so it must be able to compare two of them. An int can be compared with <. A struct cannot, unless you write operator< for it or pass a comparison as a template argument. This program stores a Ticket struct with no comparison:

#include <iostream>
#include <set>
#include <string>
using namespace std;
 
struct Ticket {
    string seat;
    int price;
};
 
int main() {
    multiset<Ticket> sold;
    sold.insert({"A1", 50});
    cout << sold.size() << '\n';
}

g++ 15 stops with this error:

/usr/include/c++/15/bits/stl_function.h:408:20: error: no match for ‘operator<’ (operand types are ‘const Ticket’ and ‘const Ticket’)

The fix is to add an operator< to Ticket that compares the fields in the order that makes sense for the program, for example by price first and then by seat.

Using an iterator after it was erased

After erase(it), the iterator it points to an element that no longer exists. Using it again is undefined behaviour. This means the program may crash, print wrong values, or appear to work. Do not reuse the iterator after the erase. If the loop must continue past the erased element, take the iterator that erase returns, which points to the next element.

Practice

Exercise 1

Given the multiset {3, 3, 5, 8, 8, 8}, find the value with the most copies. If two values tie, print the smaller one. Print the value and its number of copies.

Show the answer

#include <iostream>
#include <set>
using namespace std;
 
int main() {
    multiset<int> ms = {3, 3, 5, 8, 8, 8};
    int best = 0;
    size_t best_count = 0;
    for (auto it = ms.begin(); it != ms.end(); it = ms.upper_bound(*it)) {
        size_t c = ms.count(*it);
        if (c > best_count) {
            best_count = c;
            best = *it;
        }
    }
    cout << "most copies: " << best << " (" << best_count << ")\n";
}

The output is most copies: 8 (3). The loop checks each distinct value once, in increasing order. It replaces the best value only when a count is strictly greater, so the smaller value wins a tie.

Exercise 2

Remove exactly two copies of 7 from the multiset {7, 7, 7, 1}. Print how many 7s are left and the total size.

Show the answer

Call find(7) and erase on the iterator, twice. After two removals, one 7 is left and the size is 2. The output is after removing two 7s: 1 copies, size 2.

multiset<int> three = {7, 7, 7, 1};
for (int i = 0; i < 2; ++i) {
    auto it = three.find(7);
    if (it != three.end()) three.erase(it);
}
cout << "after removing two 7s: " << three.count(7) << " copies, size " << three.size() << '\n';

Exercise 3

What is the size of the multiset {2, 2, 2} after erase(2)? Answer before you run the code, then check.

Show the answer

The size is 0. erase(value) removes every element equal to the value, so all three 2s are removed. The output is size after erase(2): 0.

Exercise 4

A counted map holds 20 with a count of 2 and 50 with a count of 1. The program then runs stock[99] and prints the size. What is the size?

Show the answer

The size is 3. The read stock[99] inserts the key 99 with the count 0, so the map now has three keys. Use find to check for a key without inserting it.

Exercise 5

The multiset is {1, 2, 2, 3}. The code runs ms.erase(ms.find(2)), then prints ms.count(2). What is printed?

Show the answer

The output is 1. find(2) returns an iterator to one of the two 2s. Erasing that iterator removes one copy, so one 2 is left. If the code had used ms.erase(2) instead, the output would be 0.

Summary

• A multiset stores one element per copy, in sorted order. Use count to count copies and find to get one copy.
• To remove one copy, erase the iterator from find. erase(value) removes every copy.
• equal_range gives the block of copies, and upper_bound skips all copies of a value in one step.
• A counted map stores each distinct value once with its count. Erase the key when its count reaches 0.
• Reading a missing key with operator[] inserts it, so use find for a check that should not change the map.