Re: [Boost-users] [iterator] reverse_iterator from iterators that return references to data in self.

From: David Abrahams (dave_at_[hidden])
Date: 2006-07-15 10:16:07

"Seb Martel" <smartel_at_[hidden]> writes:

> Hello,
>
> given something like:
>  
> class ProxyIterator
>     : public boost::iterator_facade<ProxyIterator, Costly, boost::random_access_traversal_tag>
> {
> public:
>     ProxyIterator(FactoryOfCostly* pF, int i ) : m_pFactory( pF ), m_index( i )
>     {}
> private:
>     friend class boost::iterator_core_access;
>     void decrement() {--m_index;}
>     // ... and others
>
>     Costly& dereference() const
>     {   
>         m_value = m_pFactory->MakeCostlyAtIndex( m_index );
>         return m_value;
>     }
> private:
>     FactoryOfCostly* m_pFactory;
>     int m_index;
>     mutable Costly m_value;
> };

You might need to do something to prevent this from being reported as
a valid random access (or even forward) iterator.  24.1.3:

  --- If a and b are both dereferenceable, then a == b if and only if *a
      and *b are the same object. 

> I cannot use this ProxyIterator with a boost::reverse_iterator adaptor because the implementation of reverse_iterator's dereference dereferences a temporary:
>  
> // from reverse_iterator.hpp
> typename super_t::reference dereference() const { return *boost::prior(this->base()); }

> and in ProxyIterator, this dereference returns a reference to an
> internal member, m_value, that will immediately vanish out of
> existence. Bummer.

Yeah, bummer!

reverse_iterator is designed to be a better version of
std::reverse_iterator, but it does not solve this problem.

> What if reverse_iterator carried as member the decremented iterator
> instead of decrementing to a temporary on a dereference? 

The problem then is that it either becomes less efficient, or
impossible to represent an end reverse iterator, because you can't
necessarily decrement the underly iterator you're passed:

         vector<int> v;
         make_reverse_iterator( v.begin() );  // undefined behavior

> In the current reverse_iterator implementation, decrement must
> behave properly on an end iterator, but not on a begin iterator. Can
> a begin iterator be decremented and still used for comparison
> purposes?

No.

You could build a reverse_iterator like the one you propose by storing
the inner iterator within a boost::optional wrapper, and only
initializing it upon dereference.

HTH,

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com