[Development] HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO

Kevin Kofler kevin.kofler at chello.at
Mon Jul 27 21:44:32 CEST 2015


Giuseppe D'Angelo wrote:
> Also nobody says that middle insertions of removals should be "extra
> cheap".

This is a very common operation for a random-access, ordered but not auto-
sorted, array/vector-type list. The "array of pointers" data structure is an 
effective compromise to make this reasonably cheap (though still O(n)) while 
keeping the O(1) random access.

>> * Accessing the i-th element is performed in guaranteed O(1) time.
> 
> For "bad" types for QList, that O(1) is hiding two indirections. Only
> one with QVector. That's a huge cost you're not talking about.

It's a factor 2, vs. a factor sizeof(T)/sizeof(T*) in the opposite direction 
for the middle insertions/removals. For any nontrivial class, 
sizeof(T)/sizeof(T*) can be a lot larger than 2.

>> * Inserting an element performs at most 1 heap allocation. (This is the
>> only
>>   performance metric that can change, but the changing from the usual 1
>>   to 0 is a very welcome optimization for the cases it applies to.)
> 
> Inserting an element of a wrong type performs *at least* 1 heap
> allocation. Consider:
> 
>> ListContainer<WrongType> list; list.reserve(1000); /* insert 1000
>> elements */
> 
> This performs (at least?) 1001 heap allocations with QList and 1 with
> QVector.

This performs only 1 allocation with QList. The documentation says: "Note 
that the reservation applies only to the internal pointer array." Looking at 
the code, the reserved pointers are simply not initialized at all (not even 
zeroed). The actual 1000 allocations of the WrongType elements are only done 
if and when you actually insert them.

Therefore, you get the behavior I explained: insert does 1 allocation for a 
"wrong" type (or 2 in the rare event it needs to grow the pointer array), 0 
for a "good" type (or 1 in the rare event it needs to grow the array). The 
latter matching the behavior of QVector, of course.

        Kevin Kofler




More information about the Development mailing list