How i can remove first n elements from QList? I need effective and speed algorithm.
How i can remove first n elements from QList? I need effective and speed algorithm.
I see in the manual function erase, but i can't understand how it work. Help plz...
Qt Code:
for( int i = 0; i != n; i ++ ) { T obj = list.takeFirst(); //eventually delete obj if it was allocated previously }To copy to clipboard, switch view to plain text mode
This is the fastest way, since takeFirst() consumes O(1) time.
Therefore you get O(n) asymptotic behavior for removing the first n elements.
Regards
I can't understand your variant.
Can you ell me why i can't use this:
Qt Code:
This is an overloaded member function, provided for convenience. Removes all the items from begin up to (but not including) end. Returns an iterator to the same item that end referred to before the call.To copy to clipboard, switch view to plain text mode
I offered that solution because you asked for something very fast.
It the docs there is stated that takeFirst takes a constant time to execute, meaning that no loops are involved. The element is just returned with minimal( non-linear, but constant) computations.
Removing n items with takes first means the operation will take linear time( best, average, worst cases ). Linear execution time is also noted with O(n).
erase() will work but it is possible to be more generic an not to be as fast as takeFirst.
Regards
Thank you... Understood!
See, i use:
for (int i = 0; i < n; ++i)
list.removeFirst();
it is will be the best variant?
So it's pretty clear.T QList::takeFirst ()
Removes the first item in the list and returns it.
This is the same as takeAt(0).
This operation is very fast (constant time), because QList preallocates extra space on both sides of its internal buffer to allow for fast growth at both ends of the list.
If you don't use the return value, removeFirst() is more efficient.
See also takeLast(), takeAt(), and removeFirst().
Regards
pakulo (2nd June 2007)
Thanks a lot!
It preallocates extra space? And here I thought QList was a linked list. Such a list wouldn't need preallocation to grow at both ends. But now I see. There is also a QLinkedList class. But since there is also a QVector class (which would use a dynamic array, I guess), how is QList implemented?
"The strength of a civilization is not measured by its ability to wage wars, but rather by its ability to prevent them." - Gene Roddenberry
Bookmarks