Why doesn't QList have a resize() method?

Question

I just noticed that QList doesn't have a resize method, while QVector, for example, has one. Why is this? And is there an equivalent function?

Ragg

See bugreports.qt.io/browse/QTBUG-42732 (esp. the last comment) and codereview.qt-project.org/#/c/100738/1//ALL for some highlights, folks. – Laundryman

Answer 1

I think reason is because QList doesn't require the element type to have a default constructor. As a result of this, there is no operation where QList ever creates an object it only copies them.

But if you really need to resize a QList (for whatever reason), here's a function that will do it. Note that it's just a convenience function, and it's not written with performance in mind.

template<class T>
void resizeList(QList<T> & list, int newSize) {
    int diff = newSize - list.size();
    T t;
    if (diff > 0) {
        list.reserve(newSize);
        while (diff--) list.append(t);
    } else if (diff < 0) list.erase(list.end() + diff, list.end());
}

Knorr

Note that "doesn't require the element type to have a default constructor" is an implementation detail. QList is documented to require a default-constructible type. The "detail" is unlikely to change at this point, still... – Lingam

It should be list.reserve(newSize); – Jetpropelled

Answer 2

Well, this is the more generic answer, but I hope you will see, by comparising QList and QVector why there is no need of manually expanding the container.

QList is using internal buffer to save pointers to the elements (or, if the element is smaller than pointer size, or element is one of the shared classes - elements itself), and the real data will be kept on the heap.

During the time, removing the data will not reduce internal buffer (empty space will be filled by shifting left or right elements, leaving space on the beginning and the end for later insertions).

Appending items, like QVector will create additional new space on end of the array, and since, unlike QVector, real data is not stored in internal buffer, you can create a lot of space in single instruction, no matter what size of the item is (unlike QVector) - because you are simply adding pointers into indexing buffer.

For example, if you are using 32bit system (4 bytes per pointer) and you are storing 50 items in the QList, and each item is 1MB big, QVector buffer will need to be resized to 50MB, and QList's internal buffer is need to allocate only 200B of memory. This is where you need to call resize() in QVector, but in QList there is no need, since allocating small chunk of memory is not problematic, as allocating 50MB of memory.

However, there is a price for that which means that you sometimes you want to preffer QVector instead of QList: For single item stored in the QList, you need one additional alloc on the heap - to keep the real data of the item (data where pointer in the internal buffer is pointing to). If you want to add 10000 items larger than the pointer (because, if it can fit into pointer, it will be stored directly in the internal buffer), you will need 10000 system calls to allocate data for 10000 items on the heap. But, if you are using QVector, and you call resize, you are able to fit all the items in the single alloc call - so don't use QList if you need a lot of inserting or appending, prefer QVector for that. Of course, if you are using QList to store shared classes, there is no need for additional allocating, which again makes QList more suitable.

So, prefer QList for most of the cases as it is:

1. Using indices to access the individual elements, accessing items will be faster that QLinkedList
2. Inserting into middle of the list will only require moving of the pointers to create space, and it is faster than shifting actual QVector data around.
3. There is no need to manually reserve or resize space, as empty space will be moved to the end of the buffer for later use, and allocating space in the array is very fast, as the elements are very small, and it can allocate a lot of space without killing your memory space.

Don't use it in the following scenarios, and prefer QVector:

1. If you need to ensure that your data is stored in the sequential memory locations
2. If you are rarely inserting data at the random positions, but you are appending a lot of data at the end or beginning, which can cause a lot of unnecessary system calls, and you still need fast indexing.
3. If you are looking for (shared) replacement for simple arrays which will not grow over the time.

And, finally, note: QList (and QVector) have reserve(int alloc) function which will cause QList's internal buffer to grow if alloc is greater than the current size of the internal buffer. However, this will not affect external size of the QList (size() will always return the exact number of elements contained in the list).

Jamila

While your explanations are very reasonable, it might still be nice to call resize, not as an optimization, but as a means of shrinking or growing the list (and filling in default values if neccessary), because your algorithm/design requires a list of exactly n elements. – Copyreader

And by the way, "but you are appending a lot of data at the end or beginning" - Appending a lot of data at the beginning is still not the best idea, since this also requires shifting the other elements (Ok, if you mean prepending large blocks of multiple elements at once, it might amortize itself again). Otherwise sound reasoning. +1 – Copyreader

@ChristianRau thank you for your comments, I will edit my answer to add the facts you pointed here. As there is no resize in QList, I think reserve is a way to go in this case, right? – Jamila

