[boost] Iterator Adaptors

From: Anthony Williams (anthwil_at_[hidden])
Date: 2002-09-17 03:37:33

My previous mail on the matter appears to have got lost, so I'm trying again.

Using the original generator_iterator adaptor policies, the supplied generator
has to be callable, as the policy object calls the generator in its
constructor, and caches the value. This cache is then updated with the new
value every time the iterator is incremented. In order to implement the
bounded_generator policies, I needed to do away with this restriction --- the
upper bound may not be callable (end() iterators need not be dereferencable),
so I use StrongStorage to provide a possibly-empty cache. This cache is only
updated when the iterator is dereferenced, or when it is incremented having
not been dereferenced (to ensure values can't be skipped). This works fine in
the common usage scenario:

for(;current!=end;++current) do_something_with(*current);

However, copying a non-dereferenced iterator will then yield a pair of
non-dereferenced iterators, and dereferencing either will advance the
sequence, as they use the same generator. This is in common with other input
iterators --- only one (any one) of a set of copies may be used --- so is fine
in general.

The problem comes with how iterator_adaptor implements post-increment --- the
implementation is a simple copy/advance/return copy. This is fine for Forward
Iterators and above, and for bounded_generator iterators that have already
been dereferenced, but if they haven't, then this creates two non-dereferenced
copies of which only one may be used, and then proceeds to use both --- one is
incremented, and the other is returned. The expression *current++ is required
to be valid for Input Iterators, and in this scenario, it will skip values due
to the use of both copies. Note that for Input Iterators, the return value of
post-increment is not constrained, especially so that it may be a proxy to
hold the old _value_ of the iterator, rather than actually being a copy of the
old iterator.

Below is a patch to iterator_adaptors.hpp that makes the return value of
post-increment a proxy that holds the dereferenced value of the iterator
before it was incremented.

Anthony

Index: iterator_adaptors.hpp
===================================================================
RCS file: /cvsroot/boost/boost/boost/iterator_adaptors.hpp,v
retrieving revision 1.68
diff -c -r1.68 iterator_adaptors.hpp
*** iterator_adaptors.hpp	11 Sep 2002 14:46:40 -0000	1.68
--- iterator_adaptors.hpp	17 Sep 2002 08:22:39 -0000
***************
*** 382,387 ****
--- 382,453 ----
        >::type type;
    };
  
+     template<typename value_type>
+     class iterator_return_proxy
+     {
+     private:
+         value_type data;
+     public:
+         iterator_return_proxy(value_type data_):
+             data(data_)
+         {}
+         value_type operator*() const
+         {
+             return data;
+         }
+     };
+ 
+   template <class Iterator>
+   struct post_increment_result_generator
+   {
+       typedef iterator_return_proxy<typename Iterator::value_type> proxy;
+ 
+       enum 
+       {use_proxy=
+           ::boost::is_same<
+             typename ::boost::detail::iterator_traits<Iterator>::iterator_category,
+             std::input_iterator_tag
+        >::value
+       };
+       
+ 
+       typedef typename ::boost::detail::if_true<(use_proxy)>::template
+       then<
+         proxy,
+    // else
+         Iterator
+       >::type type;
+ 
+       struct make_proxy_value
+       {
+           static proxy make_value(Iterator& it)
+           {
+               return proxy(it.policies().dereference(it));
+           }
+       };
+       
+       struct make_self_value
+       {
+           static Iterator make_value(Iterator& it)
+           {
+               return it;
+           }
+       };
+       
+       static type make_value(Iterator& it)
+       {
+           typedef typename ::boost::detail::if_true<(use_proxy)>::template
+               then<
+               make_proxy_value,
+               // else
+               make_self_value
+               >::type helper;
+           return helper::make_value(it);
+           
+       }
+       
+   };
+ 
  
  # if defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) || defined(BOOST_NO_STD_ITERATOR_TRAITS)
  
***************
*** 902,908 ****
          return *this;
      }
  
!     self operator++(int) { self tmp(*this); ++*this; return tmp; }
  
      self& operator--() {
  #if !defined(__MWERKS__) || __MWERKS__ >= 0x2405
--- 968,977 ----
          return *this;
      }
  
!     
!     typename detail::post_increment_result_generator<self>::type operator++(int) { 
!         typename detail::post_increment_result_generator<self>::type tmp(detail::post_increment_result_generator<self>::make_value(*this));
!         ++*this; return tmp; }
  
      self& operator--() {
  #if !defined(__MWERKS__) || __MWERKS__ >= 0x2405