Re: [boost] [algorithm] adjacent_for_each interest?

Subject: Re: [boost] [algorithm] adjacent_for_each interest?
From: Dave Abrahams (dave_at_[hidden])
Date: 2013-02-10 18:09:38

on Sun Feb 10 2013, Evgeny Panasyuk <evgeny.panasyuk-AT-gmail.com> wrote:

> 10.02.2013 17:10, Ian Hobson:
>
>> Is there any interest in a version of for_each that operates on each
>> adjacent pair of elements in a range?
> [...]
>> Initial implementation available at http://github.com/irh/adjacent_for_each
>
> I have implemented for_each_adjacent on project I worked on (sorry,
> can't share source).
> I had two versions: for InputIterator and ForwardIterator. Selection
> was implemented as tag dispatching of iterator_category.
>
> You need special version for InputIterator which maintains temporary
> copy of value_type, due to 24.1.1/3:
>
> [Note: For input iterators, a == b does not imply ++a ==
> ++b. (Equality does not guarantee the substitution property or
> referential transparency.) Algorithms on input iterators should never
> attempt to pass through the same iterator twice. They should be single
> pass algorithms.]
>
> In this regard your version at
> https://github.com/irh/adjacent_for_each/blob/master/boost/algorithm/adjacent_for_each.hpp
> is broken.
> Because it advertises to work on InputIterator, but it dereferences
> iterator at same position several times. As the result current
> implementation is for ForwardIterator.

That's incorrect.  The mental model for InputIterator is an ephemeral
input stream *with a one-element backing buffer*.  You are allowed to
dereference the same InputIterator multiple times at the same position
until that iterator or a copy of it is incremented.

Table 107 spells this out:

+---------------+----------------+------------+-------------------------------+
|Expression     |Return Type     |Operational |  Assertion/note               |
|               |                |Semantics   |pre-/post-condition            |
+===============+================+============+===============================+
|*a             |convertible to T|            |pre: a is dereferenceable.     |
|               |                |            |**The expression (void)*a, *a  |
|               |                |            |is equivalent to *a.**         |
|               |                |            |(emphasis mine).               |
+---------------+----------------+------------+-------------------------------+

-- 
Dave Abrahams