Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Sorting a map by value

Reply
Thread Tools

Sorting a map by value

 
 
Kevin W.
Guest
Posts: n/a
 
      08-24-2004
How do I sort a map by the value, rather than the key? (either
automatically or with the sort function.)

--
Kevin W
Opera/CSS/webdev blog: http://www.exclipy.com/
Using Opera: http://www.opera.com/m2/
 
Reply With Quote
 
 
 
 
Rolf Magnus
Guest
Posts: n/a
 
      08-24-2004
Kevin W. wrote:

> How do I sort a map by the value, rather than the key? (either
> automatically or with the sort function.)


You can't sort maps. They are always automatically sorted by key.

 
Reply With Quote
 
 
 
 
tom_usenet
Guest
Posts: n/a
 
      08-24-2004
On Tue, 24 Aug 2004 07:55:19 GMT, "Kevin W." <(E-Mail Removed)> wrote:

>How do I sort a map by the value, rather than the key? (either
>automatically or with the sort function.)


You can't - std::map has an invariant that it is sorted by key. You'll
have to copy into a vector or similar first, or perhaps maintain two
parallel maps (key->value and value->key).

Tom
 
Reply With Quote
 
Daniel T.
Guest
Posts: n/a
 
      08-24-2004
"Kevin W." <(E-Mail Removed)> wrote:

> How do I sort a map by the value, rather than the key? (either
> automatically or with the sort function.)


First start with a test:

int main() {
map< char, int > current;
current['a'] = 5;
current['b'] = 4;
current['c'] = 3;

map< int, char > other = converse_map( current );

map< int, char >::iterator begin( other.begin() );
assert( begin->first == 3 );
assert( begin->second == 'c' );
++begin;
assert( begin->first == 4 );
assert( begin->second == 'b' );
++begin;
assert( begin->first == 5 );
assert( begin->second == 'a' );
cout << "OK";
}

When the above prints "OK" you know you are done. Now write the
'converse_map' function...

map< int, char > converse_map( const map< char, int >& o )
{
map< int, char > result;
for ( map< char, int >::const_iterator begin( o.begin() );
begin != o.end(); ++begin )
result.insert( make_pair( begin->second, begin->first ) );
return result;
}

Then turn it into a template...

template < typename T, typename U >
map< U, T > converse_map( const map< T, U >& o )
{
map< U, T > result;
for ( typename map< T, U >::const_iterator begin( o.begin() );
begin != o.end(); ++begin )
result.insert( make_pair( begin->second, begin->first ) );
return result;
}
 
Reply With Quote
 
=?iso-8859-1?Q?Joaqu=EDn=20M=AA=20L=F3pez=20Mu=F1oz?=
Guest
Posts: n/a
 
      08-24-2004
tom_usenet ha escrito:

> On Tue, 24 Aug 2004 07:55:19 GMT, "Kevin W." <(E-Mail Removed)> wrote:
>
> >How do I sort a map by the value, rather than the key? (either
> >automatically or with the sort function.)

>
> You can't - std::map has an invariant that it is sorted by key. You'll
> have to copy into a vector or similar first, or perhaps maintain two
> parallel maps (key->value and value->key).
>


Boost.MultiIndex (to appear promptly in Boost 1.32, online docs
already available at boost-consulting.com/boost/libs/multi_index) can
be used to construct such a bidirectional map easily. This is shown in one

of the examples at

boost-consulting.com/boost/libs/multi_index/doc/examples.html#example4

Regards,

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo

 
Reply With Quote
 
Thomas Matthews
Guest
Posts: n/a
 
      08-24-2004
Kevin W. wrote:

> How do I sort a map by the value, rather than the key? (either
> automatically or with the sort function.)
>


The map data structure is an association between a key
and a value. The std::map requires that each key be
unique. However, two keys can have the same value.
How will you handle the collating of pairs with
the same value but different keys?

If you _really_ want to sort the map, what you are
saying is that you want the data in the map to
be sorted by value. Easy, copy the data into
a new std::multi_map but swap the key with the
value before placing into the multimap. Or
you could use a list, or vector and a sort
function.

