0

I'm writing a C++ Qt 6.2 application and need a queue that will contain a large number of items (in the tens of thousands). I need enqueuing and dequeuing to be fast operations, so preferably better than linear time. It would also be quite convenient (though not necessary) to be able to index into the list at an arbitrary index without requiring a linear search, which is why I'm not immediately jumping to a linked list like std::list or QLinkedList.

I'm considering QList, but in Qt 6 it's now explicitly implemented as an array of items. It's not clear to me which operations will run in linear time. Qt's documentation states:

With the exception of append(), prepend() and replace(), these functions can be slow (linear time) for large lists, because they require moving many items in the list by one position in memory. If you want a container class that provides fast insertion/removal in the middle, use std::list instead.

The confusing bit here is that it says "fast insertion/removal in the middle" implying that removal from the beginning or end may not be linear, but it's not explicit about it.

There's also QQueue which is specifically designed from removing from the front and appending to the back. But again the documentation does not make it clear if front-removal is optimized and not a linear-time operation for large lists.

Can anyone shed some light on this? Or should I just fall back on using a linked list?

Bri Bri
  • 2,169
  • 3
  • 19
  • 44
  • [std::deque](https://en.cppreference.com/w/cpp/container/deque)? – Alan Birtles Aug 09 '23 at 17:35
  • What do you need, (log n) insertion/deletion, constant time lookup priority item? Then maybe [std::priority_queue](https://en.cppreference.com/w/cpp/container/priority_queue). Otherwise read this : [iterate over priority queue](https://stackoverflow.com/questions/4484767/how-to-iterate-over-a-priority-queue) – Pepijn Kramer Aug 09 '23 at 17:35
  • Look at the Qt source code! I _think_ when removing at end, the array is never resized, so that's always very fast. Appending may require resize, but if it is not a hard real time system, it should not matter, especially if you reserve correct initial capacity. Dynamic array will always use less memory than a linked list. – hyde Aug 09 '23 at 17:41
  • std::list's insertion somewhere in the list is fast O(1), but finding the location where you need to insert is slow O(n). And you can't optimize because std::list has no random acces iterator (so you can't do things like binary search) – Pepijn Kramer Aug 09 '23 at 17:42
  • @hyde I did look at the Qt source, but it's not at all easy to comprehend. I was hoping that there is documentation somewhere that makes this clear, or someone can just share their existing knowledge. – Bri Bri Aug 09 '23 at 17:48

1 Answers1

1

After doing some quick experimentations, I've found that prepending, appending, and removing the first or last item of a QList is extremely fast including with a list that contains a large number of items, so it does look like QList is indeed suitable for my needs.

I'm going to keep this question open though in case someone can post a more authoritative answer that's not based on a quick test and observation.

Bri Bri
  • 2,169
  • 3
  • 19
  • 44
  • 1
    Qt has a blog post about it [here](https://www.qt.io/blog/qlist-changes-in-qt-6). – JarMan Aug 09 '23 at 18:45
  • @JarMan Thanks! That at least makes it clear that prepend is fast, and given removing the last element is fast too, that gives me what I need for an efficient queue that allows indexing. It's confusing though because these seemingly contradicts what they say here: https://doc.qt.io/qt-6/containers.html#linear-time And there's no mention of removal times, which is important to my use case. – Bri Bri Aug 09 '23 at 20:26