Fast removal with lists

This is a discussion on Fast removal with lists within the C++ Programming forums, part of the General Programming Boards category; I'm pretty confused about lists. They work as I would expect except for removing elements. The erase() method wants an ...

  1. #1
    JMK
    JMK is offline
    Registered User
    Join Date
    May 2010
    Posts
    24

    Fast removal with lists

    I'm pretty confused about lists. They work as I would expect except for removing elements.

    The erase() method wants an iterator. But if I remove one element, the position of all the others after it will change! So it doesn't seem possible to quickly remove an element at any arbitrary position in the list.

    In other languages I would do something like this:

    link = link.push_back(object);

    And then this would remove the object from the list:

    link.Remove();

    Is there any way to get that kind of fast removal with C++?

  2. #2
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,689
    Why do you think that std::list does not do fast removal in the manner you described? Have you tried using erase just to see what happens?
    Last edited by whiteflags; 01-06-2011 at 02:02 AM.

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,712
    Quote Originally Posted by JMK
    The erase() method wants an iterator. But if I remove one element, the position of all the others after it will change! So it doesn't seem possible to quickly remove an element at any arbitrary position in the list.
    I don't really understand your concern. The erase member function erases the element pointed to by the iterator and invalidates that iterator (and all copies of it). Other iterators pointing to other elements remain valid. What makes removing an element at any arbitrary position slow is the linear time traversal to reach that element. However, this is true of linked lists in general, regardless of the programming language.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Quote Originally Posted by JMK View Post
    I'm pretty confused about lists. They work as I would expect except for removing elements.

    The erase() method wants an iterator. But if I remove one element, the position of all the others after it will change! So it doesn't seem possible to quickly remove an element at any arbitrary position in the list.
    Assuming a linked-list, then no it would not.

    Do you understand the difference between an "array" an a "linked-list"?

    The generic term of a "list" is often used to refer to either of these two since a list basically just means a sequence, and a sequence simply means that each item (except first and last) has a predecessor and a successor. In programming, how we represent that sequence is important. An array and a linked-list are some ways of representing a sequence. Most programming languages have ways of representing these two main data structures.

    Arrays and linked-lists have different advantages and disadvantages. One has added bennefits in that you can jump to any element in constant time, and the other does not. One has the advantage that elements can be removed in constant time, and the other does not.

    If you essentially want the properties of an array, then in C++ use a std::vector.
    If you essentially want the properties of a linked-list, then in C++ use a std::list.
    It sounds to me like you're using a std::vector where you actually want to be using a std::list.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked Lists?!
    By hwing91 in forum C Programming
    Replies: 32
    Last Post: 11-08-2010, 05:13 PM
  2. Dynamic Lists? Is it possible? Is it a logical solution?
    By arcaine01 in forum C++ Programming
    Replies: 10
    Last Post: 07-23-2009, 01:08 AM
  3. Help creating lists of pointers
    By The_Kingpin in forum C Programming
    Replies: 2
    Last Post: 12-11-2004, 07:10 PM
  4. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  5. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21