Re: [boost] Dereferencing End Iterators (Was: Performance Tuning?)

Subject: Re: [boost] Dereferencing End Iterators (Was: Performance Tuning?)
From: Stewart, Robert (Robert.Stewart_at_[hidden])
Date: 2009-07-22 11:23:52

Edward Grace wrote:
>
> Dear Robert,
>
> >> My second gripe is that even the idea of undefined behaviour is
> >> inconsistent (in MSVC at least).  I can quite happily iterate
> >> something to .end() (one past the last element) but not to
> >> .end()+n --- why?
> >
> > Because dereferencing an end iterator has undefined behavior.
>
> The above was a slip of the finger.  I agree with you regarding
> the .end() + n.   I should have based it on .begin() which was the
> original source of my iteration.
>
> A concrete example of what I'm talking about is here:
>
>    http://tinyurl.com/ns8j83

   typedef std::vector<int> vector;
   vector v(3);

> I assert that the problem is that the bounds checking in MSVC is
> wrong - it should only be checking for the de-referencing of invalid
> iterators not their creation.

It is not valid according to the standard.  The operational equivalent for v.begin() + n, in Table 76 (random access iterator requirements) is:

   vector::iterator tmp(v.begin());
   tmp += n;

The operational semantics for tmp += n, same table, is:

   iterator_traits<vector::iterator>::difference_type m(n);
   if (m >= 0) while (m--) ++tmp;
   else while (m++) --tmp;

Finally, the precondition for ++tmp, from Table 74 (forward iterator requirements), and for --tmp, from Table 75 (bidirectional iterator requirements), requires that tmp be dereferenceable.

Once n >= v.size(), the resulting iterator is no longer dereferenceable and the MSVC checking is valid.

> >>  From what I can see this prevents the simple creation of a
> >> striding iterator, for which the .end() can be at .end() +
> >> stride of the underlying vector.  One can do it easily by
> >> default in g++ as it doesn't hold your hand (exposing you to
> >> dereferincing this as being undefined) and leaving that up to
> >> you. In MSVC8 it will barf since the debug bounds checking
> >> doesn't allow you to keep iterating past the end.
> >
> > The debug bounds checking is revealing that you are relying on
> > undefined behavior.
>
> I may be in practice - but I don't think I am in principle.

You are.

> Ultimately are random access iterators *supposed* to be homeomorphic
> to the integers in the same (apparent) way C indices are?

There are additional preconditions for the iterators.

_____
Rob Stewart                           robert.stewart_at_[hidden]
Software Engineer, Core Software      using std::disclaimer;
Susquehanna International Group, LLP  http://www.sig.com

IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.