In my library Countertree ( set, multiset, map multimap concurrent and with access by position like the vectors ) I implemented the map as a data structure and a filter. Applying the filter you obtain the key. With the same nodes of the tree you can build a different maps, only changing the filter used. Imagine you have a map and each node have a code and a name, The map is sorted by the code. Extracting the nodes of the map, putting in a vector and inserting in map sorted by name,(the filter provide the name as key) it a easy operation. The access by positionof the trees , permit you new fast algorithms for create a map from a vector ( a 30000000 nodes need 6 seconds with 1 thread for to create a map, with 4 threads you can do in less than 3 seconds) The STL map need 35 seconds for to do it. All the implementations I know (GCC, VC++, Intel...) use a pair, and don't permit the change of the key The true problem is not to access to other element as use as second key, the problem is the sorting. If you need the data sorted by several keys simultaneously, you need multiindex. If when you sort by a second key, unsort the data by the first key, the procedure described could be good *The library countertree is pending of the final approval . You can find in https://github.com/fjtapia/countertree_2.0)