display map every time it is updated sorted by value

Question

basically, I have the

map<std::string, int>

so if i have

• foo 5
• bar 10
• jack 3

in the map, I want to display it (notice the reverse order)

• bar 10
• foo 5
• jack 3

And every time it is updated, I want iterate through all the elements, cout them, sorted by value. What is the good way to implement that? should I provide a comparator to the constructor?

I want to note that values in the map will be updated at least 100 million times, so efficiency is crucial, where as extra-space is no problem

Please no Boost solutions...thx

Answer 1

Well, you have to sort by key. The easiest way to "sort by value" is to use a multimap with the key and value switched. So here's a way to do that (note -- i don't have access to a compiler right now, so if it doesn't compile, I'm sorry):

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

typedef std::multimap<int, std::string, std::greater<int> > MapType;
struct MapKeyOutput
{
    void operator()(const MapType::value_type& val)
    {
        std::cout << val.second << " " << val.first << "\n";
    }
}

void display_insert(MapType& m, const std::string& str, int val)
{
    m.insert(std::make_pair(val, str));
    std::for_each(m.begin(), m.end(), MapKeyOutput());
}

int main()
{
    MapType m;
    display_insert(m, "Billy", 5);
    display_insert(m, "Johnny", 10);
}

You could also make a map class that uses a multimap internally, I just didn't want to type it out. Then display_insert would be some member function instead. This should demonstrate the point, though. Points of interest:

typedef std::multimap<int, std::string, std::greater<int> > MapType;

Note the comparator is greater<int> to sort descending. We're using a multimap so more than one name can have the same number.

struct MapKeyOutput
{
    void operator()(const MapType::value_type& val)
    {
        std::cout << val.second << " " << val.first << "\n";
    }
}

This is a function object to output one element in the map. second is output before first so the order is what you want.

std::for_each(m.begin(), m.end(), MapKeyOutput());

This applies our function object to every element in m.

Answer 2

The previous responses have the inconvenience not to take into account the initial requirements (the key is std::string and the value is int).

EDITED: following the comments, I suppose presenting it directly with a Bimap is better :)

So here we go, right in!

#include <boost/bimap.hpp>

class MyMap
{
  struct name {};
  struct value {};

  typedef boost::tagged<name, std::string> tagged_name;
  typedef boost::tagged<value, int> tagged_value;

  // unordered_set_of: guarantees only unicity (not order)
  // multi_set_of: guarantees only order (not unicity)
  typedef boost::bimap< boost::unordered_set_of< tagged_name >,
                        boost::multi_set_of< tagged_value,
                                             std::greater< tagged_value >
                                           >
                      > impl_type;
 public:
   // Redefine all usual types here
   typedef typename impl_type::map_by<name>::const_iterator const_iterator;
   typedef typename impl_type::value_type value_type;


   // Define the functions you want
   // the bimap will not allow mutators because the elements are used as keys
   // so you may want to add wrappers

   std::pair< iterator, bool > insert(const value_type & x)
   {
     std::pair< iterator, bool > result = m_impl.insert(x);
     if (result.second) this->display();
     return result;
   } // insert

   iterator insert(iterator position, const value_type & x)
   {
     iterator result = m_impl.insert(x);
     this->display();
     return result;
   } // insert

   template< class InputIterator >
   void insert(InputIterator first, InputIterator last)
   {
     m_impl.insert(first, last);
     this->display();
   } // insert

 private:
   void display() const
   {
     // Yeah I know about std::for_each...
     typedef typename impl_type::map_by<value>::const_iterator const_it;

     for (const_it it = m_impl.begin(), end = m_impl.end(); it != end; ++it)
     {
       // Note the inversion of the 'second' and 'first',
       // we are looking at it from the right
       std::cout << it->second << " " << it->first << std::endl;
     }
   }

   impl_type m_impl;
}; // class MyMap

Here you go.

I strongly suggest that you consult the bimap documentation though. There are a lot of possibilities for storing (set_of, unordered_set_of, unconstrained_set_of, the muli variants, the list_of variant...) so there is probably one that could do what you want.

Then you also have the possibility to just sort each time you display:

#include <set>
#include <map>

// Just use a simple std::map<std::string,int> for your impl_type
// Mutators are allowed since the elements are sorted each time you display

struct Comparator
{
  bool operator(const value_type& lhs, const value_type& rhs) const
  {
    return lhs.second < rhs.value;
  }
};

void display() const
{
  typedef std::multi_set<value_type, Comparator> sort_type;
  sort_type mySet;

  std::copy(m_impl.begin(), m_impl.end(), std::inserter(mySet, mySet.end()));

  for (sort_type it = mySet.begin(), end = mySet.end(); it != end; ++it)
  {
    std::cout << it->first<< " " << it->second << std::endl;
  }
}

It should be easier to understand my point now :)

Answer 3

If you want a performant map sorted by both key and value, you want Boost MultiIndex, it gets updated (resorted) on every update (which you have to do manually) and has a good documentation.

Answer 4

struct keyval_t { std::string key; int val; };
int operator<(const keyval_t &a, const ketval_t &b)
{ return a.val<b.val || (a.val==b.val && a.key<b.key); }

Then you need one map and one set:

map<std::string, int>; set<keyval_t>;

On update, you need to look up the map first to determine the key-value pair and then update both map and set. On printing, you just iterate through the set. In terms of theoretical time complexity, this is optimal. It doubles the memory, though. Does this meet your goal?

To reduce memory, you may consider the following:

map<std::string,uint64_t>; set<uint64_t>;

The value of the map (also the key of the set) is: (uint64_t)val<<32|counter, where counter is something that differentiates identical values. For example, whenever you insert a key, increase the counter by 1. You do not need to update the counter when you update the value. If you do not like uint64_t, use pair<int,int> instead. This solution is also faster as it avoids comparisons between strings.