Sorting a map<string,long> by the value...

[winbatch]

I frequently use maps to store pairs of data. A large percent of the time I use it to store a mapping between a value and how many times it occurred. What I would like to do in one particular scenario is to provide the output sorted by the value (in this case, the long) rather than the key (in this case, a string). Is there a built-in way to do this or do I need to iterate through the map and check whether my current value is the highest, etc.?

[Rashakil Fol]

You can't change the ordering of a map.

You want to copy the contents of your map to a datatype such as a vector, and then sort the vector by the value. You can do this using iterators.

[winbatch]

I don't want to change the ordering of the map necessarily and would be willing to copy it but was wondering if there was an existing method to get the 'largest' and 'smallest' of a map if the value is a numeric data type.

For example, if my map is map<string,long> and my data is:

key "A" with value 10
key "B" with value 35
key "C" with value 6
key "D" with value 30
key "E" with value 1

to simply return that key "B" has the largest value of 35. (or that E has smallest of 1).

Or do I need to iterate through and manually compare my results?

[Rashakil Fol]

[edit]You need to iterate, but if you make a simple function that does this, using that function is not such a big deal.[/edit]

If you need to grab the minimum and maximum values very frequently, these ideas might be helpful:

The following works well if you only insert elements into the map, and don't remove them.

Make something along the lines of

class minmaxvaluemap {
    map<typea, typeb> m_;
    map<typea, typeb>::iterator min_, max_;
};

with useful member functions.

And then update the min_ and max_ iterators to point to the pair with the minimum and maximum element every time you insert an element into the map.

If you needed to remove an element, that would be inefficient, though, because then you'd need to iterate through the entire map. So if you're adding and removing elements constantly, this would not be a good solution.

If you need to remove elements and still keep track of the minimum and maximum, use two maps in parallel -- one (map A) that maps strings to numbers and one (map B) that maps numbers to strings. (This is obviously not superbly memory-efficient, but it's only off from optimal by a pretty small scalar factor.) If the strings tend to be pretty large, you might want to have B pair numbers with map<number,string> iterators, iterators that point into A. Actually, you would probably want to do this in all cases.

Then, you just need to make sure you keep the maps synchronized.

[winbatch]

My maps often contain 300,000+ elements, so speed and memory consumption is definitely an issue. I don't need to get the minimum/maximum all the time, usually once at the end. For now, I'll probably just iterate through...