[RESOLVED] Define a comparator for std::map<>

[OneEyeMan]

Hi, ALL,
First of all Happy New Year to everybody on the forum.
Now to the problem.

I am trying to define std::map<> container which will stay sorted on the value. Now depending on the key the map should be sorted either from lowest to highest or from highest to lowest.

I can define a comparator and create such a container, but there is no std::map<> function which sets the comparator.

Now I need the container to be a class member so it is accessible from different function of the class.

What's best way to resolve it? Is the only way to split the container for 2 std::map<>'s?

Thank you.

[D_Drmmr]

I am trying to define std::map<> container which will stay sorted on the value. Now depending on the key the map should be sorted either from lowest to highest or from highest to lowest.

Do you mean depending on the type of key or on the value of key?
If it depends on the value of key, you need to write a comparator that works for any set of values.
If it depends on the type of key, you can create your own traits class that provides the correct order. E.g. (didn't check if this compiles/works)

// sort types descending by default
template <class T>
struct MyOrder
{
    typedef std::greater<T> Comparison;
};

// sort text ascending
template <class Ch, class T, class A>
struct MyOrder<std::basic_string<Ch, T, A> >
{
    typedef std::less<std::basic_string<Ch, T, A> > Comparison;
};

template <class Key>
struct MyType
{
    std::map<Key, int, typename MyOrder<Key>::Comparison> mymap;
};

[zerver]

You cannot change the comparator after creation, because doing so would make the current sorting order invalid, and map internally relies on the fact that the sorting order must be correct at all times.

So, one option for you is to define a base class and have two classes that derive from this base class, so that each of them can have a different sorting order.

[OneEyeMan]

Hi,

Do you mean depending on the type of key or on the value of key?
If it depends on the value of key, you need to write a comparator that works for any set of values.
If it depends on the type of key, you can create your own traits class that provides the correct order.

Consider the following code (pseudo-code):

std::map<std::string,std::map<std::string, double> > m_mymap;
std::map<std::string, double> m_temp;

m_temp["Test1"] = 5.0;
m_temp["Test2"] = 6.5;
m_mymap["abc"] = m_temp;
m_temp["Test1"] = 7.5;
m_temp["Test2"] = 3.1;
m_mymap["def"] = m_temp;

What's going to happen is:
m_temp values will change during the program run.
No matter where those values will change (increase/decrease), I'd like to have m_mymap["abc"] to be sorted lowest to highest on the m_temp.second and m_mymap["def"] from highest to lowest.

for( std::map<std::string, std::map<std::string,double>>::iterator it = m_mymap.begin(); it != m_mymap.end(); it++ )
{
    for( std::map<std::string, double>::iterator it1 = it.second.begin(); it1 != it.second.end(); it1++ )
    {
// for m_mymap["abc"] it1 to go from value 1.0 to 100.0 and for m_mymap["def"] - from 100.0 to 1.0 always.
    }
}

I hope this makes it more clear.

Thank you.

[D_Drmmr]

What's going to happen is:
m_temp values will change during the program run.
No matter where those values will change (increase/decrease), I'd like to have m_mymap["abc"] to be sorted lowest to highest on the m_temp.second and m_mymap["def"] from highest to lowest.

So you want to have different objects of the same type (an instance of std::map) that use a different sorting strategy? This can be achieved using a stateful comparator. You need to provide an instance of the comparator to the std::map constructor. You cannot change it after creation of a map object, but as zerver explained that doesn't make any sense anyway.

struct StatefulStringComparator
{
    const bool ascending;
    explicit StatefulStringComparator(bool asc) : ascending(asc) {}

    bool operator ()(const std::string& left, const std::string& right) const
    {
        return ascending ? left < right : right < left;
    }
};

std::map<std::string, int, StatefulStringComparator> ascMap(StatefulStringComparator(true));
std::map<std::string, int, StatefulStringComparator> descMap(StatefulStringComparator(false));

[2kaud]

m_temp values will change during the program run.

I think he's referring to the mapped values of the keys - not the keys themselves. my_map is to sorted by the map value of the keys of m_temp - not by the key itself. The value of the map values of m_temp will change during the execution of the program and when they change, my_map is to remain automatically sorted by map value - one version ascending, one version decending.

[zerver]

You cannot safely sort a map by "second", instead you should use a std::set<std:air<std::string, double>, comparator>:

std::set<std::pair<std::string, double>, AscendingPairComparator> asc;
std::set<std::pair<std::string, double>, DescendingPairComparator> desc;

void updatedata(std::string key, double newval) {
  double oldval = m_temp[key];
  asc.erase(std::pair<std::string, double>(key, oldval));
  asc.insert(std::pair<std::string, double>(key, newval));
  desc.erase(std::pair<std::string, double>(key, oldval));
  desc.insert(std::pair<std::string, double>(key, newval));
  m_temp[key] = newval;
}

[OneEyeMan]

Apologies, for some reason I was not notified about the latest responses.

I think he's referring to the mapped values of the keys - not the keys themselves. my_map is to sorted by the map value of the keys of m_temp - not by the key itself. The value of the map values of m_temp will change during the execution of the program and when they change, my_map is to remain automatically sorted by map value - one version ascending, one version descending.

Yes, this is what I'd like.
I tried to implement it, but got compilation error:

class Comparator
{
	bool operator()(const std::map<wxString,double> &lhs, const std::map<wxString,double> &rhs) const
	{
		std::map<wxString,double>::const_iterator it1 = lhs.cbegin();
		std::map<wxString,double>::const_iterator it2 = rhs.cbegin();
		return (*it1).second < (*it2).second;
	}
};

std::map<std::string,std::map<std::string,double>, Comparator > m_score;

1>c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\map(213): error C2664: 'bool Comparator::operator ()(const std::map<_Kty,_Ty> &,const std::map<_Kty,_Ty> &) const' : cannot convert parameter 1 from 'const std::string' to 'const std::map<_Kty,_Ty> &'
1>          with
1>          [
1>              _Kty=std::string,
1>              _Ty=double
1>          ]
1>          Reason: cannot convert from 'const std::string' to 'const std::map<_Kty,_Ty>'
1>          with
1>          [
1>              _Kty=std::string,
1>              _Ty=double
1>          ]
1>          No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called
1>          c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\map(210) : while compiling class template member function 'std::map<_Kty,_Ty> &std::map<_Kty,std::map<_Kty,_Ty>,_Pr>::operator [](const std::string &)'
1>          with
1>          [
1>              _Kty=std::string,
1>              _Ty=double,
1>              _Pr=Comparator
1>          ]
1>          c:\elance5\baseballdraft\baseballdraft\teamprojections.h(47) : see reference to class template instantiation 'std::map<_Kty,_Ty,_Pr>' being compiled
1>          with
1>          [
1>              _Kty=std::string,
1>              _Ty=std::map<std::string,double>,
1>              _Pr=Comparator
1>          ]

Thank you.

[OneEyeMan]

You cannot safely sort a map by "second", instead you should use a std::set<std:air<std::string, double>, comparator>:

Why I can't use std::map? What is the difference with the std::set?
Thank you.

[D_Drmmr]

Why I can't use std::map? What is the difference with the std::set?
Thank you.

std::map keeps its elements (key-value pairs) sorted based on the keys (which cannot change after they are inserted in the map, you can only remove elements and insert new ones).
std::set keeps its elements (values) sorted based on the values (which also cannot change after they are inserted in the set).
If you have a map and want to reorder it based on the values, then you can create a second map that switches the role of the key and value in each element. You can also have a look at Boost.Bimap.

[OneEyeMan]

Hi,

std::map keeps its elements (key-value pairs) sorted based on the keys (which cannot change after they are inserted in the map, you can only remove elements and insert new ones).
std::set keeps its elements (values) sorted based on the values (which also cannot change after they are inserted in the set).
If you have a map and want to reorder it based on the values, then you can create a second map that switches the role of the key and value in each element. You can also have a look at Boost.Bimap.

Well, std::map<> sorts its elements by the key, but isn't it possible to sort the container by value?
std::set is not a "pair" container, and I need a container based on the "pair" (key/value).

Having the following:

std::map<std::string,std::map<std::string, double> > m_mymap;

seems like a simplest solution...
I can probably define just one sorter function and check for a key of m_mymap (pseudo-code):

if( m_mymap.key == "abc" )
//use forward iterator
else
//use reverse iterator

Are you saying that I will need something like this:

std::set<std:air(std::string,std::map<std::string,double>)> m_mymap;

But then how will it be sorted?

Thank you.

[laserlight]

std::map<> sorts its elements by the key, but isn't it possible to sort the container by value?

Not possible by design, except in the special case where each key is equal to its corresponding value, in which case you might as well use a std::set. The usual problem is that you might want to map from the value to the key as well, in which case you would either have a second map or use Boost.Bimap as was already mentioned.

std::set is not a "pair" container, and I need a container based on the "pair" (key/value).

True, but I note that zerver's post #7 has a simple example of a std::set storing std:air objects. If you need a map, whether a std::map or std::unordered_map, it should be because you need to map keys to values, not solely because you need to store pairs.

[OneEyeMan]

Hi,

Not possible by design, except in the special case where each key is equal to its corresponding value, in which case you might as well use a std::set. The usual problem is that you might want to map from the value to the key as well, in which case you would either have a second map or use Boost.Bimap as was already mentioned.

Well, Boost introduce an extra dependency and second map does not make much sense. ;-)

