What Qt container class to use for a sorted list?

Question

Part of my application involves rendering audio waveforms. The user will be able to zoom in/out of the waveform. Starting at fully zoomed-out, I only want to sample the audio at the necessary internals to draw the waveform at the given resolution. Then, when they zoom in, asynchronously resample the "missing points" and provide a clearer waveform. (Think Google Maps.) I'm not sure the best data structure to use in Qt world. Ideally, I would like to store data samples sorted by time, but with the ability to fill-in points as needed.

So, for example, the data points might initially look like:

data[0 ms] = 10
data[10 ms] = 32
data[20 ms] = 21
...

But when they zoom in, I would get more points as necessary, perhaps:

data[0 ms] = 10
data[2 ms] = 11
data[4 ms] = 18
data[6 ms] = 30
data[10 ms] = 32
data[20 ms] = 21
...

Note that the values in brackets are lookup values (milliseconds), not array indices.

I should be able to efficiently query for a range ("all points between 10 and 30 milliseconds") and somewhat-efficiently insert new points.

In .Net I might have used a SortedList<int, int>. What would be the best class to use in Qt? Or should I use a STL container?

Answer 1

What would be the best class to use in Qt? Or should I use a STL container?

You can use the std::map. I recommend to use STL containers for the business logic, and Qt containers only when it's needed for binding data to your GUI.

EDIT: changed std::set to std::map

Answer 2

Hey,

I would strongly advice you to have a look here : Generic Containers

You'll find a good summary of different container classes in Qt... I would also recommend you to use one of those ! Looks to me you could use a QMap !

Hope it helps a bit !

Answer 3

QMap is automatically sorted, so iterating over it will produce a sorted (ascending) list.

It also provides Qmap::upperBound() and QMap::lowerBound() which you can use for your range finding functionality.

http://doc.trolltech.com/4.6/qmap.html