iterator invalidation trouble

[Alexander Stippler]

Hi,

I've got trouble with some well known issue. Iterator invalidation. My
situation:

for (it=v.begin(); it!=v.end(); ++it) {
f(*it);
}

Under some circumstances, f may alter the container by removing the current
item. Thus the iterator it gets invalid. My question is, if there is a way
to handle this specific case. The problem is that the for loop is user
code, and the user should not even notice that v changed, so I cannot
simply introduce a second iterator inside the for loop. The iterator it
should simply go on iterating with the following item, if *it is deleted.
*it is defininitely the only item which can be deleted by f.
I think this problem is rather general. Are there any threads online on
"robust iterators for c++"? Is there a trick for my situation?

regards,
alex

 

[Gianni Mariani]

Hi,

I've got trouble with some well known issue. Iterator invalidation. My
situation:

for (it=v.begin(); it!=v.end(); ++it) {
f(*it);
}

Under some circumstances, f may alter the container by removing the current
item. Thus the iterator it gets invalid. My question is, if there is a way
to handle this specific case. The problem is that the for loop is user
code, and the user should not even notice that v changed, so I cannot
simply introduce a second iterator inside the for loop. The iterator it
should simply go on iterating with the following item, if *it is deleted.
*it is defininitely the only item which can be deleted by f.
I think this problem is rather general. Are there any threads online on
"robust iterators for c++"? Is there a trick for my situation?

The way I've solved this problem in the past is to not erase the objects.

I made the container have pointers to the objects and once the user was
done with the iterating it would erase the "empty" pointers.

I also provided a "traverser" template that would wrap the for loop with
the appropriate cleaning call at the end of the loop.

 

[Ron Natalie]

I think this problem is rather general. Are there any threads online on
"robust iterators for c++"? Is there a trick for my situation?

You say the user shouldn't know if the container has changed, however
since you expose all the ugliness to him, he does have to know.

It's hard to understand what solution to propose without a better
description of the problem. Why is the user responsible for
iterating some function f() over a list when f() is not under
their control. Possibly this is better solved by passing the
container v (or begin and end iterators) to f() and letting it
manage searching over the list itself.

 

[Alexander Stippler]

You say the user shouldn't know if the container has changed, however
since you expose all the ugliness to him, he does have to know.

It's hard to understand what solution to propose without a better
description of the problem. Why is the user responsible for
iterating some function f() over a list when f() is not under
their control. Possibly this is better solved by passing the
container v (or begin and end iterators) to f() and letting it
manage searching over the list itself.

As an example of my application, let v be an arithmetic sparse vector, where
I only want to store non zero elements. Now I have e.g.
operator-(SparseVector v, double c), which could internally have a loop
using an iterator _it_ to add c to every non-zero-element. Here is the
client code - I do not want to have to consider the possibility of deleting
elements in every function using an iterator.
If c == *_it_, this would result in *_it_ == 0 and thus the current item is
removed. This happens immediately, when assigning *_it_ its new value
(through a proxy).
That's it. How to handle this? I considered not deleting *_it_ immediately,
but then I would have to guess the right time to do it. Is there any
simpler solution than registering iterators with their container?

regards,
alex

 

[Ron Natalie]

That's it. How to handle this? I considered not deleting *_it_ immediately,
but then I would have to guess the right time to do it. Is there any
simpler solution than registering iterators with their container?

My suggestion is that you not use iterators at all. Make a for_each()
like function that transforms the elements, that way it is immune to
the traversal of the container.

If things are going to magically appear and disappear from the container,
best not to expose iterators to the user at all.

 

[Dan W.]

