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.
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.
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.
phillip_Qt (8th October 2009), umulingu (1st January 2010)
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):
- Use Qt Assistant
- Search the forum
If you haven't found solution yet then create new topic with smart question.
have a look at this article.
Qt Assistant -- rocks!
please, use tags [CODE] & [/CODE].
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).
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.
Bookmarks