Can you change a std::list while iterating through it?

Question

In the following functions, it it entirely possible for the IObserver's Process() function to try to remove itself from the notify list, using the this pointer's DeleteObserver().

This causes hell with the iterators (not surprisingly!), is there a way round this? Or should I be taking a closer look at my design?

void cButtonManager::DeleteObserver(IObserver *observer)
{
    list<IObserver*>::iterator iter;
    for (iter = m_ObserverList.begin(); iter != m_ObserverList.end(); ++iter)
    {
        if (*iter == observer)
        {
            // Found the specified observer in the list, delete it
            m_ObserverList.erase(iter);
            return;
        }
    }
}

void cButtonManager::NotifyObservers(void)
{
    list<IObserver*>::iterator iter;
    for (iter = m_ObserverList.begin(); iter != m_ObserverList.end(); ++iter)
    {
        (*iter)->Process(this);
    }
}

For example, imagine that the list is a collection of people that subscribe to a magazine and the Process() function is the delivery of a new magazine issue; if the magazines latest issue is awful the subscriber may wish to un-subscribe as a direct result of that issue.

This code is legal as far as I see. The only problem you may have is if you have several threads accessing the list, or if you receive a `DeleteObserver` call while you're in the middle of another loop through the list. — Diego Sevilla, Sep 29 '11 at 15:05
@GWW: The `(iter*)->Process()` function returns and the program crashes, because iter now points to nothing at all, so the `++iter` operation fails. @Diego: Yup, you got it, the deletion is occurring within the process-loop. — Siyfion, Sep 29 '11 at 15:05
@Siyfion, but this means that `Process` is indirectly calling `DeleteObserer`. If that happens, yes, this code is problematic. — Diego Sevilla, Sep 29 '11 at 15:08
Duplicate of http://stackoverflow.com/questions/596162/can-you-remove-elements-from-a-stdlist-while-iterating-through-it ? — ltjax, Sep 29 '11 at 15:11
@ltjax, nope, because iterator in place where he calls `erase()` is not the same iterator, that makes the problem... — Griwes, Sep 29 '11 at 15:20

Griwes · Accepted Answer · 2011-09-29T15:56:58.950

3

Edit:

Some people in comments corrected me, so I will change this answer. But don't upvote, as it's the commenters' solution, not mine.

(*iter++)->Process();

edited Sep 29 '11 at 15:56

answered Sep 29 '11 at 15:19

Griwes

8,805
2
43
70

You could use the iterator returned by `erase` and return that from `Process`, assigning it to `iter`. – rubenvb Sep 29 '11 at 15:40
Yes, but that would require changes in `Process()`; here, only the code that uses it is required to be changed. Do you think that `Process()` is always called in loop? I don't think so, so returning an iterator from it would result in compiler warnings. And it is obviously not always used with iterators. – Griwes Sep 29 '11 at 15:44
6

You can also write `(*iter++)->Process();`. It's a bit tricksy, but the sequence point at the start of the function call to `Process` guarantees that the side effect of incrementing `iter` occurs before the old value of `iter` can be invalidated by whatever `Process` does. – Steve Jessop Sep 29 '11 at 15:45
`list::iterator` has no `operator+()`. – Robᵩ Sep 29 '11 at 15:46
Griwes: I don't know what `Process` does, nor when and how it is used in the rest of the OP's code. It was only a suggestion of how C++ can help you avoid an extra line of code. – rubenvb Sep 29 '11 at 15:47
@SteveJessop, hmm, I didn't think about that. But a question, is it a standard-defined or ID (probably the first one, but I would say same thing about some ID features of C++...)? – Griwes Sep 29 '11 at 15:48
@rubenvb, read what I wrote once again. And what if there was no `erase()` called, where should the `Process` get the iterator from? – Griwes Sep 29 '11 at 15:50
1

@Griwes: it's guaranteed by the standard, although it takes some close reading to convince yourself of it. Basically the operand of `operator->` is evaluated before the operator is, and hence before the call to `Process`. The sequence point on the function call forces the side-effects to be completed too. – Steve Jessop Sep 29 '11 at 15:52
I'm perfectly happy for you to get upvotes for this: I suggested the change because (a) it's shorter than your code, and (b) you were going to have to change your code anyway to get rid of the `iter+1` :-) – Steve Jessop Sep 29 '11 at 15:58
@SteveJessop, I'm just trying to be honest :P – Griwes Sep 29 '11 at 16:00
2

@Griwe, the upvotes are not there for you, they're for the readers. :) – avakar Sep 29 '11 at 16:09
@SteveJessop very nice solution there it's clean, elegant and works! Some may say that it's slightly tricksy, but it's a lot better than the alternative. – Siyfion Sep 30 '11 at 07:58
2

Even better, I've realised it's less tricksy than I thought. In the case of `std::list`, the iterator must be a user-defined type (well library-defined, but the effect is the same). It can't just be a pointer like `vector` can, or like a generic iterator could be. So, it has an `operator++` function, and hence the side-effects of `iter++` are guaranteed to have completed when `operator++` returns, which is even earlier than I said above. – Steve Jessop Sep 30 '11 at 08:40

pmr · Answer 2 · 2011-09-29T16:14:15.873

1

I don't see why you are not using list::remove here. That seems like a perfect match to me.

For the problem in NotifyObserver I would not let Process do the removing itself but rather let it signal that it wants itself to be removed from the list of observer. Plainly: return a bool from Process to signal and then call list::erase on it. Assign the return value of erase to the current iter.

edited Sep 29 '11 at 16:14

answered Sep 29 '11 at 15:49

pmr

58,701
10
113
156

1

FWIW, `list::remove` removes all elements matching a value, whereas the code shown in `DeleteObserver` only removes one. I strongly suspect that there can only *be* one match, so the difference is only one of performance, not effect. I don't think it helps with actual question, though, which is about the code in `NotifyObservers`, not the code in `DeleteObserver` (which `Process` is permitted to call, but presumably `Process` can do other worthwhile things too). – Steve Jessop Sep 29 '11 at 15:57
@SteveJessop The current behaviour rather looks like a bug to me than intentional, but that is up to the OP. I tried to provide a simple solution for the second function. – pmr Sep 29 '11 at 16:15
@pmr Indeed there can only be one match in the list to an Observer, the `AddObserver()` function (not shown) checks for uniqueness. The reason why I am using erase is because I was wondering if I would need the returned iterator (which `remove()` doesn't provide). Also, the other problem is that Process *could* remove itself from the list, but it's also entirely possible that `DeleteObserver()` is called elsewhere too (in the same thread however). – Siyfion Sep 30 '11 at 07:55

Can you change a std::list while iterating through it?

2 Answers2