Sorting a map by value

Discussion in 'C++' started by Kevin W., Aug 24, 2004.

  1. Kevin W.

    Kevin W. Guest

    Kevin W., Aug 24, 2004
    #1
    1. Advertising

  2. Kevin W.

    Rolf Magnus Guest

    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.
    Rolf Magnus, Aug 24, 2004
    #2
    1. Advertising

  3. Kevin W.

    tom_usenet Guest

    On Tue, 24 Aug 2004 07:55:19 GMT, "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 - 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
    tom_usenet, Aug 24, 2004
    #3
  4. Kevin W.

    Daniel T. Guest

    "Kevin W." <> 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;
    }
    Daniel T., Aug 24, 2004
    #4
  5. tom_usenet ha escrito:

    > On Tue, 24 Aug 2004 07:55:19 GMT, "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 - 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
    =?iso-8859-1?Q?Joaqu=EDn=20M=AA=20L=F3pez=20Mu=F1o, Aug 24, 2004
    #5
  6. 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
    Thomas Matthews, Aug 24, 2004
    #6
  7. Kevin W.

    Kevin W. Guest

    >> 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/
    Kevin W., Aug 25, 2004
    #7
  8. Re: Re: Sorting a map by value

    25.08.2004 08:20:06

    "Kevin W." <> wrote in message

    <>



    > >> 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
    Philippe Guglielmetti, Aug 25, 2004
    #8
  9. Kevin W.

    Kai-Uwe Bux Guest

    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::pair<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
    Kai-Uwe Bux, Aug 25, 2004
    #9
  10. In message <>, Kevin W.
    <> 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
    Richard Herring, Aug 25, 2004
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. PGK
    Replies:
    1
    Views:
    514
  2. Rui Maciel
    Replies:
    2
    Views:
    2,983
    AndrewDover
    Dec 1, 2009
  3. Replies:
    2
    Views:
    1,407
    James Kanze
    Jul 6, 2010
  4. Philipp Kraus

    sorting map value based

    Philipp Kraus, Nov 2, 2010, in forum: C++
    Replies:
    6
    Views:
    739
    Juha Nieminen
    Nov 7, 2010
  5. Jason
    Replies:
    0
    Views:
    372
    Jason
    Oct 4, 2006
Loading...

Share This Page