Remove first n elements from QList

[pakulo]

How i can remove first n elements from QList? I need effective and speed algorithm.

[pakulo]

I see in the manual function erase, but i can't understand how it work. Help plz...

[marcel]

for( int i = 0; i != n; i ++ )
{
T obj = list.takeFirst();
//eventually delete obj if it was allocated previously
}


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

[pakulo]

I can't understand your variant.
Can you ell me why i can't use this:

iterator QList::erase ( iterator begin, iterator end )
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.

[marcel]

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

[pakulo]

Thank you... Understood! :)

See, i use:
for (int i = 0; i < n; ++i)
list.removeFirst();

it is will be the best variant?

[marcel]

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().


So it's pretty clear.

Regards

[pakulo]

Thanks a lot!

[Michiel]

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?