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.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?


  • Lifetime Qt Champion


    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.

  • Moderators

    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 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.

  • Lifetime Qt Champion

    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)

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

Log in to reply

Looks like your connection to Qt Forum was lost, please wait while we try to reconnect.