A junior colleague asked me about the following problem: given a 

std::map
or 
std::multimap
of key to value pairs, sort it by values; or turn it into value to key mapping.
In order to solve this problem we need two data structures: the source 
std::map
or 
std::multimap
of key to value pairs, and a second, output 
std::multimap
in which we will invert the pairs (
std::multimap
because in the source different keys can point at the same value; the value in the source will become the key in the output, and 
std::multimap
will handle duplicates).

The solution is to walk the source data structure of key to value pairs, and build the output data structure of value to key pairs.

Complete listing:

#include 
#include 
#include 
#include 
#include 
using namespace std;

mutex cout_lock;
#define trace(x) { scoped_lock lock(cout_lock); cout << x << endl; }

const int COUNT = 5;

int main(int argc, char** argv)
{
    srand((unsigned int)time(NULL));

    multimap m1;
    for(int i = 0; i < COUNT; ++i)
        m1.insert(make_pair(rand() % 10, rand() % 10));

    trace("Source (Key -> Value):");
    for(const auto& it : m1)
        trace(it.first << " -> " << it.second);

    multimap m2;
    for(const auto& it : m1)
        m2.insert(make_pair(it.second, it.first));

    trace("Output (Value -> Key):");
    for(const auto& it : m2)
        trace(it.first << " -> " << it.second);

    return 1;
}

Source (Key -> Value):
2 -> 4
6 -> 8
8 -> 4
9 -> 6
9 -> 2
Output (Value -> Key):
2 -> 9
4 -> 2
4 -> 8
6 -> 9
8 -> 6
Program ended with exit code: 1

Program output.

Leave a Reply