Search the newsgroup for "view pattern". For
a hint on how to make a "view" of the data
without altering where the data is stored.

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.comeaucomputing.com/learn/faq/
Other sites:
http://www.josuttis.com -- C++ STL Library book

 
Reply With Quote
 
Kevin W.
Guest
Posts: n/a
 
      08-25-2004
>> How do I sort a map by the value, rather than the key?
>
> You can't sort maps. They are always automatically sorted by key.


Yes, but I should be able to define the "less than" predicate in the
constructor, or I should be able to pass a custom predicate into the sort
function (as I understand it, you *can* sort a map because it is only
automatically sorted when pairs are added or removed).

What I'm really asking is:
What are the arguments to this functor (values, pointers or references),
and
How do I access the value from these arguments?

--
Kevin W
Opera/CSS/webdev blog: http://www.exclipy.com/
Using Opera: http://www.opera.com/m2/
 
Reply With Quote
 
Philippe Guglielmetti
Guest
Posts: n/a
 
      08-25-2004
25.08.2004 08:20:06

"Kevin W." <(E-Mail Removed)> wrote in message

<(E-Mail Removed)>



> >> How do I sort a map by the value, rather than the key?




You need a different structure.

Have a look at the "bidirectional map" described on http://www.
codeproject.com/vcpp/stl/bimap.asp

Philippe Guglielmetti - www.goulu.net
 
Reply With Quote
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      08-25-2004
Kevin W. wrote:

>>> How do I sort a map by the value, rather than the key?

>>
>> You can't sort maps. They are always automatically sorted by key.

>
> Yes, but I should be able to define the "less than" predicate in the
> constructor


Yes, this less_than predicate will be used to compare the keys.

> or I should be able to pass a custom predicate into the sort
> function (as I understand it, you *can* sort a map because it is only
> automatically sorted when pairs are added or removed).


The std::map<Key,T> container is a sequence of pairs. The type of these
pairs is std:air<const Key, T >. Please note the *const*. Because of this
'const', you cannot change the keys once they are inserted into the
sequence. It follows that you cannot feed a segment of a map into
std::sort(). The swaps that std::sort() wants to perform are barred by
constness of keys.


Best

Kai-Uwe Bux
 
Reply With Quote
 
Richard Herring
Guest
Posts: n/a
 
      08-25-2004
In message <(E-Mail Removed)>, Kevin W.
<(E-Mail Removed)> writes
>>> How do I sort a map by the value, rather than the key?

>>
>> You can't sort maps. They are always automatically sorted by key.

>
>Yes, but I should be able to define the "less than" predicate in the
>constructor,


Yes, and it defines the ordering for the lifetime of the map. Once
established, you can't change it.

>or I should be able to pass a custom predicate into the sort function


No, because there _is_ no standard sort function which can be applied to
maps. std::sort() needs random-access non-const iterators.

>(as I understand it, you *can* sort a map because it is only
>automatically sorted when pairs are added or removed).


No. As Kai-Uwe Bux has pointed out, the key element of each pair is
const. But even if you could rearrange their order, it wouldn't do you
any good, because the key lookup algorithm depends on the elements being
correctly ordered. The next time you tried to access an element by key,
you'd get UB.
>
>What I'm really asking is:
>What are the arguments to this functor (values, pointers or
>references),


The same as to std::less, namely (const reference to) key_type, and it
returns bool. And it must implement a strict weak ordering:

a<b && b<c => a<c;
eq(a,b) && eq(b,c) => eq(a, c) where eq(a, b) means !(a<b) && !(b<a)

>and
>How do I access the value from these arguments?
>

The arguments _are_ the values (or references to them.)

--
Richard Herring
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
sorting map value based Philipp Kraus C++ 6 11-07-2010 04:55 PM
Sorting list vs sorting vector boltar2003@boltar.world C++ 2 07-06-2010 09:40 AM
stl map: get the <key,value> pair which has the minimum value Rui Maciel C++ 2 12-01-2009 11:21 PM
initial value of pointer value in std map ? PGK C++ 1 04-02-2009 10:46 AM
fired event Sorting which wasn't handled - sorting and SelectedIndexChanged Jason ASP .Net Web Controls 0 10-04-2006 02:19 PM



Advertisments