Results 1 to 9 of 9

Thread: Remove first n elements from QList

  1. #1
    Join Date
    May 2007
    Posts
    32
    Thanks
    3
    Qt products
    Qt4
    Platforms
    Windows

    Default Remove first n elements from QList

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

  2. #2
    Join Date
    May 2007
    Posts
    32
    Thanks
    3
    Qt products
    Qt4
    Platforms
    Windows

    Default Re: Remove first n elements from QList

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

  3. #3
    Join Date
    Feb 2006
    Location
    Romania
    Posts
    2,744
    Thanks
    8
    Thanked 541 Times in 521 Posts
    Qt products
    Qt4
    Platforms
    Unix/X11 Windows

    Default Re: Remove first n elements from QList

    Qt Code:
    1. for( int i = 0; i != n; i ++ )
    2. {
    3. T obj = list.takeFirst();
    4. //eventually delete obj if it was allocated previously
    5. }
    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

  4. #4
    Join Date
    May 2007
    Posts
    32
    Thanks
    3
    Qt products
    Qt4
    Platforms
    Windows

    Default Re: Remove first n elements from QList

    I can't understand your variant.
    Can you ell me why i can't use this:
    Qt Code:
    1. iterator QList::erase ( iterator begin, iterator end )
    2. This is an overloaded member function, provided for convenience.
    3. 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 

  5. #5
    Join Date
    Feb 2006
    Location
    Romania
    Posts
    2,744
    Thanks
    8
    Thanked 541 Times in 521 Posts
    Qt products
    Qt4
    Platforms
    Unix/X11 Windows

    Default Re: Remove first n elements from QList

    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

  6. #6
    Join Date
    May 2007
    Posts
    32
    Thanks
    3
    Qt products
    Qt4
    Platforms
    Windows

    Default Re: Remove first n elements from QList

    Thank you... Understood!

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

    it is will be the best variant?

  7. #7
    Join Date
    Feb 2006
    Location
    Romania
    Posts
    2,744
    Thanks
    8
    Thanked 541 Times in 521 Posts
    Qt products
    Qt4
    Platforms
    Unix/X11 Windows

    Default Re: Remove first n elements from QList

    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

  8. The following user says thank you to marcel for this useful post:

    pakulo (2nd June 2007)

  9. #8
    Join Date
    May 2007
    Posts
    32
    Thanks
    3
    Qt products
    Qt4
    Platforms
    Windows

    Default Re: Remove first n elements from QList

    Thanks a lot!

  10. #9
    Join Date
    Mar 2006
    Location
    The Netherlands
    Posts
    300
    Thanks
    9
    Thanked 29 Times in 29 Posts
    Qt products
    Qt3 Qt4
    Platforms
    Unix/X11

    Default Re: Remove first n elements from QList

    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

Similar Threads

  1. Accessing QList Objects
    By magikalpnoi in forum Qt Programming
    Replies: 7
    Last Post: 21st September 2006, 21:43
  2. QSettings again ... how to remove array elements
    By Mike in forum Qt Programming
    Replies: 4
    Last Post: 11th January 2006, 09:58

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.