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 ).

Answer 3

If you iterate using the map iterator, you will get the items sorted on key as it internally uses balanced binary tree to store the values. So you could just extract the 10 values from it using the iterators. Is that what you want or you want to do something else? Please clarify.

EDIT: Instead of using the vector and sorting, you can directly use set and pass the comparison function. Then you can extract the top 10 elements. This is my test code:

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


struct MyTestCompare
{

    bool operator()(const MyPair& firstPair, const MyPair& secondPair) const
    {
        return firstPair.second < secondPair.second;
    }
};

int main()
{
    std::map<std::string, int> m;
    m[std::string("1")] = 10;   
m[std::string("2")] = 40;
m[std::string("3")] = 30;
m[std::string("4")] = 20;



    std::set<MyPair,MyTestCompare> s;
    std::map<std::string, int>::iterator iter = m.begin();
    std::map<std::string, int>::iterator endIter = m.end();
    for(; iter != endIter; ++iter)
    {
        s.insert(*iter);
    }

}

Answer 4

May not be the most elegant way, but you can sort them via value in a set as:

#include <map>
#include <set>
#include <iostream>
#include <string>

using namespace std;

struct sortPairSecond
{
   bool operator()(const pair<string, int> &lhs, const pair<string, int> &rhs)
   {
       return lhs.second < rhs.second;
   }
};


int main (int argc, char *argv[])
{
    cout << "Started...\n";
    map<string, int> myMap;
    myMap["One"]   = 1;
    myMap["Ten"]   = 10;
    myMap["Five"]  = 5;
    myMap["Zero"]  = 0;
    myMap["Eight"] = 8;


    cout << "Map Order:\n---------------\n";
    set<pair<string,int>, sortPairSecond > mySet;
    for(map<string, int>::const_iterator it = myMap.begin(); it != myMap.end(); ++it)
    {
        cout << it->first << " = " << it->second << "\n";
        mySet.insert(*it);
    }

    cout << "\nSet Order:\n--------------\n";
    for(set<pair<string, int> >::const_iterator it = mySet.begin(); it != mySet.end(); ++it)
    {
        cout << it->first << " = " << it->second << "\n";
    }

    return 1;
}

Answer 5

Another possibility is to build a reverse map. For you that would be std::map<int, std::string>. Entries in the reverse map are sorted by their value.

The following is what I have in my tool box for such occasions:

template< typename TK, typename TV, class TP, class TA, typename T1, typename T2 >
inline void asserted_insert(std::map<TK,TV,TP,TA>& m, const T1& k, const T2& v)
{
  typedef std::map<TK,TV,TP,TA>                   map_type;
  typedef typename map_type::value_type           value_type;
  assert( m.insert(value_type(k,v)).second );
}

template< class TMap > struct reverse_map;
template< typename T1, typename T2 > struct reverse_map< std::map<T1,T2> > {
  typedef std::map<T2,T1>                         result_t;
};

template< typename T1, typename T2, class TP1, class TA1, class TP2, class TA2 >
inline void build_reverse_map(const std::map<T1,T2,TP1,TA1>& map, std::map<T2,T1,TP2,TA2>& reverse_map)
{
  typedef std::map<T1,T2,TP1,TA1>                 map_type;

  for( typename map_type::const_iterator it=map.begin(),
                                        end=map.end(); it!=end; ++it ) {
    asserted_insert( reverse_map, it->second, it->first );
  }
}

This code assumes that values are unique, too (and throws an assertion, if this is not the case). If this doesn't apply to your problem, you could easily change the code to use a multi map.