Title
ranges permutation generators discard useful information
Status
ready
Section
[alg.permutation.generators]
Submitter
Casey Carter

Created on 2018-11-26.00:00:00, last changed 2019-02-21.17:23:36.

Messages

Date: 2019-02-21.17:23:36

Proposed resolution:

This wording is relative to N4800.

  1. Modify [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.

  2. Modify [algorithm.syn] as follows:

      // [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<safe_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<safe_iterator_t<R>>
            prev_permutation(R&& r, Comp comp = {}, Proj proj = {});
      }
    }
    
  3. Modify [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<safe_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<safe_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: […]

Date: 2019-02-21.17:23:36

[ 2019-02; Kona Wednesday night issue processing ]

Status to Ready

Date: 2019-02-10.00:00:00
Shouldn't the range overloads for an algorithms return

[ 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.
Date: 2019-02-02.00:00:00

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

Previous resolution [SUPERSEDED]:

  1. Modify [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.

  2. Modify [algorithm.syn] as follows:

      // [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 = {});
      }
    }
    
  3. Modify [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: […]

Date: 2019-01-15.00:00:00

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

During the reflector discussion it had been noticed that an additional update of [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.

Date: 2018-11-26.00:00:00

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.

History
Date User Action Args
2019-02-21 17:23:36adminsetmessages: + msg10321
2019-02-21 17:23:36adminsetstatus: review -> ready
2019-02-11 03:11:50adminsetmessages: + msg10304
2019-02-11 03:11:50adminsetstatus: ready -> review
2019-02-02 20:30:17adminsetmessages: + msg10300
2019-02-02 20:30:17adminsetstatus: new -> ready
2019-01-22 17:38:08adminsetmessages: + msg10295
2018-11-27 00:14:47adminsetmessages: + msg10231
2018-11-26 00:00:00admincreate