[boost] Re: problem with new iterators in 1.31 Release candidate # 2

From: David Abrahams (dave_at_[hidden])
Date: 2004-02-01 12:14:02

Robert, please make a little more effort with your posting to indicate
who's writing, which text you are quoting from another message, and
which you are writing yourself.  If your mailer won't add the leading
">"s manually you can do it with your text editor's search/replace.
That'll save me the trouble of doing it for you and make sure that
everyone can understand your post.

Robert Ramey <ramey_at_[hidden]> writes:

>Dave Abrahams wrote:
>
>> Robert Ramey <ramey_at_[hidden]> writes:
>>
>>> I have a problem with the latest version of the new iterators.
>>> This is illustrated in the following example.
>>>
>>> #include <strstream>
>>> #include <iterator>
>>> #include <boost/iterator/counting_iterator.hpp>
>>>
>>> main(){
>>> 	std::istrstream is("abcdefg");
>>> 	typedef boost::counting_iterator<std::istream_iterator<char> > ci;
>>> 	const ci end = std::istream_iterator<char>();  // note the const !!!
>>
>> I don't see why the const should be relevant.
>
> From looking at the code for counting iterator 

This is your first mistake: don't try to understand what the class is
meant to do by looking at the code.  The documentation is the
reference standard.

> it seems to me that it is implemented for non - random access
> iterators by incrementing one iterator until it equals the other and
> return the number of times the increment occured.  

Yeah, it's a mistake.  It shouldn't use distance, but operator-.
That way neither one of your subtractions would compile.

> (I concede that I've had difficulty following the implementation so
> I could be wrong).  So if one of the iterators is const - that one
> can't be the one that's incremented.

Hah, well it increments a copy of the iterator.  You don't really
want us modifying your iterator out from under you just because you
measured a distance with it, do you?  In that case the distance would
be zero after the call.

>>> 	ci begin = std::istream_iterator<char>(is);
>>
>> Hmm, the implicit conversions from istream_iterator to the
>> counting_iterator above are troubling.  I think those constructors
>> should be explicit.
>
> Hmmm - From looking at the documentation and the code, I get
> absolutly no indication that the counting iterator requires a
> randome access iterator.

It doesn't.

The docs say:

  counting_iterator models
  ------------------------

  Specializations of counting_iterator model Readable Lvalue
  Iterator. In addition, they model the concepts corresponding to the
  iterator tags to which their iterator_category is convertible.

And then you go back and look at the synopsis and find:

  iterator_category is determined according to the following algorithm:

  if (CategoryOrTraversal is not use_default)
      return CategoryOrTraversal
  else if (numeric_limits<Incrementable>::is_specialized)
      return iterator-category(
          random_access_traversal_tag, Incrementable, const Incrementable&)
  else
      return iterator-category(
           iterator_traversal<Incrementable>::type, 
           Incrementable, const Incrementable&)

In your case, you didn't pass a CategoryOrTraversal explicitly, and
since the Incrementable type is not numeric, the last clause gets
used.  iterator-category (follow the link) just preserves the
traversal properties of an iterator, so if the Incrementable type is a
single pass traversal iterator (which yours is), the iterator_category
of the counting iterator will reflect that.

> In fact, looking at the code suggests that there is code especially
> included to handle any forward transversal iterators.  And the first
> invocation below DOES work - I can't believe that's an accident.

It's an accident.

>>> 	unsigned int size;
>>>
>>> 	// the following should fail at compilation ?
>>
>> Why?  OK, maybe it would be better to make it fail because the
>> iterator is not in fact a random-access iterator.
>>
>>> 	// in fact it compiles are returns a value of -7 !!!
>>> 	size = begin - end;
>>>
>>> 	// the following should compile and return a value of 7
>>> 	// in fact, it compiles but goes into an infinite loop
>>> 	size = end - begin;
>>> }
>
> My mistake - I wrongly presumed that only the second iterator would be
> incremented and since its const it should fail.  It looks like the code
> intends to select which iterator to increment depending on const.
> So this first case looks ok to me now.
>
>> I don't see why you think the first should compile but the second
>> should not.  If they're not random-access iterators, it seems to me
>> that there's no reason you should be able to subtract them in any
>> order.  If they were random-access iterators, it would be unreasonable
>> to expect the compiler to detect which one had an earlier position
>> and disallow one subtraction.
>
>> So my position is that both compile (as they should).  The first works
>> as one would expect while the second results in an infinite loop.  I'm
>> sorry but I don't see how this can be correct.

Ideally, neither one would compile.  Single pass traversal iterators
don't provide random access operations like operator-.

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