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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <iostream> #include <mutex> #include <map> #include <utility> #include <cstdlib> using namespace std; mutex cout_lock; #define trace(x) { scoped_lock<mutex> lock(cout_lock); cout << x << endl; } const int COUNT = 5; int main(int argc, char** argv) { srand((unsigned int)time(NULL)); multimap<int, int> 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<int, int> 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):
Program output.
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