Best data structure for ordered list (performance)

Question

I have a critical section on my application that consists of taking a data source (unordered) and then execute an algorithm on each element in order. Actually I follow the next algorithm:

• Read the source and put it to a std::map, using the sorting element as key and the info as content.
• Read the map using an iterator and execute the algorithm.

I see that map may not be the best data structure, as I only need to add the data to a sorted list and then "burn" the list altogether (also, memory allocation is costly on mobile devices, so I'd prefer to do it myself).

I've done some research and I'm reading things like B-trees and Black-Red trees. They may be what I am searching for, but I'll ask here if anybody knows of a data structure that is convenient for that task.

In short, I want a structure with:

• fast insertion.
• fast iteration (from begin to end).
• everything else is not important (neither deletion nor search).

Also fast insertion is more important than fast iteration (my profiler said so :D).

Thank you everyone.

Answer 1

The theoretical better way to do this is to use heapsort.

However, in practice, the fastest way is to append your elements to a vector, and sort them using a quicksort.

In both case, it will take O( N * log(N) ) in average, but the quicksort has lowest constant factors.