Re: [Boost-users] A forward iterator need not be default-constructible

Subject: Re: [Boost-users] A forward iterator need not be default-constructible
From: Dave Abrahams (dave_at_[hidden])
Date: 2011-10-02 14:46:36

on Sun Oct 02 2011, Krzysztof Żelechowski <giecrilj-AT-stegny.2a.pl> wrote:

> Dave Abrahams wrote:
>
>> 
>> on Sat Oct 01 2011, Krzysztof Żelechowski <giecrilj-AT-stegny.2a.pl>
>> wrote:
>> 
>>> What I am saying is that iterators that are not default-constructible are
>>> sometimes more robust because an attempt to create them out of thin air
>>> results in a compile-time error.
>> 
>> Yes... except that they are not iterators.
>
> Let’s call them concrete quasi-iterators then.  It is less important how you 
> call them than what you can do with them.
>
>> 
>>> I am not saying that all iterators are like that (I agree with Dave
>>> regarding his the interpretation of NULL).  Moreover, such iterators
>>> sometimes come up naturally from standard components (and not some
>>> shady third-party ones, as has been suggested), as evidenced in my
>>> code that fails to compile with Boost concepts.
>> 
>> Sorry, which code was that?
>
> In the opening post.

*rewinds to opening post*

Lack of documentation aside, what's the underlying problem there?  Oh,
the result of bind1st is not default-constructible?  Well, that's what
you get for using deprecated components ;-)

More seriously... I understand the problem.  What's obnoxious is that
the standard doesn't have a consistent view of the importance of Regular
Types (c.f. Stepanov).  Those binders are not Regular since they don't
have a default-constructor... well, neither are many iterators because
they don't all have a total ordering, but I think the notion of Regular
may have been expanded since '98... but anyway, yeah, let's just say the
standard's inconsistent view of default construction causes an
interoperability problem.

For the record, I'm torn about the whole "Regular Types" thing.  I can
see the argument for it, but it also forces weaker invariants.

Now, I *think* what you want is for the Range library to "degrade
gracefully" when you don't satisfy its concept requirements, and the
appropriate thing to do there is shut off concept checking.  If the
Range library were to put its "concept checking stamp of approval" on a
nonconforming iterator it would be failing to provide an assurance I
want: that the resulting iterator can be used with *any* algorithm
requiring iterators.  If I can get an error later by passing the
resulting iterator to some algorithm that happens to use default
construction, then I have a right to complain that concept checking is
broken.

>>> Being a singular iterator is not a concept, it is a run-time property.
>>> The compiler cannot check whether an operator is singular,
>>> it is equivalent to the halting problem.
>> 
>> It can't check whether an iterator is random-access either.  All (good)
>> concepts have semantic constraints that can't be checked by the
>> compiler.
>
> An algorithm using a bidirectional iterator for a random-access iterator 
> will still work, only it will take longer to accomplish.  

No.  A bidirectional iterator can provide different semantics (or invoke
undefined behavior) for random-access iterator operations that are not
part of the bidirectional iterator concept.

> Also, being a singular iterator is independent of type, while being a 
> random-access iterator is determined by type.

No again.  Objects of this type are not singular iterators:

   struct nonsingular
   {
    private:
        void operator=(nonsingular const&);
   };

Singular values crop up in all kinds of contexts, BTW.  Do ints support
division?  Well, yes, unless the denominator is zero.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com