[Qt-interest] QList vs QVector

[Martin Hofius]

Hi,
please send your answer to the mailing list...

Am Donnerstag, 30. Juli 2009 schrieben Sie:
> Hi,
> I have a demo file to study the time complexity. The program is attached
> along with this mail.
>
> What i found was that QVector is slower than QList even when I am just
> traversing all the elements.
> Can you please help out with this as in why an i getting this kind of
> behavior.
>
sorry I have no time to examine the qt source codes and to test it for myself. 
But this text from
http://doc.trolltech.com/4.5/qlist.html
may explain what you got:


8<----------------------------------------------------------------------------------------------
QList<T>, QLinkedList<T>, and QVector<T> provide similar functionality. Here's 
an overview:

    * For most purposes, QList is the right class to use. Its index-based API 
is more convenient than QLinkedList's iterator-based API, and it is usually 
faster than QVector because of the way it stores its items in memory. It also 
expands to less code in your executable.
    * If you need a real linked list, with guarantees of constant time 
insertions in the middle of the list and iterators to items rather than 
indexes, use QLinkedList.
    * If you want the items to occupy adjacent memory positions, use QVector.

Internally, QList<T> is represented as an array of pointers to items of type 
T. If T is itself a pointer type or a basic type that is no larger than a 
pointer, or if T is one of Qt's shared classes, then QList<T> stores the 
items directly in the pointer array. For lists under a thousand items, this 
array representation allows for very fast insertions in the middle, and it 
allows index-based access. Furthermore, operations like prepend() and 
append() are very fast, because QList preallocates memory at both ends of its 
internal array. (See Algorithmic Complexity for details.) Note, however, that 
for unshared list items that are larger than a pointer, each append or insert 
of a new item requires allocating the new item on the heap, and this per item 
allocation might make QVector a better choice in cases that do lots of 
appending or inserting, since QVector allocates memory for its items in a 
single heap allocation.

Note that the internal array only ever gets bigger over the life of the list. 
It never shrinks. The internal array is deallocated by the destructor and by 
the assignment operator, when one list is assigned to another.
8<---------------------------------------------------------------------------------

Greetings
Martin