Re: [gtkmm] TreeIter: const_iterator and reverse iterator

[Carl Nygard <cjnygard fast net>]

On Mon, 2004-02-02 at 12:18, Murray Cumming wrote:
> A TreeModel::const_iterator would be like a TreeModel::iterator (a
> TreeIter) which returns a const TreeRow* instead of a TreeRow* from
> operator*().
> 
> So how could we implement this?
> a) Derive the const_iterator from the iterator or vice-versa.
> b) Make the iterator a template, which can use TreeRow or const TreeRow.
> 
> But I'd also like to implement a reverse_iterator. That would be like a
> normal iterator, but operator++() would go backwards instead of
> forwards. And there would probably be a const reverse_iterator too.
> Advice is welcome.

If your container is simple, you might be able to define iterators using
the templates in bits/stl_iterator.h

If you have to do anything complicated to keep track of element
position, then you have to write your own.  I've found that if you try
to derive one from another, you get some bad interactions, or you run
into const-ness problems, or template binding problems with stl
algorithms.

After doing this a few times, I've generally settled on going about it
like so:

// Keep track of positioning in container
class iterator_base {
public:
    iterator_base(/* info for position */);

    bool operator==(const iterator_base& src) const;
    bool operator!=(const iterator_base& src) const;
protected:
    void _Incr(int offset = 1);
    void _Decr(int offset = 1);

    // Member data for position record keeping
};

// main iterator, take care of access and operator++/--/etc...
class const_iterator : public iterator_base {
    // Make sure you define these, otherwise you can't use
    // iterators in stl algorithms
    typedef std::bidirectional_iterator_tag iterator_category;
    typedef <YOUR_TYPE_HERE> value_type;
    typedef const value_type& reference;
    typedef const value_type* pointer;
    typedef std::ptrdiff_t difference_type;

    // These all just call _Incr() or _Decr()
    const_iterator operator++();
    const_iterator operator++(int);
    const_iterator operator--();
    const_iterator operator--(int);
    const_iterator operator+(int offset);
    const_iterator operator-(int offset);
    const_iterator operator+=(int offset);
    const_iterator operator-=(int offset);

    reference operator*() const;
    pointer operator->() const;

};

// Similar versions for iterator, reverse_iterator,
const_reverse_iterator.

Then in your container class, you define:

iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;

reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
// etc...

The other possibly sticky issue is defining what the end() iterator will
look like.  Associated with that is what operator==() looks like, but
that's driven by what info you need to track container element position.

Writing the iterators isn't hard, but the sad part is that it seems best
to duplicate the code, rather than trying to derive too much from other
iterator types.  I can't recall the specifics, but you start to see the
problems with template resolution when using the stl algorithms.

Aha, I remember now.  You can't derive iterator from const_iterator and
expect to reuse the operator+/+=/++/etc functions because they return
const_iterators.  So you wind up writing all the functions anyway, so
you might as well be clearer writing each separately.

Templatizing the iterator/const_iterator is of course a good option.  My
example was not templated, because it was iterating over compressed
float data which required different return values for operator*() [float
for const, proxy_object-with-operator=(float) for non-const].  YMMV

Regards,
Carl