[boost] Re: iterator adaptors and const correctness

From: Neal D. Becker (ndbecker2_at_[hidden])
Date: 2004-11-11 14:10:42

First I want to say, publicly, thank you for all your help.

David Abrahams wrote:

> "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

Sorry, I forget the details now, it was something like this.  Initially I
tried to use iterator_facade.
Let me try to give a shortened version.  Suppose 

template<typename T>
struct Ring {
  cycle_iterator<std::vector<T>::iterator> it;
};

Then

template<typename cont_t>
F (cont_t const& r) {
  
In F we now use the values in r, which will try to dereference the iterator
it, and I got (cryptic) errors.  Then I tried to use iterator_adaptor
instead (after all, this really is an iterator adaptor), and had better
luck.

[...]

>>     reference operator[] (difference_type n) { return *(base +
>>     PositiveMod (position + n)); }
> 
> What's wrong with the operator[] supplied by iterator_adaptor?
[...]

I believe in my case there was a difference in efficiency, which is critical
in my app.  Computing a new iterator required recalculating "wrap", while
just using operator[] does not require the extra step.

I have made all the changes you suggested and everything seems to be working
fine.  The updated version is enclosed.
,----[ /disk1/nbecker/shannon2/src/cycle_iterator.hpp ]
| #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::reference reference;
| 
|     explicit cycle_iterator() {}
| 
|     explicit cycle_iterator (BaseIterator const& _b, BaseIterator const&
|     _e, offset_t offset=0) :
|       base(_b), size (std::distance (_b, _e)) {
|       SetPos (offset);
|     }
| 
|     template <typename OtherBase>
|     cycle_iterator (cycle_iterator<OtherBase,offset_t> const& other,
| typename enable_if_convertible<OtherBase, BaseIterator>::type* = 0) :
|       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;
| 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);
|     }
| 
|     template<typename OtherBase>
|     difference_type
|     distance_to (cycle_iterator<OtherBase, offset_t> const& y) const {
|       if (size == 0)
| return 0;
| 
|       else {
| offset_t pos1 = realposition();
| offset_t pos2 = y.realposition();
| return -(pos1 - pos2);
|       }
|     }
| 
|     template<typename OtherBase>
|     bool equal (cycle_iterator<OtherBase, offset_t> const& y) const {
|       return distance_to (y) == 0;
|     }
| 
|     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) 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
`----