Sorting map<T>?

Discussion in 'C++' started by Jeff Dege, Mar 5, 2007.

  1. Jeff Dege

    Jeff Dege Guest

    Suppose I have a problem for which an associative array is the most
    natural fit, but which I need to be able to output in sorted order of the
    values.

    STL map would seem like a good fit, except that maps are sorted on key,
    not value.

    I can picture a couple of approaches, but I'm not clear on what would be
    cleanest.

    Any ideas?

    --
    There are three kinds of men. The one that learns by reading. The few
    who learn by observation. The rest of them have to pee on the electric
    fence for themselves.
    - Will Rogers
    Jeff Dege, Mar 5, 2007
    #1
    1. Advertising

  2. Jeff Dege wrote:
    > Suppose I have a problem for which an associative array is the most
    > natural fit, but which I need to be able to output in sorted order of the
    > values.
    >
    > STL map would seem like a good fit, except that maps are sorted on key,
    > not value.
    >
    > I can picture a couple of approaches, but I'm not clear on what would be
    > cleanest.
    >
    > Any ideas?
    >


    Well I suppose the fancy approach would be to have two sets, each
    pointing to common data but with different sorting criteria. That way
    you'd have key sorted data for lookup and value sorted data for output.
    Wrap it all up in a class so things can't get out of step and away you go.

    But most of the time I think I'd just copy to a vector, sort the vector
    and then throw the vector away.

    john
    John Harrison, Mar 5, 2007
    #2
    1. Advertising

  3. Jeff Dege

    Mark P Guest

    John Harrison wrote:
    > Jeff Dege wrote:
    >> Suppose I have a problem for which an associative array is the most
    >> natural fit, but which I need to be able to output in sorted order of the
    >> values.
    >>
    >> STL map would seem like a good fit, except that maps are sorted on key,
    >> not value.
    >>
    >> I can picture a couple of approaches, but I'm not clear on what would be
    >> cleanest.
    >>
    >> Any ideas?
    >>

    >
    > But most of the time I think I'd just copy to a vector, sort the vector
    > and then throw the vector away.
    >


    That would be my suggestion too. The only addition I'd make is that, if
    the values are large enough that copying and sorting may be inefficient,
    you can make a vector of pointers to the map values and sort that instead.
    Mark P, Mar 5, 2007
    #3
  4. Jeff Dege

    Clark Cox Guest

    On 2007-03-05 10:07:54 -0800, Jeff Dege <> said:

    > Suppose I have a problem for which an associative array is the most
    > natural fit, but which I need to be able to output in sorted order of the
    > values.
    >
    > STL map would seem like a good fit, except that maps are sorted on key,
    > not value.
    >
    > I can picture a couple of approaches, but I'm not clear on what would be
    > cleanest.
    >
    > Any ideas?


    I would probably do one of the following:

    1) Copy the data into a vector and sort it, and output *that*, then
    discard the vector when you're done.
    2) Copy the data into a set, and output that ... (may be faster or
    slower than copying to a vector depending on your data)
    3) Maintain a set of map::iterator's that is sorted by data type, but
    points into your map.
    4) Maintian a second map, that contains the same data, but with the key
    and value swapped.

    I can imagine myself using any of the above methods depending on
    performance and data constraints.


    --
    Clark S. Cox III
    Clark Cox, Mar 5, 2007
    #4
    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. cylin
    Replies:
    6
    Views:
    12,769
    velthuijsen
    Apr 16, 2004
  2. Replies:
    2
    Views:
    1,425
    James Kanze
    Jul 6, 2010
  3. Jason
    Replies:
    0
    Views:
    384
    Jason
    Oct 4, 2006
  4. Tom Kirchner

    sorting by multiple criterias (sub-sorting)

    Tom Kirchner, Oct 11, 2003, in forum: Perl Misc
    Replies:
    3
    Views:
    474
    Michael Budash
    Oct 11, 2003
  5. Íéêüëáïò Êïýñáò

    Sorting a set works, sorting a dictionary fails ?

    Íéêüëáïò Êïýñáò, Jun 10, 2013, in forum: Python
    Replies:
    12
    Views:
    156
    Ulrich Eckhardt
    Jun 10, 2013
Loading...

Share This Page