How To: Sort map by Value(second) 
Author Message
 How To: Sort map by Value(second)

I would like to sort the STL map by the Type, instead of
the Key.  Any savy thoughts or references to this
implementation would be well appreciated.

Much Thanks,
Holt



Sun, 05 Jun 2005 01:41:28 GMT  
 How To: Sort map by Value(second)
Quote:
>A map is, by definition, sorted by the key.  Period.

>If you want it sorted differently, while still

maintaining the key-value

Quote:
>pairs, what's typically done is to insert map iterators
into a vector, and
>then sort the vector with a suitable predicate (one that
dereferences the
>iterator & compares the value part of the key-value pair).

>-cd

That might work.  Wouldn't I use a Set instead of a Vector
though?

Holt.



Sun, 05 Jun 2005 02:36:33 GMT  
 How To: Sort map by Value(second)

Quote:
> I would like to sort the STL map by the Type, instead of
> the Key.  Any savy thoughts or references to this
> implementation would be well appreciated.

A map is, by definition, sorted by the key.  Period.

If you want it sorted differently, while still maintaining the key-value
pairs, what's typically done is to insert map iterators into a vector, and
then sort the vector with a suitable predicate (one that dereferences the
iterator & compares the value part of the key-value pair).

-cd



Sun, 05 Jun 2005 02:18:57 GMT  
 How To: Sort map by Value(second)

Quote:
> >A map is, by definition, sorted by the key.  Period.

> >If you want it sorted differently, while still
> maintaining the key-value
> >pairs, what's typically done is to insert map iterators
> into a vector, and
> >then sort the vector with a suitable predicate (one that
> dereferences the
> >iterator & compares the value part of the key-value pair).

> >-cd

> That might work.  Wouldn't I use a Set instead of a Vector
> though?

You could use a multiset if you define the appropriate predicate.
Remember there can be duplicate values in your map, just no duplicate
keys.

Ken



Sun, 05 Jun 2005 02:46:53 GMT  
 How To: Sort map by Value(second)

Quote:
> I would like to sort the STL map by the Type, instead of
> the Key.

Can't be done. Maps and set are only every by key. It is that way for the
lifetime of the object. Any attempt to subvert this will "break" maps and
sets abilities (map.find() could report that an item is not present when it
is simply because you have "broken" the strict weak ordering it relies on).

What you could use is a sorted vector of pairs. You can sort by key or by
type by using predicates whenever you wish to switch. The drawback to this
is that you have to manually maintain the sortedness and uniqueness of the
vector (something tht is builtin to map). You can do that using
lower_bound() for inserts but then the insert code is O(N) whereas for a map
it is O(log N). You could do many push_back()'s and then follow up with
sort() to restore the sortedness (and also erase(unique()) if uniqueness is
important).

In short there is a cost to using a sorted vector but it will work fine if
the vector's contents do not change much over the lifetime.

I use sorted vectors. But only when the contents do not change much.

Stephen Howe



Sun, 05 Jun 2005 03:17:10 GMT  
 How To: Sort map by Value(second)

Quote:


> > >A map is, by definition, sorted by the key.  Period.

> > >If you want it sorted differently, while still
> > maintaining the key-value
> > >pairs, what's typically done is to insert map iterators
> > into a vector, and
> > >then sort the vector with a suitable predicate (one that
> > dereferences the
> > >iterator & compares the value part of the key-value pair).

> > >-cd

> > That might work.  Wouldn't I use a Set instead of a Vector
> > though?

> You could use a multiset if you define the appropriate predicate.
> Remember there can be duplicate values in your map, just no duplicate
> keys.

Also it's probably faster (although you should time it) to put the iterators
into a vector and sort it than it is to put them into a set.  Remember to
call reserve() on the vector before inserting the first item to pre-size it
to the size of the map.  This will avoid any re-allocations during
insertion.

-cd



Sun, 05 Jun 2005 03:19:23 GMT  
 How To: Sort map by Value(second)

Quote:

> I would like to sort the STL map by the Type, instead of
> the Key.  Any savy thoughts or references to this
> implementation would be well appreciated.

> Much Thanks,
> Holt

A couple of months ago I published an STL-like container that
acts as a map both for the key and the value --that is, you can
do fast lookup on type and value and obtain iterators to the
sequence of elements ordered by either type. I call it bimap,
for bidirectional map. You can download it at

http://www.codeproject.com/vcpp/stl/bimap.asp

Regards,

Joaqun M Lpez Mu?oz
Telefnica, Investigacin y Desarrollo



Fri, 10 Jun 2005 15:24:40 GMT  
 
 [ 7 post ] 

 Relevant Pages 

1. Sorting map by value

2. DLL can't map to a reloaded second DLL

3. ListControl sort by second column!

4. Second highest value from array

5. Time values with MICRO seconds precision ??

6. preventing sorting in STL map

7. Sort map content using iterator ?

8. sort map<>

9. Sort a map?

10. Map sorting

11. sorting a map

12. Sorting on double values.

 

 
Powered by phpBB® Forum Software