3197. std::prev should not require BidirectionalIterator

Section: 24.4.3 [iterator.operations] Status: New Submitter: Billy O'Neal III Opened: 2019-04-03 Last modified: 2024-06-18

Priority: 3

View other active issues in [iterator.operations].

View all other issues in [iterator.operations].

View all issues with New status.

Discussion:

MSVC++ (and apparently libc++) have asserts that std::prev only accepts BidirectionalIterators, because it's declared in the standard as accepting only BidirectionalIterator. libc++ changed their tests (in this commit), apparently from a bug report from Ville and Jonathan, saying that one could theoretically call std::prev with a negative number.

The standardese in [iterator.operations] strongly indicates that prev requires a BidirectionalIterator, but I don't see the usual wording that connects template type parameters of that name to the <algorithm> requirements or similar. So perhaps one could argue that the name Bidirectional there has no meaning. Even if that is the case, that's a defect in the other direction.

[2019-06-12 Priority set to 3 after reflector discussion]

[2022-04-22; Jonathan adds a comment]

P2408 changes the requirements for types substituting BidirectionalIterator etc. in the Algorithms clause. We should consider whether that is appropriate here, especially as algorithms might make use of std::prev internally. An algorithm that was changed by P2408 to accept types that model bidirectional_iterator instead of requiring Cpp17BidirectionalIterator might have to stop using std::prev if we don't resolve this issue to allow it.

We should consider whether distance, advance and next need the same treatment.

[2024-06-18; Jonathan adds a comment]

Related to LWG 2353 which made a similar change to std::next. Also, if we require a Cpp17BidirectionalIterator here, then that means you can't use std::prev on a std::bidirectional_iterator unless it also meets the Cpp17BidirectionalIterator requirements. That seems like an unnecessary restriction, since std::prev doesn't do anything that wouldn't work fine with any type that models std::bidirectional_iterator.

Proposed resolution:

This wording is relative to N4810.

[Drafting Note: Three mutually exclusive options are prepared, depicted below by Option A, Option B, and Option C, respectively.]

Option A

  1. NAD, the name BidirectionalIterator actually means that prev requires bidirectional iterators, in which case this change to libcxx is incorrect.

Option B

  1. Modify 24.2 [iterator.synopsis], header <iterator> synopsis, as indicated:

    // 24.4.3 [iterator.operations], iterator operations
[…]
template<class BidirectionalInputIterator>
  constexpr BidirectionalInputIterator prev(BidirectionalInputIterator x,
    typename iterator_traits<BidirectionalInputIterator>::difference_type n = 1);

  2. Modify 24.4.3 [iterator.operations] as indicated:

    template<class BidirectionalInputIterator>
  constexpr BidirectionalInputIterator prev(BidirectionalInputIterator x,
    typename iterator_traits<BidirectionalInputIterator>::difference_type n = 1);

    -7- Effects: Equivalent to: advance(x, -n); return x;

Option C

  1. The intent of the wording is that the template parameters apply requirements, and the defect is that they do not. We should add a requirement in 24.4.3 [iterator.operations]/1 to the effect that the template parameter names impose said requirements.