Collection and Fixed Number of Items

webzoid

I'm interested to see how others have tackled this scenario.

What would be a cute or efficient or fast way of limiting the number of elements in a QList or other collection?

Considering the following crude example:

QList<double> list;

void addItem(double VALUE) {
    if (list.count() == MAX_ITEMS)
        list.pop_back();

    list.insert(0, VALUE);
}

This could achieve what I want, but seems very inefficient.

You may ask why I'm inserting elements at the start of the list rather than appending to the end, well, in my application the entries in a list are all timestamped and I prefer to have the most recent entry at the start. I don't know whether there is a performance impact based on doing things this way.

Is there a more credible alternative in existence within the Qt world?

Thanks

SGaist

Hi,

Do you mean something like QQueue ?

? Offline

This could achieve what I want, but seems very inefficient.

Hi! It is ineffcient. What you're asking for is called a "ring buffer" or "circular buffer". Boost has one, see Boost.Circular Buffer.

Chris Kawa

If you know the maximum size and you can afford to pre-allocate the entire space (to avoid dynamic allocation on insertions) a much better container than a linked list is a ring buffer.
It is basically a fixed size array with two pointers (start and end). Insertions/deletions are basically pointer increment/decrement, so it's cheap. Indexed access is just (start + index) so cheap also.
There's no ring buffer in Qt but there are many implementations out there (e.g. circular_buffer in boost). If you don't want to pull a dependency you can easily implement it on top of any continuous container like QVector or std::vector, but for better results I suggest something with a constant size like std::array.

webzoid

@SGaist isn't QQueue just built on top of a QList with just enqueue and dequeue functions? Fundamentally, nothing is different behind the scenes?

@Wieland correct, a ring buffer would suit but wasn't sure whether Qt had such classes available.

@Chris-Kawa I can certainly afford to pre-allocate a buffer. What I'm storing in these lists won't break the bank in terms of memory but I do need the end result to be fast - these buffers may get updated rather quickly (for instance, during a log file replay). I'll look at wrapping something up into a circular buffer.

SGaist

I was wondering whether you wanted to use a FIFO or as my fellows rightly pointed to a ring buffer.

webzoid

@SGaist you were indeed correct.

I've found this implementation of QCircularBuffer but this seems to have been discontinued since 5.5 (for some reason)

http://doc.qt.io/archives/qt-5.5/qt3d-qcircularbuffer.html

I guess I could just re-implement this in my application