By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,778 Members | 1,890 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,778 IT Pros & Developers. It's quick & easy.

Sort a map using the value, not the key.

P: n/a
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
Jul 19 '05 #1
Share this Question
Share on Google+
7 Replies


P: n/a

"Diego Barros" <drylight_@_yahoo.com> wrote in message
news:bh***********@otis.netspace.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
Jul 19 '05 #2

P: n/a

"Rob Williscroft" <rt*@freenet.REMOVE.co.uk> wrote in message
news:Xn**********************************@195.129. 110.200...
Diego Barros wrote in news:bh***********@otis.netspace.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::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

}
Jul 19 '05 #3

P: n/a

"Rob Williscroft" <rt*@freenet.REMOVE.co.uk> wrote in message
news:Xn**********************************@195.129. 110.200...
Diego Barros wrote in news:bh***********@otis.netspace.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::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

}
Jul 19 '05 #4

P: n/a
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::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.
--
http://www.victim-prime.dsl.pipex.com/
Jul 19 '05 #5

P: n/a

"Rob Williscroft" <rt*@freenet.REMOVE.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::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.


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

john
Jul 19 '05 #6

P: n/a
Diego Barros <drylight_@_yahoo.com> wrote in message news:<bh***********@otis.netspace.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.begin(), s.end(), std::ostream_iterator<const
char*>(std::cout, "\n"));

This should print:
bar
foo
Jul 19 '05 #7

P: n/a
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::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.
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::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;
}


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/
Jul 19 '05 #8

This discussion thread is closed

Replies have been disabled for this discussion.