No, it is not. reserve in turn is a mere optimization, which doesn't really change the outside world's view of the list (the number of elements), whereas resize is used if you really want the list to change its external size. If there is no resize for QList (for the conceptual reasons you described), then you are just unlucky if you need it. Seeing that you propose reserve as a replacement for resize, I will put my up-vote in ice until it's fixed. – Copyreader

@Christian Rau You are right, QVector::resize will set size() to return given size, while QList::reserve() will not affect this. – Jamila

@ChristianRau thank you for your contributions to my answer - it is exciting to see that posting answers on SO is great way to learn, too :). – Jamila

How did you come up with the 200KB for 50 items in the QList case?? – Colonize

I found a thread about this question here - lists.trolltech.com/qt4-preview-feedback/2005-06/…. It seems that one reason is they don't want to enforce a default constructor, but I'm not sure if it's a valid reason. – Ragg

@Colonize if one pointer has size of 4B on 32bit system, and, as I understood from the documentation, internal buffer is storing pointers, for 50 elements, size will be 200B... Oh, sh*t... Thanks! – Jamila

satuon this is an assumption from the op in the thread you mentioned. @Burgos you are welcome :D – Colonize

How would you create 1MB object? – Inexperienced

Answer 3

wasle answer is good, but it'll add the same object multiple time. Here is an utility functions that will add different object for list of smart pointers.

template<class T>
void resizeSmartList(QList<QSharedPointer<T> > & list, int newSize) {
    int diff = newSize - list.size();

    if (diff > 0) {
        list.reserve(diff);
        while (diff>0){
            QSharedPointer<T> t = QSharedPointer<T>(new T);
            list.append(t);
            diff--;
        }
    }else if (diff < 0) list.erase(list.end() + diff, list.end());
}

For use without smart pointers, the following will add different objects to your list.

template<class T>
void resizeList(QList<T> & list, int newSize) {
    int diff = newSize - list.size();

    if (diff > 0) {
        list.reserve(diff);
        while (diff>0){
            T t = new T;
            list.append(t);
            diff--;
        }
    }else if (diff < 0) list.erase(list.end() + diff, list.end());
}

Also remember that your objects must have default constructor (constructor declared in the header with arg="someValue") or else it will fail.

Maggi

Answer 4

Just use something like

QList<Smth> myList;
// ... some operations on the list here
myList << QVector<Smth>(desiredNewSize - myList.size()).toList();

Essentially, there are these to/from Vector/List/Set() methods everywhere, which makes it trivial to resize Qt containers when necessary in a somewhat manual, but trivial and effective (I believe) way.

Another (1 or 2-liner) solution would be:

myList.reserve(newListSize); // note, how we have to reserve manually
std::fill_n(std::back_inserter(myList), desiredNewSize - myList.size(), Smth());

-- that's for STL-oriented folks :)

For some background on how complex an effective QList::resize() may get, see:

• bugreports.qt.io/browse/QTBUG-42732 , and
• codereview.qt-project.org/#/c/100738/1//ALL

Laundryman

For the And is there an equivalent function?, this is quite surprizing, noone (of the 4K viewers) checked out the docs for potentially relevant signatures :) – Laundryman

@Downvoting coward, let's have words, when you have enough spirit :) – Laundryman

This makes absolutely no sense. The question is whether QList lacks a resize method. The answer is: because Qt containers have plenty of problems, and this is just yet another one. – Lingam

@Lingam Well, it makes enough sense for the case, when you want to create a QList of given size, at least; I quoted the respective sub-question in a comment above :) – Laundryman

But the question isn't about "creating a QList of a given size", and even if it were, going through a conversion from/to QVector is a plain nonsense. This is C++, not Python or Perl! We do care about efficiency! – Lingam

Building a hyperspace ship, huh? :) (coming from "Which airplane we want to build?") I corrected the answer, though -- it is still a one liner, and pretty effective, to my taste :) – Laundryman

@Lingam I'd be interested in this measured against other solutions on this page, wanna a bet on a beer next Qt Summit? :) – Laundryman

Your code doesn't consider a resize that shrinks the list. And I can't consider a good answer one that goes through allocating a temporary QVector (at least 1 heap allocation), default construct the contents, allocating a temporary QList (1 to (QVector's size+1) heap allocations), copying the data from the vector, possibly reallocating the original list, copying the data AGAIN at the end of the original list, deallocating the list and the vector. Are you serious? – Lingam

@Lingam Sure, it does not account for shrinking (which the OP, probably di not have in mind either), why be that picky -- but one may trivially add that to create a testable function, and I am not quite afraid of it being slow with cheaply constructed / copied items. – Laundryman

I wonder who is the guy working on that code, huh... (hint: me) – Lingam

@Lingam Yes, I was surprised you did not mention that :) – Laundryman