2963. Algorithms with underspecified iterator requirements

Section: 26 [algorithms], 29 [numerics] Status: New Submitter: Gašper Ažman Opened: 2017-05-10 Last modified: 2017-07-12

Priority: 3

View other active issues in [algorithms].

View all other issues in [algorithms].

View all issues with New status.

Discussion:

While researching whether the proposed resolution of Iterators of Containers of move-only types do not model InputIterator (LWG 2962), I came across several algorithms that underspecify their requirements, mostly with regard to some associated type of the iterator type they operate on. A list can be found below.

The list of algorithms with underspecified requirements from <algorithm> and <numeric> follows.

With the advent of concepts, these algorithms will need better specifications if we are ever hoping to be allowed to overload based on them. I want this issue to bring the standard algorithms closer to having their concept requirements directly transcribable to library annotations.

Suggested resolution:

  1. copy, copy_if, copy_n, copy_backward

    Add to description: *result shall be assignable from *first.

  2. move, move_backward

    Add to description: *result shall be move-assignable from *first.

  3. transform

    Add to description: The result of the expression op(*first) or binary_op(*first1, *first2) shall be writable to result.

  4. rotate_copy

    Add to description: *first shall be writable to result.

  5. merge

    Add to description: *first1 and *first2 shall be writable to result..

  6. set_union, set_intersection, set_difference, set_symmetric_difference

    Add to description: *first1 and *first2 shall be writable to result.

  7. partial_sum

    acc is not defined.

    Change description: acc, a variable of InputIterator's value type, shall be constructible

  8. adjacent_difference

    acc is not defined.

    Change description: acc, a variable of InputIterator's value type, shall be MoveAssignable and shall be constructible from the type of *first.

  9. iota

    iota is mis-specified. Since the expression we need to support is *first = value: *first is required to be of type InputIterator::reference, and value is an lvalue of type T. The current specification allows calling iota with a const output iterator!

    T shall be convertible to ForwardIterator's value typevalue shall be writable to first. The expression *first = value shall not modify value.

[2017-07 Toronto Monday issue prioritization]

Priority 3; Marshall to work with Gaspar to improve wording.

Proposed resolution: