Sorting a std::map by value before output & destroy

Question

I'm aware that map is not prepared to be sorted. It's heavily optimized for fast and random key access and actually doesn't support std::sort.

My current problem is that I've a full map<std::string,int> which I'm not going to use anymore. I just need to extract 10 pairs in value(int) order and destroy it.

The best thing, if it was possible, would be to sort it in place and then iterate it 10 times, but that apparently is not a solution.

I'm trying different solutions as going through a multimap<int,string> (to allow duplicate keys), but I'd like to know if there is a more elegant solution, using stl algorithms as much as posible.

EDIT:

I'm using a map because for the 99% of the time, I need it as a map: fast key lookups to increase values. Just need a good way of later extracting in value order when I don't need the map anymore.

Current approach whould be:

• std::copy the map(std::string,int) to a vector(pair(std::string,int))
• sort the vector
• get the first 10 values
• destroy vector and map

Answer 1

Maps are stored as a tree sorted in key order. You want the 10 smallest (or largest) integer values, and their keys, right?

In that case, iterate the map and put all the key-value pairs in a vector of pairs (std::vector<std::pair<std::string, int> >). I think you can just use the two-iterator-arg constructor of std::vector for this. Then use std::partial_sort on the vector. Specify a comparator to partial_sort, which compares pairs by just comparing the value int, ignoring the key string. Then you have the 10 pairs you want at the start of the vector, and the rest of the vector contains the remaining pairs in an unspecified order.

Code (untested):

typedef std::pair<std::string, int> mypair;

struct IntCmp {
    bool operator()(const mypair &lhs, const mypair &rhs) {
        return lhs.second < rhs.second;
    }
};


void print10(const std::map<std::string,int> &mymap) {
    std::vector<mypair> myvec(mymap.begin(), mymap.end());
    assert(myvec.size() >= 10);
    std::partial_sort(myvec.begin(), myvec.begin() + 10, myvec.end(), IntCmp());

    for (int i = 0; i < 10; ++i) {
        std::cout << i << ": " << myvec[i].first 
            << "-> " << myvec[i].second << "\n";
    }
}

Note that if there are several strings with the same value, either side of the limit of 10, then it's not specified which ones you get. You can control this by having your comparator look at the string too, in cases where the integers are equal.

Answer 2

For iterating by value you could use boost::multi_index. It will looks as follows:

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/hashed_index.hpp>
using namespace boost::multi_index;

struct X {
  X( std::string val_str, int val_int ) : val_str(val_str), val_int(val_int) {};
  std::string val_str;
  int         val_int;
};

typedef multi_index_container<
    X,
    indexed_by<
        hashed_unique< member<X, std::string, &X::val_str> >,
        ordered_non_unique< member<X, int, &X::val_int> >
    >
> X_map;

void func()
{
   X_map data;
   data.insert( X("test", 1) );
   // ...

   // search by val_str 
   // complexity is equal to O(1) for hashed index (worst cast O(n) ), 
   // and O(log n) for ordered index
   X_map::const_iterator it = data.find( "test" );
   // ...

   // iterate in order of val_int
   size_t N = 0;
   for ( X_map::nth_index<1>::type::const_iterator it = data.get<1>().begin(); N < 10 && it != data.get<1>().end(); ++it, ++N ) {
     // copy elements somewhere
   }
}

You could use any index for iteration ( val_str or val_int ).