[Qt-interest] QList vs QVector

[Patric]

I think QList is implemented as linked list, and QVector is just static 
list.

Regards,
Patric


----- Original Message ----- 
From: "Martin Hofius" <Martin at hofius-online.com>
To: <qt-interest at trolltech.com>
Sent: Friday, July 31, 2009 1:19 PM
Subject: Re: [Qt-interest] QList vs QVector


> 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
> _______________________________________________
> Qt-interest mailing list
> Qt-interest at trolltech.com
> http://lists.trolltech.com/mailman/listinfo/qt-interest
>