Sorting map by value 
Author Message
 Sorting map by value

Hi,

does anyone knows how to sort a map by value, not key



Fri, 15 Mar 2002 03:00:00 GMT  
 Sorting map by value
I would assume using std::sort and passing a predicate to that which
takes a pair<key,value>x,pair <map key,value>y. and returns true or
false based on the value instead of key.
I am not sure of this though.

On Mon, 27 Sep 1999 15:42:18 -0700, "Jordan Peters"

Quote:

>Hi,

>does anyone knows how to sort a map by value, not key

--
Girish Bharadwaj [mvp].
Please do not email queries to me.
Post them in newsgroups.
Thank you.


Sat, 16 Mar 2002 03:00:00 GMT  
 Sorting map by value
    That won't work.  std::sort requires random access iterators, and map
only provides bi-directional iterators.


Quote:
> I would assume using std::sort and passing a predicate to that which
> takes a pair<key,value>x,pair <map key,value>y. and returns true or
> false based on the value instead of key.
> I am not sure of this though.



Sat, 16 Mar 2002 03:00:00 GMT  
 Sorting map by value
    The first question you must ask is, "Why do you care what order your map
is in?"   Clearly, you want to iterator over it, in sorted order.
Inwhichcase, you don't want a map, but a vector.   Copy the items in the map
into a vector, and use std::sort with an appropriate predicte.


Quote:
> does anyone knows how to sort a map by value, not key



Sat, 16 Mar 2002 03:00:00 GMT  
 Sorting map by value
In fact (or perhaps more to the point), maps (when iterated over) are in key
sort order.

You cannot ever "reorder" it (short of making a new map based on a new key).

Which brings me to my point:  Consider having both your map (by key) and a
set.

That may be what you're trying to get to....or maybe not.

--
Reginald Blue                   | Opinions expressed here do not
Natural Language Understanding  | necessarily represent those of
Unisys Corporation              | my employer.
--------------------------------+-------------------------------

NL technology,speech application| My email address is wrong, you
development training, see:      | need to remove the obvious.
                                +-------------------------------
http://www.speechdepot.com/


Quote:
>     The first question you must ask is, "Why do you care what order your
map
> is in?"   Clearly, you want to iterator over it, in sorted order.
> Inwhichcase, you don't want a map, but a vector.   Copy the items in the
map
> into a vector, and use std::sort with an appropriate predicte.



> > does anyone knows how to sort a map by value, not key



Sat, 16 Mar 2002 03:00:00 GMT  
 Sorting map by value

Quote:

> does anyone knows how to sort a map by value, not key

You can't sort a std::map, because is it stored in a tree that makes lookup
by key fast, so it is already "sorted" in a way you can't undo.

A solution would be to create list of the same type as the map, iterate
through the map, and then insert into the list, sorting by value instead
of key.

Something like:

typedef pair<int, std::string> MapType;

std::map<MapType> MyMap;
std::list<MapType> MyList;

for (map<MapType>::iterator i = MyMap.begin(); i != MyMap.end(); i++)
  DoSortedInsert(MyList, i);

--
Jeff Rife                   | Coach: What'll you have, Normie?
19445 Saint Johnsbury Lane  |  
Germantown, MD  20876-1610  |  Norm: Uh, 1929 Lafite Rothschild, Coach...or, a
Home: 301-916-8131          |        beer...whatever everyone else is having.
Work: 301-770-5800 Ext 5335 |  



Sat, 16 Mar 2002 03:00:00 GMT  
 Sorting map by value

Quote:

> I would assume using std::sort and passing a predicate to that which
> takes a pair<key,value>x,pair <map key,value>y. and returns true or
> false based on the value instead of key.

You would assume wrong.

std::map is stored in a tree that results in fast lookup by key.  You can't
sort it, because it is already sorted...more or less.

Quote:
> I am not sure of this though.

It seems the quality of MVP's is going down a bit.

--
Jeff Rife                   | "This?  This is ice.  This is what happens to
19445 Saint Johnsbury Lane  |  water when it gets too cold.  This?  This is
Germantown, MD  20876-1610  |  Kent.  This is what happens to people when
Home: 301-916-8131          |  they get too {*filter*}ly frustrated."
Work: 301-770-5800 Ext 5335 |              -- Chris Knight, "Real Genius"



Sat, 16 Mar 2002 03:00:00 GMT  
 Sorting map by value
Thanks for correcting me. I was not sure of that anyway..

On Tue, 28 Sep 1999 10:16:18 -0400, "James Curran"

Quote:

>    That won't work.  std::sort requires random access iterators, and map
>only provides bi-directional iterators.



>> I would assume using std::sort and passing a predicate to that which
>> takes a pair<key,value>x,pair <map key,value>y. and returns true or
>> false based on the value instead of key.
>> I am not sure of this though.

--
Girish Bharadwaj [mvp].
Please do not email queries to me.
Post them in newsgroups.
Thank you.


Sat, 16 Mar 2002 03:00:00 GMT  
 Sorting map by value
Yes, it's true, You cannot ever "reorder" map keys, obviously my question
was wrong. What I need is actually a multimap, and I would like to have
the equal keys sorted by value, something like that:

