Implementing a dictionary merging tool

Imagine that we have a sorted list of things, and someone else comes up with another sorted list of things, and we want to share the lists with each other. The best idea is to combine both the lists. The combination of both the lists should be sorted too, as this way, it is easy to look it up for specific items.

Such an operation is also called a merge. In order to merge two sorted ranges of items, we would intuitively create a new range and feed it with items from both the lists. For every item transfer, we would have to compare the frontmost items of our input ranges in order to always select the smallest one from what is left from the input. Otherwise, the output range would not be sorted any longer. The following diagram illustrates it better:

The std::merge algorithm can do exactly that for us, so we do not need to fiddle around too much. In this section, we will see how to use the algorithm.

How to do it...

We are going to build up a cheap dictionary...