Unsolved Collection and Fixed Number of Items
-
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
-
Hi,
Do you mean something like QQueue ?
-
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.
-
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. -
@SGaist isn't
QQueue
just built on top of aQList
with justenqueue
anddequeue
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.
-
I was wondering whether you wanted to use a FIFO or as my fellows rightly pointed to a ring buffer.
-
@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