1, 'x'
1, 'y'
1, 'z'
2, 'a'
2, 'b'
2, 'c'


Quote:
> In fact (or perhaps more to the point), maps (when iterated over) are in
key
> sort order.

> You cannot ever "reorder" it (short of making a new map based on a new
key).

> Which brings me to my point:  Consider having both your map (by key) and a
> set.

> That may be what you're trying to get to....or maybe not.

> --
> Reginald Blue                   | Opinions expressed here do not
> Natural Language Understanding  | necessarily represent those of
> Unisys Corporation              | my employer.
> --------------------------------+-------------------------------

> NL technology,speech application| My email address is wrong, you
> development training, see:      | need to remove the obvious.
>                                 +-------------------------------
> http://www.speechdepot.com/



> >     The first question you must ask is, "Why do you care what order your
> map
> > is in?"   Clearly, you want to iterator over it, in sorted order.
> > Inwhichcase, you don't want a map, but a vector.   Copy the items in the
> map
> > into a vector, and use std::sort with an appropriate predicte.



> > > does anyone knows how to sort a map by value, not key



Sat, 16 Mar 2002 03:00:00 GMT  
 Sorting map by value

Quote:

> Hi,

> does anyone knows how to sort a map by value, not key

Sure. If you have
std::map<Key,Value> Map1;

create a
std::map<Value,Key> Map2;

and insert all the elements of map1 into map2 but switching the keys and
values.

Nick



Sat, 16 Mar 2002 03:00:00 GMT  
 Sorting map by value

Quote:

>     The first question you must ask is, "Why do you care what order your map
> is in?"   Clearly, you want to iterator over it, in sorted order.
> Inwhichcase, you don't want a map, but a vector.   Copy the items in the map
> into a vector, and use std::sort with an appropriate predicte.

Huh ? I don't think you can assume that at all.
There are many reasons to use a map rather than a vector, telling someone they
don't want t amap without seeing any code or real problem statement whatever is
unlikely to be useful.

Nick



Sat, 16 Mar 2002 03:00:00 GMT  
 Sorting map by value

Quote:

> Yes, it's true, You cannot ever "reorder" map keys, obviously my question
> was wrong. What I need is actually a multimap, and I would like to have
> the equal keys sorted by value, something like that:

> 1, 'x'
> 1, 'y'
> 1, 'z'
> 2, 'a'
> 2, 'b'
> 2, 'c'



I'm not really familiar with the exact multimap semantics, but if that doesn't
give you what you need, you could have a map of lists and keep the lists sorted.
I know this is something like a multimap already but i am not sure multimap lets
you order your values easily like this.

i.e.in your map, '1' would map to a list with 'x','y','z' in it. Depending on
the length of your lists it might be ok.

Nick



Sat, 16 Mar 2002 03:00:00 GMT  
 Sorting map by value
Hi-

You could create a class which holds both values and sorts correctly based on
both values.  This type could then be stored in a set<>.  If both classes
support operator< the pair<> class may already give you what need to combine
them.  See p.35-36 "Pair Comparisons" in "The Standard C++ Library" by Josuttis.

-Neil



Sat, 16 Mar 2002 03:00:00 GMT  
 Sorting map by value
    What the they on doing with the map the rest of the time is irrelevant.
For this particular task, a vector is best, which is why I had them copy
their existing map into a vector.  I never said they said abandon the map
entirely.


Quote:
> Huh ? I don't think you can assume that at all.
> There are many reasons to use a map rather than a vector, telling someone
they
> don't want t amap without seeing any code or real problem statement
whatever is
> unlikely to be useful.



Sat, 16 Mar 2002 03:00:00 GMT  
 Sorting map by value

Quote:

>     What the they on doing with the map the rest of the time is irrelevant.
> For this particular task, a vector is best, which is why I had them copy
> their existing map into a vector.  I never said they said abandon the map
> entirely.

No it isn't. What if I want to do lookups and insertions pretty often.
I can
1) Maintain both maps which are implicitly always sorted and lookup is in log
time
or i can (your method)
2) Whenever I do a lookup, create a vector from the map and sort it and search
it (at best n log n time)
or ... keep the vector and add the new item to it and resort (if you use in
insertion, rather than sort, it's order n time)

My point was that unless you knew (rather than assumign ) the original posters
requirements, you don't know.
I took the poster at face value and gave him a map solution. Maybe a vector is
more appropriate, but (unless i am missing some of the original post) it was
impossible to tell

Nick



Sat, 16 Mar 2002 03:00:00 GMT  
 
 [ 18 post ]  Go to page: [1] [2]

 Relevant Pages 

1. How To: Sort map by Value(second)

2. preventing sorting in STL map

3. Sort map content using iterator ?

4. sort map<>

5. Sort a map?

6. Map sorting

7. sorting a map

8. Sorting on double values.

9. SortedList sorted by value.

10. Sorting multiple values at once.

11. Sorting Array Error - left operand must be L-value

12. (Q) Mapping numerical values to #defined

 

 
Powered by phpBB® Forum Software