robust iterator implementation

[Martin Smith]

Hi,

Does anyone know a good (c++)example of the implementation of a
"robust" list iterator (ie an iterator whereby insert/delete
operations does not have any effect on the list)?

I am looking for an implementation that does not make copies of the list.

thanks in advance,

martin

[Dave Moore]

"Martin Smith" <ms****@hotmail .com> wrote in message
news:ct******** **@news2.solcon .nl...

Hi,

Does anyone know a good (c++)example of the implementation of a
"robust" list iterator (ie an iterator whereby insert/delete
operations does not have any effect on the list)?
??? I don't understand ... insert and delete operations will always have "an
effect" on the list, namely, they will add or remove elements. What else
would they do? Perhaps if you give a few more details it would be easier to
understand what you want to do ...
I am looking for an implementation that does not make copies of the list.

Why would an iterator make a copy of the list? I can see why it might store
a reference to the list ...

Dave Moore

[Martin Smith]

O.k sorry for being a bit short.
I am currently implementing the iterator design pattern, from
the book "design patterns" (gamma etc). In the implementation
section for this pattern, it is mentioned that there are many
ways to implement a so called "robust iterator". This iterator
works correct even if delete and insert operators are applied
to the aggregate. Since there are many ways one could implement
this, I was wondering if anyone knows of a good example
for this problem.

kind regards,
martin.

"Dave Moore" <dt*****@email. unc.edu> wrote in message
news:35******** *****@individua l.net...

"Martin Smith" <ms****@hotmail .com> wrote in message
news:ct******** **@news2.solcon .nl...

Hi,

Does anyone know a good (c++)example of the implementation of a
"robust" list iterator (ie an iterator whereby insert/delete
operations does not have any effect on the list)?
??? I don't understand ... insert and delete operations will always have

"an effect" on the list, namely, they will add or remove elements. What else
would they do? Perhaps if you give a few more details it would be easier to understand what you want to do ...

I am looking for an implementation that does not make copies of the

list.
Why would an iterator make a copy of the list? I can see why it might store a reference to the list ...

Dave Moore

[Clark S. Cox III]

On 2005-01-24 07:44:16 -0500, "Martin Smith" <ms****@hotmail .com> said:

O.k sorry for being a bit short.
I am currently implementing the iterator design pattern, from
the book "design patterns" (gamma etc). In the implementation
section for this pattern, it is mentioned that there are many
ways to implement a so called "robust iterator". This iterator
works correct even if delete and insert operators are applied
to the aggregate. Since there are many ways one could implement
this, I was wondering if anyone knows of a good example
for this problem.

If I understand you correctly, one way that one could implement such an
iterator for a vector-like container is to have the iterator class
contain a pointer to the container, and an index. Then, in the
appropriate functions (operator*, operator[], operator->, etc.) simply
call through to Container::oper ator[], like so:

MyIterator::val ue_type &
MyIterator::ope rator*()
{
return (*m_container)[m_index];
}

.... and have the pointer-arithmatic-like operators (operator++,
operator--, operator +=, etc.) operate on the stored index, like so:

MyIterator &
MyIterator::ope rator++()
{
++m_index;
return *this;
}

[msalters]

Martin Smith wrote:

O.k sorry for being a bit short.
I am currently implementing the iterator design pattern, from
the book "design patterns" (gamma etc). In the implementation
section for this pattern, it is mentioned that there are many
ways to implement a so called "robust iterator". This iterator
works correct even if delete and insert operators are applied
to the aggregate. Since there are many ways one could implement
this, I was wondering if anyone knows of a good example
for this problem.

Even this is a bit on the vague side. The std::list has iterators
which are robust, in the sense that insert never affects such
iterators, and deletion affects only iterators refering to the
deleted item.
Now, it is possible to define an even more robust form of
list iterators, such that deletion of a node will also safely
invalidate the iterators to that node. This requires
registration of the iterators with the node (registration
with the list itself makes deletion O(N) ).
With this registration, it also is possible to invalidate
iterators when the entire list is deleted. This adds yet more
overhead (primarily time, can reuse the per-node data).

Another aspect of robustness is how dereferencing an invalid
iterator fails. The standard makes this UB, but a robust
iterator would probably throw an exception. Other
implementations exist, e.g. an iterator whose value_type
is double may return NaN instead. There may even be situations
in which it makes sense to return iterator::value _type();
Regards,
Michiel Salters