ranges::iota
, ranges::shift_left
, and ranges::shift_right
Document #: | P2440R0 |
Date: | 2021-09-12 |
Project: | Programming Language C++ |
Audience: |
LEWG |
Reply-to: |
Tim Song <t.canens.cpp@gmail.com> |
This paper proposes adding the algorithms ranges::iota
, ranges::shift_left
, and ranges::shift_right
, to match their std
counterparts.
ranges::iota
As [P2214R0] explains, while conceptification of other numeric algorithms is a far more complex endeavor (see, e.g., [P1813R0]), iota
is straightforward:
We already have
views::iota
in C++20, which importantly means that we already have all the correct constraints in place. In that sense, it almost takes less time to adoptranges::iota
than it would take to discuss whether or not it’s worth spending time adopting it.
The ranges::iota
algorithm isn’t redundant to views::iota
either: the algorithm determines the number of values to write based on the output range, while using ranges::copy
or similar algorithms with views::iota
requires that information to be computed upfront. When you already have a range, ranges::iota
can be more convenient and efficient.
Following the law of useful returns, this paper proposes returning both the end of the range and the final value.
ranges::shift_left
and ranges::shift_right
These were proposed in [P1243R3] but removed in Prague due to concerns about the return type of shift_left
losing information about the original end of the range. There were particularly concerns about difficulty in recovering the original end if sentinels are involved, since the elements between the end of the new range and the previous end could have been moved from.
However, this argument overlooks the fact that:
end()
and advance it by the shift amount n
to obtain the original end. This is a potentially linear time operation, but it is not impossible to recover the information.n
is not possible, but in this case the algorithm may not necessarily have computed the end iterator of the original range: all it needs is the size, which can be computed from last - first
if their types model sized_sentinel_for
, or from the range if its type models sized_range
. Additionally, we guarantee that in this case the range is unchanged, so the sentinel remains usable.Moreover, the standard library already provides a view factory for users who want to iterate [new_last, last)
: views::counted
. In some cases, using counted_iterator
might even be more efficient by reducing iterator comparisons to integer comparisons (comparing counted_iterator
s only need to compare the counter).
Meanwhile, just returning a subrange
that represents the new range of elements instead of a more complex, bespoke type that users need to decompose themselves is substantially more convenient, and it is hardly unprecedented for some algorithms to not return the end of the range despite necessarily computing it (e.g., ranges::count
, ranges::min/max/minmax_element
), and here we don’t even necessarily compute it. It also allows shift_left
and shift_right
to have the same return type, without having to complicate the latter.
This paper therefore proposes maintaining the [P1243R3] design: ranges::shift_left
and ranges::shift_right
should return a subrange
that represents the new range after the shift.
ranges::iota
<numeric>
synopsis, as indicated:namespace std { + namespace ranges { + // 25.5 [algorithms.results], algorithm result types + + template<class O, class T> + struct out_value_result; + } // [...] // 25.10.13 [numeric.iota], iota template<class ForwardIterator, class T> constexpr void iota(ForwardIterator first, ForwardIterator last, T value); + namespace ranges { + template<class O, class T> + using iota_result = out_value_result<O, T>; + + template<input_or_output_iterator O, sentinel_for<O> S, weakly_incrementable T> + requires indirectly_writable<O, const T&> + constexpr iota_result<O, T> iota(O first, S last, T value); + + template<weakly_incrementable T, output_range<const T&> R> + constexpr iota_result<borrowed_iterator_t<R>, T> iota(R&& r, T value); + } // [...] }
namespace std::ranges { // ... template<class O, class T> struct out_value_result { [[no_unique_address]] O out; [[no_unique_address]] T value; template<class O2, class T2> requires convertible_to<const O&, O2> && convertible_to<const T&, T2> constexpr operator out_value_result<T2, O2>() const & { return {out, value}; } template<class O2, class T2> requires convertible_to<O, O2> && convertible_to<T, T2> constexpr operator out_value_result<T2, O2>() && { return {std::move(out), std::move(value)}; } };
template<input_or_output_iterator O, sentinel_for<O> S, weakly_incrementable T> requires indirectly_writable<O, const T&> constexpr ranges::iota_result<O, T> ranges::iota(O first, S last, T value); template<weakly_incrementable T, output_range<const T&> R> constexpr ranges::iota_result<borrowed_iterator_t<R>, T> ranges::iota(R&& r, T value);
? Effects: Equivalent to: [ Drafting note: Matching range-v3, we write
as_const(value)
to the output to enforce thatvalue
should not be modified by the writing operation. ]
<version>
synopsis, with the value selected by the editor to reflect the date of adoption of this proposal:ranges::shift_left
and ranges::shift_right
<algorithm>
synopsis, as indicated:namespace std { // [...] // 25.7.14 [alg.shift], shift template<class ForwardIterator> constexpr ForwardIterator shift_left(ForwardIterator first, ForwardIterator last, typename iterator_traits<ForwardIterator>::difference_type n); template<class ExecutionPolicy, class ForwardIterator> ForwardIterator shift_left(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last, typename iterator_traits<ForwardIterator>::difference_type n); + namespace ranges { + template<permutable I, sentinel_for<I> S> + constexpr subrange<I> shift_left(I first, S last, iter_difference_t<I> n); + template<forward_range R> + requires permutable<iterator_t<R>> + constexpr borrowed_subrange_t<R> shift_left(R&& r, range_difference_t<R> n); + } template<class ForwardIterator> constexpr ForwardIterator shift_right(ForwardIterator first, ForwardIterator last, typename iterator_traits<ForwardIterator>::difference_type n); template<class ExecutionPolicy, class ForwardIterator> ForwardIterator shift_right(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last, typename iterator_traits<ForwardIterator>::difference_type n); + namespace ranges { + template<permutable I, sentinel_for<I> S> + constexpr subrange<I> shift_right(I first, S last, iter_difference_t<I> n); + template<forward_range R> + requires permutable<iterator_t<R>> + constexpr borrowed_subrange_t<R> shift_right(R&& r, range_difference_t<R> n); + } // [...] }
template<class ForwardIterator> constexpr ForwardIterator shift_left(ForwardIterator first, ForwardIterator last, typename iterator_traits<ForwardIterator>::difference_type n); template<class ExecutionPolicy, class ForwardIterator> ForwardIterator shift_left(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, typename iterator_traits<ForwardIterator>::difference_type n); + +template<permutable I, sentinel_for<I> S> + constexpr subrange<I> ranges::shift_left(I first, S last, iter_difference_t<I> n); +template<forward_range R> + requires permutable<iterator_t<R>> + constexpr borrowed_subrange_t<R> ranges::shift_left(R&& r, range_difference_t<R> n);
1 Preconditions:
n >= 0
istrue
. For the overloads in namespacestd
, tThe type of*first
meets the Cpp17MoveAssignable requirements.2 Effects: If
n == 0
orn >= last - first
, does nothing. Otherwise, moves the element from positionfirst + n + i
into positionfirst + i
for each non-negative integeri < (last - first) - n
. For the overloads without anExecutionPolicy
template parameterIn the first overload case, does so in order starting fromi = 0
and proceeding toi = (last - first) - n - 1
.3 Returns: Let NEW_LAST be
first + (last - first - n)
ifn < last - first
, otherwisefirst
.4 Complexity: At most
(last - first) - n
assignments.template<class ForwardIterator> constexpr ForwardIterator shift_right(ForwardIterator first, ForwardIterator last, typename iterator_traits<ForwardIterator>::difference_type n); template<class ExecutionPolicy, class ForwardIterator> ForwardIterator shift_right(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, typename iterator_traits<ForwardIterator>::difference_type n); + +template<permutable I, sentinel_for<I> S> + constexpr subrange<I> ranges::shift_right(I first, S last, iter_difference_t<I> n); +template<forward_range R> + requires permutable<iterator_t<R>> + constexpr borrowed_subrange_t<R> ranges::shift_right(R&& r, range_difference_t<R> n);
5 Preconditions:
n >= 0
istrue
. For the overloads in namespacestd
, tThe type of*first
meets the Cpp17MoveAssignable requirements, and.ForwardIterator
meets the Cpp17BidirectionalIterator requirements (23.3.5.6 [bidirectional.iterators]) or the Cpp17ValueSwappable requirements.6 Effects: If
n == 0
orn >= last - first
, does nothing. Otherwise, moves the element from positionfirst + i
into positionfirst + n + i
for each non-negative integeri < (last - first) - n
. In the first overload case, ifForwardIterator
meets the Cpp17BidirectionalIterator requirements, dDoes so in order starting fromi = (last - first) - n - 1
and proceeding toi = 0
if:.7 Returns: Let NEW_FIRST be
first + n
ifn < last - first
, otherwiselast
.8 Complexity: At most
(last - first) - n
assignments or swaps.
__cpp_lib_shift
in 17.3.2 [version.syn] to reflect the date of adoption of this proposal.[P1243R3] Dan Raviv. 2020-01-09. Rangify New Algorithms.
https://wg21.link/p1243r3
[P1813R0] Christopher Di Bella. 2019-08-02. A Concept Design for the Numeric Algorithms.
https://wg21.link/p1813r0
[P2214R0] Barry Revzin, Conor Hoekstra, Tim Song. 2020-10-15. A Plan for C++23 Ranges.
https://wg21.link/p2214r0