Efficient way to modify std :: list?

Question

I am trying to iterate through std::list , but there is a problem - operations performed during iteration can lead to the addition or removal of an item from the list. Add-ons are not a problem in this case, but deletion may invalidate any iterator in the list, including either the current or the next element in the sequence.

The point at which the decision to change the list is made is far from the iteration cycle - the debugger shows 40 function calls in the call stack between them. Because of this, it will not be possible to modify the iterator based on deletion.

The only thing I can think of is to make a copy of the list at the beginning and iterate over it, testing each item to make sure it is still in the main list. This is an O (n ^ 2) sentence, which I would like to avoid, if possible.

Answer 1

You have three options:

• As you said, make a local copy of the list

• when the iterators are invalid, start over (perhaps skip n iterations? [using continue ])

• Edit: As Pubby said, mark the deleted items have expired, and when you add items, use skips n iterations :)

Iterators do not allow access by index, so it's a little harder to come up with an elegant solution for your problem.

Answer 2

may invalidate any iterator in the list

Nothing.

See the description of std::list::erase :

Iterator validity

• Iterators, pointers, and references that reference elements; a deleted function is not valid.
• All other iterators, pointers, and links remain valid.

Conclusion for deletion: only the deleted item becomes invalid. All others remain valid. And in this case, you have the opportunity to implement O (n) in most contexts.

Answer 3

Here are some more options.

1. Splicing

Instead of deleting an element, the modifier code can move it to a temporary list using the splice method. Combining one element is a constant time operation. And this does not invalidate any iterators or references (even for the moved item).

Before moving an item, the “modification” code must advance the main copy of the list iterator (belonging to the “iterating” code).

The iterating code should simply clear this temporary list after each iteration.

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

Disadvantages: some performance hit due to the need to clear the temporary list; an external interface is needed to promote an iterator belonging to the "iterating" code; if any code between the "iterative" and "modifying" codes should check the next / previous elements with respect to the "remove" element, it sees only the other "deleted" elements, and not the rest.

2. Connect to the blocked flag

If you set the “blocked” flag for an element that is currently specified by an iterator, the “modifying” code can use splicing only for this single element and delete others in the usual way.

The iterative code should just clear the temporary list after each iteration.

Advantages: virtually no performance.

Disadvantages: it is necessary to change the list items; an external interface is needed to promote an iterator belonging to the "iterating" code; if any code between "iterative" and "modifying" codes should check the next / previous elements with respect to the "remove" element, it does not find anything.

3. Flags "Locked" and "Remove"

If you set the “blocked” flag for the element that the iterator currently indicates, the “modifying” code can simply set the “delete” flag for this single element and delete the others in the usual way.

The iteration code should (after each iteration) simply delete the item marked for deletion.

Advantages: virtually no performance; if some code between the "iterating" and "modifying" codes should check the next / previous elements against the "remove" element, it works as expected.

Disadvantages: it is necessary to change the list items.

Answer 4

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

1) Do not remove material from the list immediately. Instead, create another container of iterators to erase as soon as you are done with the full iteration. This changes the behavior (the “deleted” elements can still act), so I don’t know if this will help you.

2) Indicate in your list either pointers or a pair with the item / validity flag and just clear the reality. Then, as soon as you finish the iteration for the first time, perform another iteration, clearing the back nodes.