CODEWITHSUNDEEP
c++stlsorting
Martin
Martin

Reputation: 9369

How can I order a map by value efficiently?

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.

Upvotes: 3

Views: 420

Answers (6)

Emile Cormier
Emile Cormier

Reputation: 29229

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

Upvotes: 1

Kerrek SB
Kerrek SB

Reputation: 477640

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

Upvotes: 2

Mooing Duck
Mooing Duck

Reputation: 66981

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.

Upvotes: 2

znkr
znkr

Reputation: 1756

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

Upvotes: 0

Nim
Nim

Reputation: 33655

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.

Upvotes: 0

Jason S
Jason S

Reputation: 189886

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)

Upvotes: 0

Related Questions