[Boost-users] [iterator] Problems with iterator_facade and const-qualification

6 May 2011

      I'm trying to use the iterator_facade and am running into trouble. It's 
not really caused by the iterator_facade, but I figured I'd ask anyway. 
This takes some explanation, so if anyone reads this, know that I *do* 
appreciate it. :-)

TLDR version: I'm getting a compiler error about converting between 
pointers of iterator_facade<> instantiations with different const 
qualifications on the value_type. The code's attached, in addition to 
mostly appearing (with a few minor formatting changes) inline below. 
Please help me figure out what to do to fix it.

What I'm doing is a bit roundabout, but here goes.

One fault with C++ iterators (at least from some point of view) is that 
if you want to operate on different kinds of iterators you have to care 
about too much -- you need to know more than just the type that op* 
returns (which is all you care about most of the time, iterator_traits 
notwithstanding), but what the underlying iterator type is. This means 
that if you want to write code that operates on multiple kinds of 
iterators, it must be a template.

Templates don't suit my needs at this time, so I'm trying to write a 
couple wrapper classes that will do dynamic dispatch to different 
iterator types. Think of this as writing a C++ version of Java's 
Iterator interface.

Thus I define a base class for my iterators:

   template<typename ValueType, typename ReferenceType>
   class iterator_base
     : public iterator_facade<iterator_base<ValueType, ReferenceType>,
                              ValueType,
                              boost::forward_traversal_tag,
                              ReferenceType>
   {
     friend class boost::iterator_core_access;

   protected:
     virtual void increment() = 0;
     virtual ReferenceType dereference() const = 0;
     virtual bool equal(iterator_base const & other) const = 0;

   public:
     virtual iterator_base* clone() const = 0;
   };

(I'm only worrying about forward iterators at this time. I'm also 
ignoring ptrdiff_t) The first three functions are straight from the 
iterator_facade class, and the fourth is your typical clone() method.

Now, I define a template that wraps any iterator that doesn't implement 
my iterator_base; it just stores an instance of the backing iterator 
type and does the corresponding thing (I'm removing some 'typenames' in 
there to avoid line wraps):

   template<typename BackingIter>
   class cplusplus_iterator_adaptor
     : public iterator_base<iterator_traits<BackingIter>::value_type,
                            iterator_traits<BackingIter>::reference>
   {
   private:
     BackingIter backing;

     typedef typename iterator_traits<BackingIter>::value_type ValueType;
     typedef typename iterator_traits<BackingIter>::reference Reference;

   public:
     cplusplus_iterator_adaptor() {}

     cplusplus_iterator_adaptor(cplusplus_iterator_adaptor const & other)
       : backing(other.backing)
     {}

     explicit cplusplus_iterator_adaptor(BackingIter iter)
       : backing(iter)
     {}

     cplusplus_iterator_adaptor* clone() const {
       return new cplusplus_iterator_adaptor(*this);
     }

     // Actual iterator functions
     void increment() {
       ++backing;
     }

     bool equal(iterator_base<ValueType, Reference> const& other) const {
       const cplusplus_iterator_adaptor * p =
         dynamic_cast<cplusplus_iterator_adaptor const*>(&other);
       return p && backing == p->backing;
     }

     Reference dereference() const {
       return *backing;
     }
   };

Okay, now we have something that we can use like
   cplusplus_iterator_adaptor<vector<int>::iterator> my_itr(vec.begin());
   *my_itr;
   ++my_itr;
and it will work the same as vector<int>::iterator, except that you can 
treat it polymorphically from an iterator_base<int> reference or 
pointer, thus freeing you from caring that it wraps a vector iterator 
instead of just caring that it gives you an int&.

There's one problem with this however, which is that if I 
<i>actually</i> want to deal with it polymorphically, I have to use a 
reference or pointer; but (1) this kinda sucks and (2) lots of code is 
written that operates on iterators by value (like, say, the STL).

To solve this problem, I implemented a wrapper class that gives value 
semantics to a iterator_base<> pointer. This wrapper class also 
implements the elements required of the iterator concept, and 
additionally behaves like a cloning smart pointer.

   template<typename ValueType, typename ReferenceType = ValueType &>
   class iterator_base_wrapper
     : public iterator_facade<iterator_base_wrapper<ValueType,
                                                    ReferenceType>,
                              ValueType,
                              boost::forward_traversal_tag,
                              ReferenceType>
   {
   private:
     iterator_base<ValueType, ReferenceType> * backing;

   public:
     iterator_base_wrapper() : backing(0) {}

     iterator_base_wrapper(iterator_base_wrapper const & other)
       : backing(other.backing->clone())
     {}

     explicit iterator_base_wrapper(iterator_base const & base)
       : backing(base.clone())
     {}

   private:
     void swap(iterator_base_wrapper & other) const {
       std::swap(backing, other.backing);
     }

   public:
     iterator_base_wrapper& operator=(iterator_base_wrapper const&other) {
       iterator_base_wrapper copy(other);
       swap(copy);
       return *this;
     }

     ~iterator_base_wrapper() {
       delete backing;
     }

   private:
     friend class boost::iterator_core_access;

     virtual void increment() {
       ++(*backing);
     }

     virtual bool equal(iterator_base_wrapper const & other) const {
       return backing->equal(*other.backing);
     }

     ReferenceType dereference() const {
       return **backing;
     }
   };

OK, goal achieved! Somewhat. It's now possible to use the
iterator_base_wrapper like you would a normal iterator:

   int run()
   {
     const int arr[] = {0,1,2,3,4,5,6,7,8,9,10};
     const int size_arr = sizeof(arr)/sizeof(arr[0]);

     vector<int> v(arr, arr+size_arr);

     cplusplus_iterator_adaptor<vector<int>::iterator> a_beg(v.begin());
     cplusplus_iterator_adaptor<vector<int>::iterator> a_end(v.end());

     iterator_base_wrapper<int> ii(a_beg);
     iterator_base_wrapper<int> ii_end(a_end);

     vector<int>::const_iterator vi = v.begin();
     while(ii != ii_end) {
       assert( *vi == *ii );
       ++vi;
       ++ii;
     }
     assert( vi == v.end() );

     return 0;
   }

(BY the way, I totally intend on writing a couple make_* functions, a
la make_pair.)

OK, but now, what happens if we change things to be const_iterators? I
can still make the cplusplus_iterator_adaptor:
   cplusplus_iterator_adaptor<vector<int>::const_iterator>
       a_beg(v.begin());
But I *can't* make my wrapper, using either
   iterator_base_wrapper<const int, const int &> ii(a_beg);
or
   iterator_base_wrapper<int, const int &> ii(a_begin);
because of this error:
   cannot convert from 'iterator_base<int, const int&>*' to
   'iterator_base<const int, const int&>*'.

The reason for *this* is that the cplusplus_iterator_adaptor uses the
iterator_traits<>::value_type of the underlying iterator -- vector's
const_iterator -- which isn't const-qualified when it subclasses
iterator_facade. This means that the iterator_facade base class in
both cases are different types.

What's the best way to fix this? The best I can come up with is to add
like a clone_const() function that returns a const-qualified version
of the value type. But that seems ugly. Is there something elegant I'm
missing?

Evan Driscoll