Multisets and Key-Based Data Processing

A set throws duplicates away. Sometimes the duplicates are the data: two players with the same score, three noodles of the same length, the same price on two items. A multiset keeps every copy — and keeps them sorted. And once sets and maps hold your data, most problems about records — names, IDs, dates, scores — come down to one question: what is the key?

A set that keeps duplicates

A multiset is declared and filled like a set:

It prints

A multiset has the operations of a set, with copies allowed:

• insert(x) always adds a copy, and size() counts every copy: 6.
• count(x) is how many copies of x there are: 3 sevens.
• The walk visits every copy, smallest to largest. *ms.begin() is the smallest value and *ms.rbegin() the largest; lower_bound and upper_bound work as in a set.

Removing one copy

The last two lines of that program are the trap of this lesson:

• ms.erase(x) removes every copy of x;
• ms.erase(ms.find(x)) removes one copy: find points at a single copy, and erasing a position removes just that one.

find returns ms.end() when x isn't there, and erasing end() breaks the program, often with a crash — so check first, unless the problem promises that x is present:

Practise the difference: each bag has to end up exactly like the target, and there are just enough moves for the shortest way.