2074. Off by one error in std::reverse_copy

Section: 26.7.10 [alg.reverse] Status: C++14 Submitter: Peter Miller Opened: 2011-08-17 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [alg.reverse].

View all issues with C++14 status.

Discussion:

The output of the program below should be:

"three two one null \n"

But when std::reverse_copy is implemented as described in N3291 26.7.10 [alg.reverse] it's:

"null three two one \n"

because there's an off by one error in 26.7.10 [alg.reverse]/4; the definition should read:

*(result + (last - first) - 1 - i) = *(first + i)

Test program:

#include <algorithm>
#include <iostream>

template <typename BiIterator, typename OutIterator>
auto
reverse_copy_as_described_in_N3291(
  BiIterator first, BiIterator last, OutIterator result )
-> OutIterator
{
  // 25.3.10/4 [alg.reverse]:
  // "...such that for any non-negative integer i < (last - first)..."
  for ( unsigned i = 0; i < ( last - first ); ++i )
    // "...the following assignment takes place:"
    *(result + (last - first) - i) = *(first + i);

  // 25.3.10/6
  return result + (last - first);
}

int main()
{
  using std::begin;
  using std::end;
  using std::cout;

  static const char*const in[3]  { "one", "two", "three" };
  const char*             out[4] { "null", "null", "null", "null" };

  reverse_copy_as_described_in_N3291( begin( in ), end( in ), out );

  for ( auto s : out )
    cout << s << ' ';

  cout << std::endl;

  return 0;
}

[2012, Kona]

Move to Ready.

[2012, Portland: applied to WP]

Proposed resolution:

This wording is relative to the FDIS.

Change 26.7.10 [alg.reverse] p4 as follows:

template<class BidirectionalIterator, class OutputIterator>
  OutputIterator
    reverse_copy(BidirectionalIterator first,
                 BidirectionalIterator last, OutputIterator result);

-4- Effects: Copies the range [first,last) to the range [result,result+(last-first)) such that for any non-negative integer i < (last - first) the following assignment takes place: *(result + (last - first) - 1 - i) = *(first + i).

-5- Requires: The ranges [first,last) and [result,result+(last-first)) shall not overlap.

-6- Returns: result + (last - first).

-7- Complexity: Exactly last - first assignments.