[boost] Re: iterator adaptors and const correctness

From: David Abrahams (dave_at_[hidden])
Date: 2004-11-11 10:05:08

"Neal D. Becker" <nbecker_at_[hidden]> writes:

> I was struggling with const correctness and iterator adaptors.  At
> first I was using iterator_facade.  I found it difficult to get
> dereference to work correctly.  

What were you trying to do and what was the problem?

> After changing to iterator_adaptor I got things working.  I'm
> wondering if the approach I used is "correct".
>
> I include the whole class here, because it isn't really very big.
>
> I was using a Ring class which contains an iterator, which is
> cycle_iterator<std::vector<Complex>::iterator>.
>
> If a Ring const& is passed 

Passed to what, as which argument?

> I had problems with dereference.
>
> The changes I made to cycle_iterator fix this were:
>
> 1) Add templated conversion constructor to cycle_iterator, to allow
> implicit conversion of cycle_iterator -> const cycle_iterator.

Okay.

> 2) Include both 
>
> reference dereference()
>
> and
>
> const reference dereference() const

That seems very wrong.  Generally an iterator's constness should not
affect what you get when you dereference it, and a reference type is
never changed by adding "const" to it.

> (likewise for operator[])

likewise.

> So, do my changes constitute a "correct" approach to making interoperable 
> iterators using boost::iterator_adaptor?

Did you read
http://www.boost.org/libs/iterator/doc/iterator_facade.html#a-constant-node-iterator
and
http://www.boost.org/libs/iterator/doc/iterator_facade.html#interoperability
?

>
> #ifndef cycle_iterator_H
> #define cycle_iterator_H
>
> #include <boost/iterator/iterator_adaptor.hpp>
> #include <iterator>
>
> namespace boost {
>
>   //! This is a cycle iterator that does keep track of wraparound.
>   template<typename BaseIterator, typename offset_t>
>   class cycle_iterator : public boost::iterator_adaptor<cycle_iterator<BaseIterator, offset_t>,
> 							BaseIterator
> 						       >
>   {
>   public:
>     typedef typename boost::iterator_adaptor<cycle_iterator<BaseIterator, offset_t>,
> 					     BaseIterator
> 					    > super_t;
>
>     typedef typename super_t::difference_type difference_type;
>     typedef typename super_t::value_type value_type;

You don't need the above typedef

>     typedef typename super_t::reference reference;
>
>     explicit cycle_iterator() {}
>
>     explicit cycle_iterator (BaseIterator const& _b, BaseIterator const& _e, offset_t offset=0) :
>       base(_b), size (_e-_b) {

If you want to support forward/bidirectional iterators you might want
to use distance instead of operator-

>       SetPos (offset);
>     }
>
>     template <typename OtherBase>
>     cycle_iterator (cycle_iterator<OtherBase,offset_t> const& other) :
>       base (other.base),
>       size (other.size),
>       position (other.position),
>       wrap (other.wrap)
>     {}
>
>   private:
>     friend class boost::iterator_core_access;
>   
>
>     void increment () {
>       ++position;
>       if (position >= size) {
> 	++wrap;

Tabs don't travel well ;-)

> 	position -= size;
>       }
>     }
>
>     void decrement () {
>       --position;
>       if (position < 0) {
> 	--wrap;
> 	position += size;
>       }
>     }
>
>     void SetPos (offset_t newpos) {
>       position = newpos % size;
>       wrap = newpos / size;
>       if (position < 0) {
> 	--wrap;
> 	position += size;
>       }
>     }
>
>     void advance (difference_type n) {
>       offset_t newpos = realposition() + n;
>       SetPos (newpos);
>     }
>
>     difference_type
>     distance_to (cycle_iterator<BaseIterator, offset_t> const& y)
>     const {

If you really want interop., you should templatize this one so you
can compare const/non-const cycle iterators.

>       if (size == 0)
> 	return 0;
>
>       else {
> 	offset_t pos1 = realposition();
> 	offset_t pos2 = y.realposition();
> 	return -(pos1 - pos2);

Pretty convoluted, but I guess that's okay.  pos2-pos1 would be simpler.
>       }
>     }
>
>     bool equal (cycle_iterator<BaseIterator, offset_t> const& y)
>     const {

Likewise, you should templatize this one, as described in the tutorial.

>       return distance_to (y) == 0;
>     }
>
>     reference dereference() { return *(base + position); }
>
>     const reference dereference() const { return *(base + position); }
>
>    offset_t PositiveMod (offset_t x) const {
>       offset_t y = x % size;
>       if (y < 0)
> 	y += size;
>       return y;
>     }
>
>   public:
>
>     reference operator[] (difference_type n) { return *(base +
>     PositiveMod (position + n)); }

What's wrong with the operator[] supplied by iterator_adaptor?
>     
>     const reference operator[] (difference_type n) const { return *(base +PositiveMod (position + n)); }
>   
>     offset_t offset() const { return position; }
>
>     offset_t realposition () const {
>       return position + wrap * size;
>     }
>
>
>     //  private:
>
>     BaseIterator base;
>     offset_t size;
>     offset_t position;
>     offset_t wrap;
>   };
>
>   template<typename offset_t, typename BaseIterator>
>   cycle_iterator<BaseIterator, offset_t> make_cycle_iterator(BaseIterator b, BaseIterator e, offset_t offset=0) {
>     return cycle_iterator<BaseIterator, offset_t> (b, e, offset);
>   }
>
>   template<typename BaseIterator>
>   cycle_iterator<BaseIterator, int> make_cycle_iterator(BaseIterator b, BaseIterator e, int offset=0) {
>     return cycle_iterator<BaseIterator, int> (b, e, offset);
>   }
>
> } //namespace boost
>
> #endif
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

-- 
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com