How can I order a map by value efficiently?

Question

Consider a std::map<K,V>. I want to re-order the map by value profiting by an appropriate container std::C<V*> or std::C<V&>, in a way that no copies of values are done to store the elements in C. Furthermore, elements in C must be sorted according to the result of int f(V&) applied to each element. Despite my efforts I could not find an appropriate C and an enough efficient way to build it. Do you have any solution? A small example would be much appreciated.

Answer 1

Seems simple enough.

std::map<K,V> src;
int f(V&) {return 0;}

V* get_second(std::pair<const K,V> &r) {return &(r.second);} //transformation
bool pred(V* l, V* r) { return f(*l)<f(*r); }   //sorting predicate

std::vector<V*> dest(src.size());  //make destination big enough
std::transform(src.begin(), src.end(), dest.begin(), get_second); //transformcopy
std::sort(dest.begin(), dest.end(), pred); //sort

Unless you meant C is supposed to be another map:

std::pair<K,V*> shallow_pair(std::pair<const K,V> &r) 
{return std::pair<K,V*>(r.first, &(r.second));}

std::map<K, V*> dest2;
std::transform(src.begin(), src.end(), 
               std::inserter(dest2,dest2.end()), shallow_pair);

http://ideone.com/bBoXq

This requires the previous map to remain in scope longer than dest, and have no pairs removed until dest is destructed. Otherwise src will need to have been holding smart pointers of some sort.

Answer 2

You can use std::reference_wrapper, like this:

#include <map>
#include <string>
#include <algorithm>
#include <functional>

#include <prettyprint.hpp>
#include <iostream>

template <typename T>
std::ostream & operator<<(std::ostream & o, std::reference_wrapper<T> const & rw)
{
  return o << rw.get();
}

int main()
{
  std::map<int, std::string> m { { 1, "hello"}, { 2, "aardvark" } };
  std::cout << m << std::endl;

  std::vector<std::reference_wrapper<std::string>> v;
  for (auto & p : m) v.emplace_back(p.second);
  std::cout << v << std::endl;

  std::sort(v.begin(), v.end(), std::less<std::string>); // or your own predicate
  std::cout << v << std::endl;

  v.front().get() = "world";
  std::cout << m << std::endl;
}

This prints:

[(1, hello), (2, aardvark)]
[hello, aardvark]
[aardvark, hello]
[(1, hello), (2, world)]

Answer 3

Sounds like you are using multiple containers to represent multiple views into the same dataset. The trouble with this approach is in keeping the containers synchronized and avoiding dangling pointer issues. Boost.MultiIndex was made for just this purpose. A boost::multi_index container stores only one copy of each element, but allows you to access the elements via several indices.

Example:

#include <iterator>
#include <iostream>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/global_fun.hpp>
#include <boost/multi_index/member.hpp>

typedef std::string Key;
typedef int Value;

struct Record
{
    Record(const Key& key, Value value) : key(key), value(value) {}
    Key key;
    Value value;
};

inline std::ostream& operator<<(std::ostream& os, const Record& rec)
{
    os << rec.key << " " << rec.value << "\n";
    return os;
}

inline int sortFunc(const Record& rec) {return -rec.value;}

struct ByNumber{}; // tag

namespace bmi = boost::multi_index;
typedef bmi::multi_index_container<
  Record,
  bmi::indexed_by<
    // sort by key like a std::map
    bmi::ordered_unique< bmi::member<Record, Key, &Record::key> >,

    // sort by less<int> on free function sortFunc(const Record&)
    bmi::ordered_non_unique<bmi::tag<ByNumber>, 
                            bmi::global_fun<const Record&, int, &sortFunc> >
  > 
> RecordSet;

typedef RecordSet::index<ByNumber>::type RecordsByNumber;

int main()
{
    RecordSet rs;
    rs.insert(Record("alpha", -1));
    rs.insert(Record("charlie", -2));
    rs.insert(Record("bravo", -3));

    RecordsByNumber& byNum = rs.get<ByNumber>();

    std::ostream_iterator<Record> osit(std::cout);

    std::cout << "Records sorted by key:\n";
    std::copy(rs.begin(), rs.end(), osit);

    std::cout << "\nRecords sorted by sortFunc(const Record&):\n";
    std::copy(byNum.begin(), byNum.end(), osit);
}

Result:

Records sorted by key:
alpha -1
bravo -3
charlie -2

Records sorted by sortFunc(const Record&):
alpha -1
charlie -2
bravo -3

Answer 4

The place I'd start is to:

• look at Boost::bimap
• create ordering from V -> K via a comparator function object which evaluates f(V&) the way you suggested. (e.g. as in std::map<K,V,C> where C is a comparator class)

Answer 5

How about,

std::set<boost::shared_ptr<V>, compfunc>

where compfunc is a functor which takes two shared_ptr objects and applies the logic in your function?

Excuse the formatting, not good on my phone.

Answer 6

How about something like this (untested pseudo code):

V* g(pair<K,V> &v) { return &v.second; }
bool cmp(V* a, V* b) { return f(*a) < f(*b); }

map<K,V> map;
vector<V*> vec;
vec.reserve(map.size());
transform(map.begin(), map.end(), back_inserter(vec), g);
sort(vec.begin(), vec.end(), cmp);