Re: [boost] New iterator adaptors questions

From: David Abrahams (dave_at_[hidden])
Date: 2003-04-21 10:18:25

[I've cc'd this to the -lib reflector because a post-meeting mailing
will propose these adaptors for the TR and issues of possible defects
in the standard are addressed here]

Vladimir Prus <ghost_at_[hidden]> writes:

> I'm still having problems with using the new iterator adaptors, when
> trying to create input iterator with the help of
> 'iterator_facade'. The complete code is attached. The problems are
> with 'deference' method.
>
> 1. iterator_facade insists on having const 'deference', while it
> seems that input iterators frequently alter internal state during
> dereferencing. What is the rationale for the current behaviour.

Good question.  Well, nothing in the standard says that *a has to work
when a is a constant object, but I think this is a defect in the
standard.  Don't you expect to be able to do:

   if (!v.empty())
   {
      V::value_type x = *v.begin();
   }

OK, you could use v.front().  Instead imagine using std::find to
search over an iterator range with a valid sentinel value at the
one-past-the-end position:

    x = *find(start, finish, whatever);

I think the solution in your case ought to be to make the value
mutable... but see below(**)

> 2. Unless I explicitly specify reference type, iterator_facade will
>    try to use ValueType& as reference type, which is wrong in my case,
>    and, I'd think, for all input iterators. Again, what is the
>    rationale?

An input iterator which is not also a forward iterator can access
lvalues.  It may fail to be a forward iterator by virtue of only being
a single-pass iterator, and the value_type may be expensive or even
impossible to copy.  In fact, we had complaints from someone using the
earlier design because the the dereferencing an input iterator always
copied.

I think for iterator_adaptor we can detect whether or not the
underlying iterator's operator*() returns a value or a reference, and
use that to automatically choose a smarter default for the reference
type of adapted input iterators.  However, we have no clue to go on
with iterator_facade, since there's no underlying iterator.

Do you think making the reference type a value by default for
iterator_facade would be advisable in this case?  It will simplify the
definition of certain input iterators at the cost of complicating the
description of how defaults are determined.  I'm honestly not sure
it's worth it.

(**)In fact, looking at your code, I'm not sure you can do it that
way.  The input iterator requirements say:

+-----------+------------------+------------------------------------------+
| operation | type             | semantics, pre/post-conditions           |
+-----------+------------------+------------------------------------------+
| a == b    |convertible to    | == is an equivalence relation over its   |
|           |bool              |domain.                                   |
|           |                  |                                          |
+-----------+------------------+------------------------------------------+
| *a        | convertible to T | pre: a is dereferenceable.               |
|           |                  | If a==b and (a,b) is in the domain of == |
|           |                  | then *a is equivalent to *b.             |
+-----------+------------------+------------------------------------------+

In your iterator, all iterators that are not exhausted are equal so
when a == b, usually *a != *b.  So you probably need to keep a cached
value of the value_type in the iterator, and that makes returning a
reference from operator* perfectly feasible, even desirable.

Your code, modified so it should work:

  #include <boost/iterator.hpp>
  #include <boost/iterator/iterator_adaptor.hpp>

  #include <iostream>
  #include <sstream>

  class adapted_iterator
    : public boost::iterator_facade< 
        adapted_iterator, const std::string, std::input_iterator_tag>
  {
      typedef boost::iterator_facade<
        adapted_iterator, const std::string, std::input_iterator_tag
      > base;

   public:
      adapted_iterator() : is(0), index(0) {}
      adapted_iterator(std::istream* is) : is(is), index(0) {}

   private:
      friend class boost::iterator_core_access;

      base::reference
      dereference() const
      {
          return cache;
      }

      void increment()
      {
          getline(*is, cache);
          ++index;
      }

      bool equal(const adapted_iterator& another) const
      {
          return exhausted() == another.exhausted() && (
              exhausted()
              || is == another.is && index == another.index
            );
      }

   private:
      bool exhausted() const
      {
          return is == 0 || !*is;
      }

      std::istream* is;
      std::size_t index;
  };

  int main()
  {
      std::stringstream ss("1  \n234\n\n45");

      for(adapted_iterator i(&ss), e; i != e; ++i) 
      {
          std::cout << "'" << *i << "'\n";
      }
      return 0;
  }

Probably this should go in the docs as a case study.

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