Issue 3169: ranges permutation generators discard useful information

3169. `ranges` permutation generators discard useful information

Section: 26.8.13 [alg.permutation.generators] Status: C++20 Submitter: Casey Carter Opened: 2018-11-26 Last modified: 2021-02-25

Priority: 0

View all issues with C++20 status.

Discussion:

In the Ranges design, algorithms that necessarily traverse an entire range - consequently discovering the end iterator value - return that iterator value unless the algorithm's sole purpose is to return a derived value, for example, ranges::count. ranges::next_permutation and ranges::prev_permutation necessarily traverse the entirety of their range argument, but are currently specified to discard the end iterator value and return only a bool indicating whether they found a next (respectively previous) permutation or "reset" the range to the first (respectively last) permutation. They should instead return an aggregate composed of both that bool and the end iterator value to be consistent with the other range algorithms.

[2019-01-22; Daniel comments and updates wording]

During the reflector discussion it had been noticed that an additional update of 26.2 [algorithms.requirements] p.16 is necessary for the new type next_permutation_result and two missing occurrences of iterator_t<> where added. The proposed wording has been updated.

[2019-02-02 Priority to 0 and Status to Tentatively Ready after five positive votes on the reflector.]

Previous resolution [SUPERSEDED]:

Modify 26.2 [algorithms.requirements] as follows:

-16- The class templates binary_transform_result, for_each_result, minmax_result, mismatch_result, next_permutation_result, copy_result, and partition_copy_result have the template parameters, data members, and special members specified above. They have no base classes or members other than those specified.

Modify 26.4 [algorithm.syn] as follows:

  // 26.8.13 [alg.permutation.generators], permutations
  template<class BidirectionalIterator>
    constexpr bool next_permutation(BidirectionalIterator first,
                                    BidirectionalIterator last);
  template<class BidirectionalIterator, class Compare>
    constexpr bool next_permutation(BidirectionalIterator first,
                                    BidirectionalIterator last, Compare comp);

  namespace ranges {
    template<class I>
    struct next_permutation_result {
      bool found;
      I in;
    };

    template<BidirectionalIterator I, Sentinel<I> S, class Comp = ranges::less<>,
             class Proj = identity>
      requires Sortable<I, Comp, Proj>
      constexpr boolnext_permutation_result<I>
        next_permutation(I first, S last, Comp comp = {}, Proj proj = {});
    template<BidirectionalRange R, class Comp = ranges::less<>,
             class Proj = identity>
      requires Sortable<iterator_t<R>, Comp, Proj>
      constexpr boolnext_permutation_result<iterator_t<R>>
        next_permutation(R&& r, Comp comp = {}, Proj proj = {});
  }

  template<class BidirectionalIterator>
    constexpr bool prev_permutation(BidirectionalIterator first,
                                    BidirectionalIterator last);
  template<class BidirectionalIterator, class Compare>
    constexpr bool prev_permutation(BidirectionalIterator first,
                                    BidirectionalIterator last, Compare comp);

  namespace ranges {
    template<class I>
    using prev_permutation_result = next_permutation_result<I>;

    template<BidirectionalIterator I, Sentinel<I> S, class Comp = ranges::less<>,
             class Proj = identity>
      requires Sortable<I, Comp, Proj>
      constexpr boolprev_permutation_result<I>
        prev_permutation(I first, S last, Comp comp = {}, Proj proj = {});
    template<BidirectionalRange R, class Comp = ranges::less<>,
             class Proj = identity>
      requires Sortable<iterator_t<R>, Comp, Proj>
      constexpr boolprev_permutation_result<iterator_t<R>>
        prev_permutation(R&& r, Comp comp = {}, Proj proj = {});
  }
}

Modify 26.8.13 [alg.permutation.generators] as follows:

template<class BidirectionalIterator>
  constexpr bool next_permutation(BidirectionalIterator first,
                                  BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
  constexpr bool next_permutation(BidirectionalIterator first,
                                  BidirectionalIterator last, Compare comp);

namespace ranges {
  template<BidirectionalIterator I, Sentinel<I> S, class Comp = ranges::less<>,
           class Proj = identity>
    requires Sortable<I, Comp, Proj>
    constexpr boolnext_permutation_result<I>
      next_permutation(I first, S last, Comp comp = {}, Proj proj = {});
  template<BidirectionalRange R, class Comp = ranges::less<>,
           class Proj = identity>
    requires Sortable<iterator_t<R>, Comp, Proj>
    constexpr boolnext_permutation_result<iterator_t<R>>
      next_permutation(R&& r, Comp comp = {}, Proj proj = {});
}

[…]

-4- Returns: Let B be true if ~~and only if~~ a next permutation was found and otherwise false. Returns:

B for the overloads in namespace std, or
{ B, last } for the overloads in namespace ranges.

-5- Complexity: […]

template<class BidirectionalIterator>
  constexpr bool prev_permutation(BidirectionalIterator first,
                                  BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
  constexpr bool prev_permutation(BidirectionalIterator first,
                                  BidirectionalIterator last, Compare comp);

namespace ranges {
  template<BidirectionalIterator I, Sentinel<I> S, class Comp = ranges::less<>,
           class Proj = identity>
    requires Sortable<I, Comp, Proj>
    constexpr boolprev_permutation_result<I>
      prev_permutation(I first, S last, Comp comp = {}, Proj proj = {});
  template<BidirectionalRange R, class Comp = ranges::less<>,
           class Proj = identity>
    requires Sortable<iterator_t<R>, Comp, Proj>
    constexpr boolprev_permutation_result<iterator_t<R>>
      prev_permutation(R&& r, Comp comp = {}, Proj proj = {});
}

[…]

-9- Returns: Let B be true if ~~and only if~~ a previous permutation was found and otherwise false. Returns:

B for the overloads in namespace std, or
{ B, last } for the overloads in namespace ranges.

-10- Complexity: […]

[2019-02-10 Tomasz comments; Casey updates the P/R and resets status to "Review."]

Shouldn't the range overloads for an algorithms return safe_iterator_t<R> instead of iterator_t<R>? Other algorithms are consistently returning the safe_iterator_t/safe_subrange_t in situation, when range argument is an rvalue (temporary) and returned iterator may be dangling.

[2019-02; Kona Wednesday night issue processing]

Status to Ready

Proposed resolution:

This wording is relative to N4800.

Modify 26.2 [algorithms.requirements] as follows:

-16- The class templates binary_transform_result, for_each_result, minmax_result, mismatch_result, next_permutation_result, copy_result, and partition_copy_result have the template parameters, data members, and special members specified above. They have no base classes or members other than those specified.