[Qt-interest] QList vs QVector

[Ankit Agarwal]

Hi Martin,
Thanks for the detailed information. In my case, I am not editing the list
many a times, i.e. insertions and deletion operations are not being done.
Thus, I though of using QVector, as the data shall be stored in adj. memory
location giving be faster access(QVector of 50000 elements). But, what I
observed was that QList is giving be a lower traversal time than QVector.
Why am I getting such behavior ?

On Fri, Jul 31, 2009 at 3:49 PM, Martin Hofius <Martin at hofius-online.com>wrote:

> 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
>



-- 
Regards,
Ankit Agarwal
Blog : http://ankit17.wordpress.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.qt-project.org/pipermail/qt-interest-old/attachments/20090805/b59bce7a/attachment.html