This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of C++20 status.

### 3169. `ranges` permutation generators discard useful information

Section: 25.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 25.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]:

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

> 2. Modify 25.4 [algorithm.syn] as follows:

>    >       // 25.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 = {});
>    >       }
>    >     }

> 3. Modify 25.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.

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

2. Modify 25.4 [algorithm.syn] as follows:

   >       // 25.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<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 25.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<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: […]