What is the best way to sort the value of an STL map?

[Jsplinter]

I am using a map in the standard way. It holds keys and values and sorts them by key and works wonderfully. However, after I am through adding to the map, I need to rank the keys based on their associated values. What is the best solution?

A) Take map<myKey, myValue> object and copy by value each element into a multi-map, but reverse the order so that it looks like multimap<myValue,myKey>. This will sort the by the values from the old map object which will now be keys in the multi-map.

B) Create a struct that holds both myKey and myValue

struct myPairs
{
myKey k;
myValue v;
};

and then push_back those objects into a vector for sorting?

C) The same as B, but use pointers. Don't have to copy by value so should be faster

D) Use a container tool from Boost or some other library that I'm not familiar with that works like map, but allows sorting by value.

[ravenous]

I think I'd use a std::set instead of a vector and then sorting. If you do something like:

std::set< valueType > mySet;
for( auto it_map = myMap.begin(); it_map != myMap.end(); ++it_map )
    mySet.insert( it->second );

for( auto it_set = mySet.begin(); it_set != mySet.end(); ++it_set )
    std::cout << *it_set << std::endl;

You'll get a sorted list of the values printed out.

[Jsplinter]

That would be just fine except for:
A) The valueTypes in my map are not all unique.
B) The valueTypes' data is meaningless without the associated key.

[mike_2000_17]

D) Use Boost.Multi-Index. This is a library for keeping an array sorted according to multiple indices (i.e. keys). This is probably the best and easiest way to keep the list "sorted" according to both the key and the value at the same time.

However, if you just want to completely switch from one ordering (according to keys) to another ordering (according to values), then store them as a pair, and make two functors for the two kinds of comparison:

typedef std::pair<MyKey, MyValue> MyPair;

struct CompareByKey {
  bool operator() (const MyPair& a, const MyPair& b) const {
    return a.first < b.first;
  };
};
struct CompareByValue {
  bool operator() (const MyPair& a, const MyPair& b) const {
    return a.second < b.second;
  };
};

Then either you use std::vector and std::sort, or use two sets.

int main() {
  std::vector< MyPair > v;
  //... push all the elements into v.
  std::sort(v.begin(), v.end(), CompareByKey()); 
  //now you have a vector sorted by keys and can be accessed by binary_search.

  std::sort(v.begin(), v.end(), CompareByValue());
  //now you have the same vector but sorted by values.

  //with two sets:
  std::set< MyPair, CompareByKey> sk;
  //insert all the elements into sk and you have a sorted set according to key.

  std::multiset<MyPair, CompareByValue> sv;
  std::copy(sk.begin(), sk.end(), std::back_inserter(sv)); 
  //now you have another set with the values sorted by value.
 
};

You can also have a std::vector of the pairs, and then keep a std::set and a std::multiset that holds the indices into the vector, sorted (with similar kinds of functors) by either way.