sorting a map (C++)

Thinking · 09-13-2005, 07:59 AM

hiho@ll

i have a std::map<string,float>
which maps ip's to their load averages for the last minute

now i need those ip's who has the lowest load!

anybody knows if there is a sort algorithm i can use for a map, which sorts using the value's
don't really have the time to write a complex algorithm by myself

for now i only have a simple loop which iterates through the map
but i think it will be a little bit slow

anybody has a better idea?

thx@ll

addy86 · 09-13-2005, 08:34 AM

If you need the entry with the lowest value only once, it is by far faster to iterate over the complete map (complexity: O(n)) than to sort the map and then pick the first element (complexity: O(n*log(n)).
However, if you want to sort nevertheless: Chapter 17.1 gives you the information you need.

Proud · 09-13-2005, 09:06 AM

Why not use a linkedlist with a paired values structure, which you keep sorted.

Thinking · 09-13-2005, 10:13 AM

i'm not sure, Proud, but to use a linked list i need my own sort algorithm, because the values of the linked list are pairs and the algorithm itself needs to know that they are pairs
so it's not a standard simple algorithm
(and i don't have time ;-( )

thx@addy86

Proud · 09-13-2005, 11:35 AM

Well iirc with a double linked list if you insert items in sorted order as you build it up (O(log(n) ?) then finding the lowest load would take O(1), and you wouldnt need to have a sorting algorithm as such, as you simply assume the list is sorted when inserting or deleting. But I'm rusty after my summer after my Algorithms and Data Structures module.

Edit: searching would take O(log(n)), finding the lowest load would take O(1).

Thinking · 09-13-2005, 12:54 PM

hmm

well i understand

but because for now it's easier to search i do this
if it's too slow i will use "find"-way

thx!!

dakensta · 09-13-2005, 04:52 PM

Quote:

for now i only have a simple loop which iterates through the map but i think it will be a little bit slow

Try it first! Unless you have millions of ip addresses, it probably isn't.

Quote:

... but to use a linked list i need my own sort algorithm ...

Use a std::vector and std::sort.
Write your own comparison operator i.e. function or functor that takes two objects and returns bool.