Sort a map using the value, not the key.

[Diego Barros]

Hello,

I was wondering if it was posibble to sort a map using the values and not
the keys. Sorting on the keys (if they were strings, for example) is
currently possible. What about, for example, if I have a map with string
keys and object values, can I have custom sorting of the items in the map
based on member variables of said object?

Any help would be appreciated. Thanks.

Cheers,
Diego

 

[John Harrison]

Hello,

I was wondering if it was posibble to sort a map using the values and not
the keys. Sorting on the keys (if they were strings, for example) is
currently possible. What about, for example, if I have a map with string
keys and object values, can I have custom sorting of the items in the map
based on member variables of said object?

Any help would be appreciated. Thanks.

Cheers,
Diego

Its the sorting on the keys that makes a map work, so no, you cannot have a
map that is sorted on the values.

Why do you want a map sorted on values? There are probably several things
you could do instead. If you explain what you are trying to achieve someone
will suggest a solution.

john

 

[John Harrison]

Diego Barros wrote in

Basically there is existing code which has a map of objects. Each
object has an associated name (string) and that is used as the key in
the map. So sorting is done alphabetically on this name.

I now need to sort based on a member variable of the object, in this
case an integer which specifies sort order. So if there are 20 items
in the map they should be sorted by the sort order value of each
object. If there is more than one object with the same sort order
value then I wish to sort on the object's name (string) member
variable (for that sort order value). Do I maybe need to use something
else likea vector and keep it sorted myself?

#include <map>
#include <string>

struct Object { int value; };
typedef std::map< std::string, Object > main_map_t;
typedef std::map< int, main_map_t::iterator > lookup_map_t

main_map_t main_map;
lookup_map_t lookup_map;

//...

void index()
{
main_map_t::iterator ptr, term;

ptr = main_map.begin();
term = main_map.end();

for ( ; ptr != term; ++ptr )
{
lookup_map[ ptr->second.value ] = ptr;
}
}

void lookup( int key )
{
lookup_map_t::iterator ptr = lookup_map.find( key );
if ( ptr == lookup_map.end() ) return; // or throw ...

std::string const &name = ptr->second->first;
Object &object = ptr->second->second;

// do something
}

HTH

Rob.

That doesn't work since the sort order values can be duplicates. I think I'd
prefer something like this

struct Object { int value; };
typedef std::map< std::string, Object > main_map_t;
typedef std::set< main_map_t::iterator, lookup_cmp > lookup_set_t;

where lookup_cmp is a function which orders two main_map_iterators, i.e.

bool lookup_cmp(main_map_t::iterator lhs, main_map_t::iterator rhs)
{
if (lhs->second.value < rhs->second.value)
return true;
if (lhs->second.value > rhs->second.value)
return false;
return lhs->first < rhs->first;
}

Untested code.

john

}

 

[Rob Williscroft]

John Harrison wrote in

That doesn't work since the sort order values can be duplicates. I
think I'd prefer something like this

struct Object { int value; };
typedef std::map< std::string, Object > main_map_t;
typedef std::set< main_map_t::iterator, lookup_cmp > lookup_set_t;

where lookup_cmp is a function which orders two main_map_iterators,
i.e.

bool lookup_cmp(main_map_t::iterator lhs, main_map_t::iterator rhs)
{
if (lhs->second.value < rhs->second.value)
return true;
if (lhs->second.value > rhs->second.value)
return false;
return lhs->first < rhs->first;
}

Untested code.

You don't duplicate Object::value which is possibly better than my
version, though the insert{} and find() cost will be higher.

The killer point though is how do you find anything, since a
main_map_t::iterator is required you need to get this from
main_map before you can search the lookup set.


Rob.

 

[John Harrison]

John Harrison wrote in

Ok, then my version needs std::multimap<>, and your's needs
std::multiset<>.

Because my type includes the key from the original map, there is no
possiblity of duplicates.

You don't duplicate Object::value which is possibly better than my
version, though the insert{} and find() cost will be higher.

The killer point though is how do you find anything, since a
main_map_t::iterator is required you need to get this from
main_map before you can search the lookup set.

True enough, but maybe the OP just wants to iterate through in a particular
order.

john