As an example of my application, let v be an arithmetic sparse vector, where
I only want to store non zero elements. Now I have e.g.
operator-(SparseVector v, double c), which could internally have a loop
using an iterator _it_ to add c to every non-zero-element. Here is the
client code - I do not want to have to consider the possibility of deleting
elements in every function using an iterator.
If c == *_it_, this would result in *_it_ == 0 and thus the current item is
removed. This happens immediately, when assigning *_it_ its new value
(through a proxy).
That's it. How to handle this? I considered not deleting *_it_ immediately,
but then I would have to guess the right time to do it. Is there any
simpler solution than registering iterators with their container?

regards,
alex

You mean you are subtracting a number from all these numbers, and
removing them once they become zero? What about if they become
negative? You also say "if( c == *it )" but you cannot compare floats
or doubles for equality like that. And which iterator(s) become(s)
non-valid? You mean that you have multiple iterators in other parts
of the code pointing at elements in this container as you're deleting
elements.

You haven't explained basic things, like, do you need the elements to
be sorted? Random accessible? Find-able in constant time?
There are containers, for instance hash_set and hash_map, which have
the advantage that iterators are not invalidated by insertion or
deletion of elements. Or you could achieve something similar by using
a vector of pointers to heap-allocated objects, then you keep pointers
to particular objects, rather than iterators.

HTH

 

[Howard Hinnant]

Hi,

I've got trouble with some well known issue. Iterator invalidation. My
situation:

for (it=v.begin(); it!=v.end(); ++it) {
f(*it);
}

Under some circumstances, f may alter the container by removing the current
item. Thus the iterator it gets invalid. My question is, if there is a way
to handle this specific case. The problem is that the for loop is user
code, and the user should not even notice that v changed, so I cannot
simply introduce a second iterator inside the for loop. The iterator it
should simply go on iterating with the following item, if *it is deleted.
*it is defininitely the only item which can be deleted by f.
I think this problem is rather general. Are there any threads online on
"robust iterators for c++"? Is there a trick for my situation?

You could use a container that only invalidates the erased element
(list, set, multiset, etc.) and then do something like:

for (it = v.begin(); it != v.end()
f(*it++);

This is effectively:

for (it = v.begin(); it != v.end()
{
It temp = it;
++it;
f(*temp);
}

That is, you increment off of the iterator before it possibly becomes
invalidated.

-Howard

 

[Gianni Mariani]

You could use a container that only invalidates the erased element
(list, set, multiset, etc.) and then do something like:

for (it = v.begin(); it != v.end()
f(*it++);

This is effectively:

for (it = v.begin(); it != v.end()
{
It temp = it;
++it;
f(*temp);
}

That is, you increment off of the iterator before it possibly becomes
invalidated.

This is not a general solution. This assumes that the current object is
the one that gets removed, what if it is the next object instread, what
it there is a cascade effect and all objects in the container get removed ?

I'll give you an example. Consider a list (like this one) that has
"client contexts". Each client may cause a disconnect (destruct) of any
number of other clients on the list. Hence each time you traverse,
every iterator must remain valid. (this is a true-life example BTW).

 

[Jeff Schwab]

Hi,

I've got trouble with some well known issue. Iterator invalidation. My
situation:

for (it=v.begin(); it!=v.end(); ++it) {
f(*it);
}

Under some circumstances, f may alter the container by removing the current
item. Thus the iterator it gets invalid. My question is, if there is a way
to handle this specific case. The problem is that the for loop is user
code, and the user should not even notice that v changed, so I cannot
simply introduce a second iterator inside the for loop. The iterator it
should simply go on iterating with the following item, if *it is deleted.
*it is defininitely the only item which can be deleted by f.
I think this problem is rather general. Are there any threads online on
"robust iterators for c++"? Is there a trick for my situation?

regards,
alex

Write your own "smart iterator" class. Have the constructor and
destructor maintain a static count of existing iterators. Only do the
cleanup of your sparse matrix (removing zero-valued elements, etc.) when
there are no outstanding iterators.

-Jeff

 

[Alexander Stippler]

Thank you for your suggestions. I will investigate the smart iterator
approach a bit further, since all other approaches do not leave things
transparent to the user or at least restrict his possibilities.