Re: [Boost-users] Boost Iterator Adaptor, with a mutable member variable is optimized out incorrectly

Subject: Re: [Boost-users] Boost Iterator Adaptor, with a mutable member variable is optimized out incorrectly
From: Nathan Ridge (zeratul976_at_[hidden])
Date: 2013-10-23 18:25:00

Your code invokes undefined behaviour.

boost::copy() will call code like this in a loop:

    *out = *in;

where 'out' is your ostream iterator and 'in' is a 
reverse_iterator<B::const_iterator>.

reverse_iterator, itself implemented using iterator_adaptor,
has an operator* that looks something like this:

    UnderlyingIterator::reference operator*()
    {
        return *boost::prior(base());
    }

where UnderlyingIterator is B::const_iterator, and thus
UnderlyingIterator::reference is 'int const&'.

(The boost::prior() call is necessary because reverse_iterator
uses iterator_adaptor in such a way that the underlying
iterator is one element ahead of the element the
reverse_iterator points to. This way, the reversed range's
begin() can be the underlying range's end() and vice versa.)

Here's the undefined behaviour: boost::prior() returns an
iterator by value, which is a temporary in the context of
the the reverse_iterator::operator* call. When that iterator
is dereferenced in reverse_iterator::operator*,
B::const_iterator::operator* returns a reference to a field
of this temporary iterator. reverse_iterator::operator* in
turn returns this reference.

Now when program execution gets to calling the
assignment operator in

   *out = *in;

the reverse_iterator::operator* has returned, the
temporary B::const_iterator inside it has been destructed,
and the returned reference is now dangling.
ostream_iterator::operator= tries to read from this
dangling reference, and now anything can happen.

Given that you're invoking undefined behaviour, it is
perfectly normal that an unoptimized build works fine
while an optimized build gives incorrect results.

To avoid the undefined behaviour, I would recommend
making B::const_iterator's reference type be 'int const'
(without the reference) - this can be controlled through
the fifth template parameter of iterator_adaptor:

  class const_iterator :
    public boost::iterator_adaptor<const_iterator,
                                   std::vector<int>::const_iterator,
                                   int const,
                                   boost::bidirectional_traversal_tag,
                                   int const> 
  {
     ...
    int const dereference() const {
      return 2 * (*base());
    }
  };

As a general rule, I would avoid writing iterators that
return a reference to something stored locally. If
you're going to be an lvalue iterator (dereference to
a reference), return a reference to something stored
externally, otherwise be an rvalue iterator (dereference
to a value).

Hope that helps.

Regards,
Nate