Re: iterator invalidation trouble

From: Dan W. (danw_at_raytron-controls.com)
Date: 12/29/03 

Date: Mon, 29 Dec 2003 13:52:26 -0500

On Mon, 29 Dec 2003 19:31:48 +0100, Alexander Stippler
<stip@mathematik.uni-ulm.de> wrote:

>Ron Natalie wrote:
>
>>
>> "Alexander Stippler" <stip@mathematik.uni-ulm.de> wrote in message
>> news:3ff061a1@news.uni-ulm.de...
>>> 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.
>
>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

Relevant Pages

  • Re: Under what circumstances can the STL move a vector?
    ... > vector in the first element on the heap is moved, thus invalidating ... Each container has well defined semantics on how and when iterators ... and references into the container become invalidated. ...
    (comp.lang.cpp)
  • Re: Interface of the set classes
    ... > container usually depend on the data set. ... > templates, iterators, probably tags, and on. ... Python has iterators, and doesn't need templates, since signature based ... The equivalent of "specializing a template" ...
    (comp.lang.python)
  • Re: Reinventing the iterator
    ... this environmental benefit from iterators. ... the container once from beginning to end. ... iterator-based algorithms are good for any ... (defmethod find (item (container array)) ...
    (comp.lang.lisp)
  • Re: Seed7 Release 2007-05-07
    ... You do not need iterators ... I am sure it is possible to declare ... Iterators in Seed7. ... I meant different container types. ...
    (comp.lang.misc)
  • Re: iterator invalidation trouble
    ... > You say the user shouldn't know if the container has changed, ... I only want to store non zero elements. ... I considered not deleting *_it_ immediately, ... simpler solution than registering iterators with their container? ...
    (comp.lang.cpp)