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]

"Diego Barros" <drylight_@_yah oo.com> wrote in message
news:bh******** ***@otis.netspa ce.net.au...

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]

"Rob Williscroft" <rt*@freenet.RE MOVE.co.uk> wrote in message
news:Xn******** *************** ***********@195 .129.110.200...

Diego Barros wrote in news:bh******** ***@otis.netspa ce.net.au:

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::ite rator > lookup_map_t

main_map_t main_map;
lookup_map_t lookup_map;

//...

void index()
{
main_map_t::ite rator 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::i terator 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::ite rator, lookup_cmp > lookup_set_t;

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

bool lookup_cmp(main _map_t::iterato r lhs, main_map_t::ite rator 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

}

[John Harrison]

"Rob Williscroft" <rt*@freenet.RE MOVE.co.uk> wrote in message
news:Xn******** *************** ***********@195 .129.110.200...

Diego Barros wrote in news:bh******** ***@otis.netspa ce.net.au:

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::ite rator > lookup_map_t

main_map_t main_map;
lookup_map_t lookup_map;

//...

void index()
{
main_map_t::ite rator 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::i terator 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::ite rator, lookup_cmp > lookup_set_t;

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

bool lookup_cmp(main _map_t::iterato r lhs, main_map_t::ite rator 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 news:bh******** ****@ID-196037.news.uni-berlin.de:

That doesn't work since the sort order values can be duplicates. I
think I'd prefer something like this
Ok, then my version needs std::multimap<> , and your's needs
std::multiset<> .

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

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

bool lookup_cmp(main _map_t::iterato r lhs, main_map_t::ite rator 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::ite rator is required you need to get this from
main_map before you can search the lookup set.
Rob.
--
http://www.victim-prime.dsl.pipex.com/

[John Harrison]

"Rob Williscroft" <rt*@freenet.RE MOVE.co.uk> wrote in message
news:Xn******** *************** ***********@195 .129.110.201...

John Harrison wrote in news:bh******** ****@ID-196037.news.uni-berlin.de:

That doesn't work since the sort order values can be duplicates. I
think I'd prefer something like this
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.

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

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

bool lookup_cmp(main _map_t::iterato r lhs, main_map_t::ite rator 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::ite rator 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

[Allan Odgaard]

Diego Barros <drylight_@_yah oo.com> wrote in message news:<bh******* ****@otis.netsp ace.net.au>...

I now need to sort based on a member variable of the 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?

You can use a set with a custom sort function. A set keeps its members
sorted, and uses the function you provide to decide the order.

E.g. for normal C strings we'd use:

struct ltstr
{
bool operator() (const char* s1, const char* s2) const
{
return strcmp(s1, s2) < 0;
}
};

std::set<const char*, ltstr> s;
s.insert(s.end( ), "foo");
s.insert(s.end( ), "bar");

std::copy(s.beg in(), s.end(), std::ostream_it erator<const
char*>(std::cou t, "\n"));

This should print:
bar
foo

[Rob Williscroft]

Kristoffer Vinther wrote in news:bh******** **@news.net.uni-c.dk:

[snip]

#include <map>
#include <string>

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

main_map_t main_map;
lookup_map_t lookup_map;

//...

void index()
{
main_map_t::ite rator 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::i terator 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.
Wouldn't you be required to rebuild the index whenever main_map is
changed? I realize that OP asked only for a sorted set, but I suspect
he also wants efficient searches and updates. If not, why not just
std::copy objects to an std::vector and std::sort them (same
complexity as building the index and probably faster)?

If the OP wants, to make (say) the occasional report then your
solution would be ideal. Except, I'm assuming the OP's objects are
bigger/more complex than the example I gave :), I'd make it a
std::vector of iterators, they could be then sorted with
std::sort using the comparitor John wrote in another sub thread:

bool lookup_cmp(main _map_t::iterato r lhs, main_map_t::ite rator rhs)
{
if (lhs->second.value < rhs->second.value )
return true;
if (lhs->second.value > rhs->second.value )
return false;
return lhs->first < rhs->first;
}

But if recuring searches are required then both the main_map
and the lookup_map above should be put in a user defined class
with sutable insert(), find() (2 version's) and erase() members
defined.
The hybrid data structure needed for efficient searches on both key
and value is not easily constructible from STL containers, I suspect.
Am I wrong?
Well Maybe, but what I describe above is a UDT with 2 data members
and 4 member function's, doesn't seem that OTT.
If iterators remained valid after map insertions, a
solution like the one you propose would be feasible, though.

As John has already pointed out they do, Its a major (i.e. useful)
feature of std ::map, multimap, set and mutliset.
Rob.
--
http://www.victim-prime.dsl.pipex.com/