Map Container & Sorting :: STL

[kuphryn]

Hi.

Is it possible to sort a map *by value* instead of by key? Moreover, is it possible to declare a map that with a custome sorting algorithm that sorts accord to value? If yes, please give a sample of the sorting function. I can create the function object, but I need to know the parameter.

Thanks,
Kuphryn

[Yves M]

I don't get it, why would you want to sort a map ? Given a Key it gives you back the data associated with the Key. There is no need for any ordering on the Keys, except for them to be unique. So in general, you wouldn't even be able to sort a map by Key.
[edit : ok, it's true that std::map is a sorted container ;) But then again I might be thinking to mathematically about maps ;) Most of the time I use hash_map, which is not sorted anyways...]

Might it not be better to use a different data structure ? Or why exactly do you want to sort this map ?

The point is that using STL, there is no way you can sort your std::map by value instead of by key.

Another edit : There is really no hope for you here, since a map is actually implemented in terms of a red-black tree ;) Not that it would matter really, but it emphasizes the fact that you can't sort a map by value.

If you are really desperate, you could do something like this :

map<long, double> orgMap;
map<long, double>::iterator orgIt;
map<double, long> dstMap;

... // fill in the map

// Now copy it to the new map, which is sorted by value
// (of course, you'll have to make sure that the values are unique, otherwise use multimap)
orgIt = orgMap.begin();
while (orgIt != orgMap.end()) {
dstMap[(*orgIt).second] = (*orgIt).first;
orgIt++;
}

[jfaust]

Kuphryn,

I'm guessing that you are using a map to store something with two pieces of data, that doesn't necessarily have a good key to value mapping. What you really want usually in such a case is to create a struct with the two values and create a container of those structs.

Check out boost::tuple at http://www.boost.org/libs/tuple/doc/tuple_users_guide.html which allows you to hook two or more values together. Think of it as an unnamed struct. You could create a container of these, then when you need to sort, you can provide a sort routine that sorts how you want it to.

Jeff

[Yves M]

Ha, boost definitely seems like a handy tool ;)

[kuphryn]

Okay. Thanks.

The algorithm I am working on a probably simple for most programmers. Nonetheless, I want to come up with my own solution instead of posting it and home someone else solve it.

Hey, I always appreciate help from members.

jfaust brought up an interesting and possible idea. I could work, but do not believe it will help improve the algorithm.

Kuphryn