Thread: Fast removal with lists

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?

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.

Originally Posted by JMK

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.