CODEWITHSUNDEEP
c++listiterator
Mark Ransom
Mark Ransom

Reputation: 308392

Efficient way to iterate a std::list that's changing?

I'm trying to iterate through a std::list but there's a problem - the operations performed during the iteration may end up adding or removing an element from the list. Additions are not a problem in this case, but a removal can end up invalidating any iterator in the list, including either the current or next item in the sequence.

The point where the decision is made to modify the list is far removed from the iteration loop - the debugger is showing 40 function calls in the call stack between the two. Because of that it won't be possible to modify the iterator based on the removal.

The only thing I can think of is to make a copy of the list at the start and iterate over that, testing each element to make sure it's still in the master list. That's an O(n^2) proposition that I'd like to avoid if possible.

Upvotes: 8

Views: 406

Answers (4)

Evgeny Kluev
Evgeny Kluev

Reputation: 24667

Here are some more options.

1. Splice

Instead of removing an element, "modifying" code could move it to some temporary list with splice method. Splicing single element is a constant time operation. And it does not invalidate any iterators or references (even for moved element).

Prior to moving an element, "modifying" code should advance master copy of the list iterator (belonging to "iterating" code).

"Iterating" code should just clear this temporary list after each iteration.

Advantages: no need to add any flags to the containing elements.

Disadvantages: some performance hit because of the need to clear temporary list; needed external interface to advance iterator belonging to "iterating" code; if some code between "iterating" and "modifying" codes needs to inspect next/previous elements relative to "removed" element, it sees only other "removed" elements instead of the rest of the list.

2. Splice with "locked" flag

If you set "locked" flag for the element currently pointed by iterator, "modifying" code may use splice only for this single element and remove others in usual way.

"Iterating" code should just clear temporary list after each iteration.

Advantages: practically no performance hit.

Disadvantages: need to modify list's elements; needed external interface to advance iterator belonging to "iterating" code; if some code between "iterating" and "modifying" codes needs to inspect next/previous elements relative to "removed" element, it does not find anything.

3. "Locked" and "removed" flags

If you set "locked" flag for the element currently pointed by iterator, "modifying" code may just set the "removed" flag for this single element and remove others in usual way.

"Iterating" code should (after each iteration) just remove an element flagged for removal.

Advantages: practically no performance hit; if some code between "iterating" and "modifying" codes needs to inspect next/previous elements relative to "removed" element, it works as expected.

Disadvantages: need to modify list's elements.

Upvotes: 2

Mark B
Mark B

Reputation: 96281

Two possible approaches come to mind (in addition to making a copy of the list):

1) Don't erase stuff from the list right away. Instead, build another container of iterators to erase once you're all done with the full iteration. This does change the behavior ("deleted" elements may still be acted upon) so I don't know if it helps you.

2) Have your list contain either pointers or a pair with the item/validity flag, and simply clear the validity. Then once you're done iterating the first time do one more iteration cleaning up the retired nodes.

Upvotes: 0

Boris
Boris

Reputation: 622

can end up invalidating any iterator in the list

Not any.

Look at the description of std::list::erase:

Iterator validity

  • Iterators, pointers and references referring to elements removed by the function are invalidated.
  • All other iterators, pointers and references keep their validity

Conclusion for erase: only removed element become to be invalid. All of other stay valid. And, in this case, you have an opportunity to implement O(n) in most contexts.

Upvotes: 1

user1182183
user1182183

Reputation:

You have three options:

  1. Like you said make a local copy of the list

  2. when the iterators are invalidated start over again (and maybe skip n iterations? [with continue])

  3. Edit: Like Pubby said, mark removed elements expired, and when you add elements use the skipping n iterations stuff :)

Iterators don't allow access by index so this makes it a bit harder to come up with a elegant solution for your problem.

Upvotes: 2

Related Questions