True, but I note that zerver's post #7 has a simple example of a std::set storing std:air objects. If you need a map, whether a std::map or std::unordered_map, it should be because you need to map keys to values, not solely because you need to store pairs.

std::map<std::string, std::set<std::pair<std::string, double>, AscendingPairComparator> > m_mymap;

Would such construct work?
Then std::set will be sorted in ascending order and depending on the m_mymap key it will use either normal iterator or reverse_iterator.

Will this work?
Now with std::set<std:air<std::string, double>> will I be able to simply change the value of the double, or I will have to delete+insert?

Thank you.

[OneEyeMan]

Anybody?

Thank you.

Hi,

Well, Boost introduce an extra dependency and second map does not make much sense. ;-)

std::map<std::string, std::set<std::pair<std::string, double>, AscendingPairComparator> > m_mymap;

Would such construct work?
Then std::set will be sorted in ascending order and depending on the m_mymap key it will use either normal iterator or reverse_iterator.

Will this work?
Now with std::set<std:air<std::string, double>> will I be able to simply change the value of the double, or I will have to delete+insert?

Thank you.

[Paul McKenzie]

Now with std::set<std:air<std::string, double>> will I be able to simply change the value of the double, or I will have to delete+insert?

A set more than likely uses a tree structure to store the value. You must delete and insert again to keep the internals of the set's structure coherent.

Regards,

Paul McKenzie