Results 1 to 7 of 7

Thread: Vector vs List

  1. #1
    Join Date
    Oct 2007
    Posts
    201
    Thanks
    19
    Thanked 1 Time in 1 Post
    Qt products
    Qt4
    Platforms
    Unix/X11 Windows

    Default Vector vs List

    Hi Everybody
    Can any one tell me when should i go for list and wen for vector? I'll be thankful for your kind help.
    Cheers,
    Phillip



    --- Please post the solution you got to solve your problem. It may help others.

  2. #2
    Join Date
    Dec 2007
    Posts
    628
    Thanks
    3
    Thanked 89 Times in 87 Posts
    Qt products
    Qt3 Qt4 Qt5 Qt/Embedded
    Platforms
    MacOS X Unix/X11 Windows

    Default Re: Vector vs List

    See, items in a vector are on adjacent memory locations so inserting in front and in between is slow. Because front/mid insertion can lead to large numbers of items having to be moved by one position in memory. So if you have no requirement of front/mid insertion the go for vector otherwise go for list.
    And benefit of a list is more than vector, because insertion is fast and index-based access is very fast.

  3. The following 2 users say thank you to yogeshgokul for this useful post:

    phillip_Qt (8th October 2009), umulingu (1st January 2010)

  4. #3
    Join Date
    Oct 2007
    Posts
    201
    Thanks
    19
    Thanked 1 Time in 1 Post
    Qt products
    Qt4
    Platforms
    Unix/X11 Windows

    Default Re: Vector vs List

    Quote Originally Posted by yogeshgokul View Post
    See, items in a vector are on adjacent memory locations so inserting in front and in between is slow. Because front/mid insertion can lead to large numbers of items having to be moved by one position in memory. So if you have no requirement of front/mid insertion the go for vector otherwise go for list.
    And benefit of a list is more than vector, because insertion is fast and index-based access is very fast.
    Thank you Yogesh.
    Cheers,
    Phillip



    --- Please post the solution you got to solve your problem. It may help others.

  5. #4
    Join Date
    Jan 2008
    Location
    Poland
    Posts
    687
    Thanks
    4
    Thanked 140 Times in 132 Posts
    Qt products
    Qt4 Qt5
    Platforms
    Unix/X11 Windows

    Default Re: Vector vs List

    QList is not a real linked list (QLinkedList is) so its insertion cost is still O(n) like in QVector. The advantage is in prepending where in QList it's amortized O(1) (means that average complexity is O(1) but can be O(n) in some cases - in QVector it's always O(n)). Generaly, as it stands in docs, QList is a bit faster and good for most cases. The only advantage of QVector is that you really have all items in adjacent memopry position, so you can iterate through items with a pointer for example. If you want fast insertion (O(1)) then use QLinkedList, but access to items is iterator-based, not index-based.
    I would like to be a "Guru"

    Useful hints (try them before asking):
    1. Use Qt Assistant
    2. Search the forum

    If you haven't found solution yet then create new topic with smart question.

  6. #5
    Join Date
    Aug 2008
    Location
    Ukraine, Krivoy Rog
    Posts
    1,963
    Thanked 370 Times in 336 Posts
    Qt products
    Qt3 Qt4 Qt5
    Platforms
    MacOS X Unix/X11 Windows

    Default Re: Vector vs List

    Quote Originally Posted by phillip_Qt View Post
    Hi Everybody
    Can any one tell me when should i go for list and wen for vector? I'll be thankful for your kind help.
    have a look at this article.
    Qt Assistant -- rocks!
    please, use tags [CODE] & [/CODE].

  7. #6
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    33,359
    Thanks
    3
    Thanked 5,015 Times in 4,792 Posts
    Qt products
    Qt3 Qt4 Qt5 Qt/Embedded
    Platforms
    Unix/X11 Windows Android Maemo/MeeGo
    Wiki edits
    10

    Default Re: Vector vs List

    Quote Originally Posted by faldżip View Post
    QList is not a real linked list (QLinkedList is) so its insertion cost is still O(n) like in QVector. The advantage is in prepending where in QList it's amortized O(1) (means that average complexity is O(1) but can be O(n) in some cases - in QVector it's always O(n)).
    Insertion (as in "inserting in an arbitrary place) is O(n/2) for QList (when you are inserting items in the middle of the list) and O(n) for QVector (when you are inserting items at the beginning of the vector). So for appending both structures are equivalent (O(1)), for prepending QList is faster (O(1) vs O(n)) and for insertion they are asymptotically equal (although QList is faster on average as the most expensive insert is O(n/2) as opposed to O(n) for vector).
    Your biological and technological distinctiveness will be added to our own. Resistance is futile.

    Please ask Qt related questions on the forum and not using private messages or visitor messages.


  8. #7
    Join Date
    Oct 2007
    Posts
    201
    Thanks
    19
    Thanked 1 Time in 1 Post
    Qt products
    Qt4
    Platforms
    Unix/X11 Windows

    Default Re: Vector vs List

    Thank you all for your reply. It is really helped me a lot to understand the vector and list.
    Cheers,
    Phillip



    --- Please post the solution you got to solve your problem. It may help others.

Similar Threads

  1. QFtp hidden files/folder's list
    By jay in forum Qt Programming
    Replies: 1
    Last Post: 26th December 2008, 13:12
  2. Replies: 2
    Last Post: 19th September 2008, 06:21
  3. Single slot for multiple list boxes
    By Sheetal in forum Qt Programming
    Replies: 1
    Last Post: 15th April 2008, 07:53
  4. Replies: 1
    Last Post: 22nd October 2007, 03:04
  5. QComboBox drop list button events
    By maird in forum Qt Programming
    Replies: 5
    Last Post: 20th October 2007, 20:25

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Digia, Qt and their respective logos are trademarks of Digia Plc in Finland and/or other countries worldwide.