[boost] Re: live_ptr => live_container / live_iterator

From: Valentin Bonnard (Bonnard.V_at_[hidden])
Date: 1999-08-17 08:34:10

Andy Glew wrote:

> > Well, as we have been discussing, you can either wrap up all the
> > containers, or write just one wrapper for any iterator.  I'll add
> > the latter to my to-do list for weak_ptr.
> 
> The latter - writing one wrapper good for any method that returns
> an iterator - is what I would like, and what I do not know how to do.

A priori, writing a skiping iterator seems trivial:

template <typename It, typename Predicate>
class SkipingIterator {
    mutable It pos;
    Predicate pred;

    void skip () const
    { while (pred (*pos)) ++pos; }

public:
    value_type& operator* () const
    { skip (); return *pos; }

    void operator++ ()
    { skip(); ++pos; }
};

Except that the semantic near the end is ugly (the precondition 
is that there are non skiped elements before the end).

In general, implementing == in a resonnable way is impossible 
w/o a random access iterator as It.

Since iterators give no way to test for end, writing iterator 
wrappers doesn't feel right.

The only solution to this dilemma is make iterators know the 
end:

...
    It last;

    void skip () const
    { while (pos != last && pred (*pos)) ++pos; }

    bool operator== (const SkipingIterator& rhs) const
    { skip(); rhs.skip(); return pos == rhs.pos; }

The strange result is that the iterator knows its 
end, but there is no standard way to test it. So 
a warper arround SkipingIterator, for example 
SkipingIterator, would still need to store two 
SkipingIterators.

The other solution is to invent Smart Iterators with 
an avail() member function to test for end:

template <typename SmrtIt, typename Predicate>
class SkipingIterator {
    mutable SmrtIt pos;
    Predicate pred;

    void skip () const
    { while (pos.avail() && pred (*pos)) ++pos; }

public:
    value_type& operator* () const
    { skip (); return *pos; }

    void operator++ ()
    { skip(); ++pos; }

    bool operator== (const SkipingIterator& rhs) const
    { skip(); rhs.skip(); return pos == rhs.pos; }

    bool avail () const
    { skip(); return pos.avail (); }
};

What about: avail_next (), avail_previous (), avail_next (int), 
avail_previous (int)

or incrementable(), decrementable ()

or dereferencable()

With such iterators, algorithms would take only 
one iterator instead of ranges:

template <class SmrtInputIterator, typename OutputIterator>
OutputIterator smrt_copy (SmrtInputIterator, OutputIterator);

template <class SmrtInputIterator, typename OutputIterator, typename
Predicate>
OutputIterator smrt_transform (SmrtInputIterator, OutputIterator,
Predicate);

This would really change the look and feel of the STL.

-- 
Valentin Bonnard