robust iterator implementation

Discussion in 'C++' started by Martin Smith, Jan 24, 2005.

  1. Martin Smith

    Martin Smith Guest

    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
    Martin Smith, Jan 24, 2005
    #1
    1. Advertising

  2. Martin Smith

    Dave Moore Guest

    "Martin Smith" <> wrote in message
    news:ct2j3u$nua$...
    > 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
    Dave Moore, Jan 24, 2005
    #2
    1. Advertising

  3. Martin Smith

    Martin Smith Guest

    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" <> wrote in message
    news:...
    >
    > "Martin Smith" <> wrote in message
    > news:ct2j3u$nua$...
    > > 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, Jan 24, 2005
    #3
  4. On 2005-01-24 07:44:16 -0500, "Martin Smith" <> 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::eek:perator[], like so:

    MyIterator::value_type &
    MyIterator::eek:perator*()
    {
    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::eek:perator++()
    {
    ++m_index;
    return *this;
    }
    Clark S. Cox III, Jan 24, 2005
    #4
  5. Martin Smith

    msalters Guest

    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
    msalters, Jan 25, 2005
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Hendrik Maryns
    Replies:
    18
    Views:
    1,419
  2. greg
    Replies:
    6
    Views:
    454
    Dietmar Kuehl
    Jul 17, 2003
  3. Replies:
    6
    Views:
    643
    Jim Langston
    Oct 30, 2005
  4. Replies:
    1
    Views:
    394
    mlimber
    Nov 17, 2005
  5. Simon Strandgaard
    Replies:
    2
    Views:
    159
    Simon Strandgaard
    Oct 4, 2003
Loading...

Share This Page