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

If your keys are in a limited range of values, you might want to consider the use of Bucketsort.

Answer 2

I would suggest writing a skip list. It is exactly what you ask for - a sorted list with O(log(n)) insertion. It is also relatively easy to implement.

Answer 3

There are at least two efficient solutions:

1. Append elements to a vector; sort the vector; scan the vector.
2. Insert elements into a priority_queue; drain it.

The vector has the advantage of O(N) load time (vs. O(N log N) for the priority_queue). (Note that it still takes O(N log N) overall, due to the sort).

The priority_queue has the advantage of freeing memory as you drain it. This doesn't reduce the maximum memory footprint, and is probably of negligible benefit, but it's worth trying anyway.

Answer 4

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.