Sorting map<T>?

[Jeff Dege]

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

[John Harrison]

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

[Mark P]

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.

[Clark Cox]

On 2007-03-05 10:07:54 -0800, Jeff Dege <jd***@jdege.visi.comsaid:

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
cl*******@gmail.com