Re: [boost] Re: Advice on using iterator_adaptor

From: Thomas Witt (witt_at_[hidden])
Date: 2003-09-29 12:23:50

Hi Keith,

Keith MacDonald wrote:
> Hi Thomas,
> 
> My real task is to iterate through a memory mapped file.  The constraint on
> Win32 is that MapViewOfFile is limited to a window no larger than the
> maximum contiguous area of virtual memory.  Therefore, the iterator will be
> more complicated than a simple char*, but I decided to start with that, to
> find out how iterator_adaptor worked.

Ok.

> 
> You said "First rule of iterators: Don't derive from an iterator", and I'm
> certainly looking for advice, but P.J. Plauger's library always derives
> iterator from const_iterator, which is itself derived from a base class.

The long version of the rule is: "Don't derive from an iterator, unless 
you really know what you are doing". Unless you are a std library 
implementor, or you are an iterator expert chances are good you don't. 
The thing is that people often use derivation to adapt an iterator. Like 
adding a different ctor or changing the return value. This problem is 
that this solution often seems to work fine, but certainly leads to 
problems in the long run. These problems are caused by the "false" 
return types for operator++ and the like. I got caught by this as I 
started to work with iterators and I've seen a lot of people fall into 
the same trap.

So you can derive from an iterator, if you reimplement all the iterators 
that return the iterator itself. I only had a brief look at the vc7.1 
headers but IIUC this is what Dinkumware does. In most cases this 
counters the very reason why derivation was done in the first place, to 
reuse the base iterator interface.

That's why I do believe the mentioned rule is generally correct.

> If
> someone can spell out exactly how iterator_adaptor should be used for
> creating iterators in new container classes, I'm sure I'll not be the only
> one to benefit.

I'll try to explain where the boost iterator library fits into this 
picture. The boost iterator library aka iterator adaptor provides 
facilities to ease the implementation of new iterators and the adaption 
of existing ones.

If you need to create a new iterator that's state is not already an 
iterator or is sufficiently iterator like iterator_facade is the way to 
go. iterator_facade provides the full blown iterator interfaces, taking 
care of all the nitty gritty details. iterator_facade forwards all calls 
to the iterator interface to up to six core operations that need to be 
implemented in the user's class. The actual number of core operations 
needed depends on the iterator category.

Using you unsigned char example (I'll drop the unsigned), 
iterator_facade usage will look like this.

// untested !!

class iterator;

class const_iterator :
   public iterator_facade<
              const_iterator
            , char const
            , char const&
            , readable_lvalue_iterator_tag
            , random_access_iterator_tag
           >
{
   // This is needed to grant the library access to the
   // private core_interface
   friend class iterator_core_acces;

public:
   const_iterator();
   const_iterator(char const*);

   // iterator -> const_iterator conversion
   // implicit in the derivation solution
   const_iterator(iterator);
private:
   // core iterator interface
   char const& dereference() const
   void increment();
   void decrement();
   bool equal(const_iterator) const;
   void advance(difference_type n);
   difference_type distance_to(const_iterator);
};

iterator_adaptor should be used if the iterator's state is sufficiently 
iterator like. One way to use iterator_adaptor for your example would be 
to create the mutable iterator type from the constant one like this:

class iterator :
   public iterator_adaptor<
              const_iterator,
              char,
              writable_lvalue_iterator_tag,
              char &
           >
{
   typedef iterator_adaptor<
              const_iterator,
              char,
              writable_lvalue_iterator_tag,
              char &
           > super_t;

   friend class iterator_core_access;
public:
   iterator();
   iterator(char* p)
     : super_t(const_iterator(p)
   {}
private:
   char& dereference()
   {
     // this is basically what Dinkumware does
     // It's safe you know it isn't const
     return const_cast<char&>(*base_reference());
   }
};

There might be other ways to achieve the same using the iterator library.

HTH

Thomas