stride_view| Document #: | P1899R1 |
| Date: | 2021-11-07 |
| Project: | Programming Language C++ |
| Audience: |
Ranges Study Group, Library Evolution Working Group |
| Reply-to: |
Christopher Di Bella <[email protected]> |
The ability to use algorithms over an evenly-spaced subset of a range has been missed in the STL for a quarter of a century. Given that there’s no way to compose a strided range adaptor in C++20, this should be adopted for C++23.
iterator_concept, and corrects iterator_category so it can’t be contiguous.compute-distace so they pass in size of underlying range instead of themselves.Initial revision.
The ability to use algorithms over an evenly-spaced subset of a range has been missed in the STL for a quarter of a century. This is, in part, due to the complexity required to use an iterator that can safely describe such a range. It also means that the following examples cannot be transformed from raw loops into algorithms, due to a lacking iterator.
namespace stdr = std::ranges;
namespace stdv = std::views;
for (auto i = 0; i < ssize(v); i += 2) {
v[i] = 42; // fill
}
for (auto i = 0; i < ssize(v); i += 3) {
v[i] = f(); // transform
}
for (auto i = 0; i < ssize(v); i += 3) {
for (auto j = i; j < ssize(v); i += 3) {
if (v[j] < v[i]) {
stdr::swap(v[i], v[j]); // selection sort, but hopefully the idea is conveyed
}
}
}Boost.Range 2.0 introduced a range adaptor called strided, and range-v3’s equivalent is stride_view, both of which make striding far easier than when using iterators:
stdr::fill(v | stdv::stride(2), 42);
auto strided_v = v | stdv::stride(3);
stdr::transform(strided_v, stdr::begin(strided_v) f);
stdr::stable_sort(strided_v); // order restored!Given that there’s no way to compose a strided range adaptor in C++20, this should be one of the earliest range adaptors put into C++23.
stride_viewAlthough it isn’t possible to compose stride_view in C++20, someone inexperienced with the ranges design space might mistake filter_view as a suitable way to “compose” stride_view:
auto bad_stride = [](auto const step) {
return views::filter([n = 0, step](auto&&) mutable {
return n++ % step == 0;
});
};This implementation is broken for two reasons:
filter_view expects a predicate as its input, but the lambda we have provided does not model predicate (a call to invoke on a predicate mustn’t modify the function object, yet we clearly are).bidirectional_iterator, it does not model the concept, thus rendering any program containing it ill-formed, with no diagnostic being required.For these reasons, the author regrets not proposing this in the C++20 design space.
Both Boost.Range 2.0 and range-v3 are popular ranges libraries that support a striding range adaptor. The proposed wording has mostly been implemented in cmcstl2 and in a CppCon main session.
Boost.Range 2.0’s strided has a precondition that 0 <= n, but this isn’t strong enough: we need n to be positive.
The stride needs to be positive since a negative stride doesn’t really make sense, and a semantic requirement of std::weakly_incrementable (23.3.4.4
[iterator.concept.winc]) is that incrementing actually moves the iterator to the next element: this means a zero-stride isn’t allowed either.
LEWG unanimously agreed that this was the correct decision in Prague.
A simple implementation of stride_view would be similar to what’s in Boost.Range 2.0: a single-pass range adaptor. With some effort, we can go all the way to a random-access range adaptor, which is what this section mainly covers.
A naive random-access range adaptor would be implemented by simply moving the iterator forward or backward by n positions (where n is the stride length). While this produce a correct iterator when moving forward, its operator-- will be incorrect whenever n doesn’t evenly divide the underlying range’s length. For example:
auto x = std::vector{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
// prints 0 3 6 9
stdr::copy(stdv::stride(x, 3), std::ostream_iterator<int>(std::cout, " "));
// prints 9 6 3 0
stdr::copy(stdv::stride(x, 3) | stdv::reverse, std::ostream_iterator<int>(std::cout, " "));
auto y = std::vector{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
// prints 0 3 6 9
stdr::copy(stdv::stride(y, 3), std::ostream_iterator<int>(std::cout, " "));
// prints 8 5 2: not the same range in reverse!?
stdr::copy(stdv::stride(y, 3) | stdv::reverse, std::ostream_iterator<int>(std::cout, " "));The problem here is that the range has lost all information by the time we’ve reached the end of the sequence. In order to correctly iterate backwards, we need to cache our step value and do some fancy computation:
// `stride_` is the number of elements we're supposed to skip over
// `n` is the number of strides we take
if (moving_forward) {
auto remaining = ranges::advance(current_, n * stride_, ranges::end(underlying_range_));
step_ = stride_ - remaining;
return *this;
}When moving forward, we update our step_ cache. In most cases, this will be zero, since we’ll usually be taking a stride of length stride_. The only case where this step_ is a number is when there are fewer elements left to skip than our stride length. This is important for preserving the range when iterating backward.
if (moving_backward) {
auto stride = step_ == 0 ? n * stride_
: (n + 1) * stride_ - step_;
step_ = ranges::advance(current_, stride, ranges::begin(underlying_range_));
}When we move backward, we consider the value of step_. If it’s zero, then we skip over n * stride_ elements in the same way as moving forward. If step_ is nonzero, then we need to skip over fewer elements in its first step, to make up the distance. In the example above, to print out 9 6 3 0, y’s iterator needs to pretend there’s one extra value between the end of the underlying range and 10 so that the first value of our stdv::stride(y, 3) | stdv::reverse is 9.
<ranges> synopsis [ranges.syn]Add the following to 24.2 [ranges.syn]:
// [...]
namespace std::ranges {
// [...]
// [range.stride]
template<input_range R>
requires view<R>
class stride_view;
template<class R>
inline constexpr bool enable_borrowed_range<stride_view<R>> =
forward_range<R> && enable_borrowed_range<R>;
namespace views { inline constexpr unspecified stride = unspecified; }
// [...]
}Add the contents of this subsection as a subclause to 24.7 [range.adaptors].
1 stride_view presents a view of an underlying sequence, advancing over n elements at a time, as opposed to the usual single-step succession.
2 The name views::stride denotes a range adaptor object 24.7.2
[range.adaptor.object]. Given subexpressions E and N, the expression views::stride(E, N) is expression-equivalent to stride_view(E, N).
3 [Example:
auto input = views::iota(0, 12) | views::stride(3);
ranges::copy(input, ostream_iterator<int>(cout, " ")); // prints 0 3 6 9
ranges::copy(input | views::reverse, ostream_iterator<int>(cout, " ")); // prints 9 6 3 0— end example]
stride_view [range.stride.view]namespace std::ranges {
template<input_range R>
requires view<R>
class stride_view : public view_interface<stride_view<R>> {
template<bool Const> class iterator; // exposition only
public:
stride_view() = default;
constexpr stride_view(R base, range_difference_t<R> stride);
constexpr R base() const& requires copy_constructible<R> { return base_; }
constexpr R base() && { return std::move(base_); }
constexpr range_difference_t<R> stride() const noexcept;
constexpr iterator<false> begin() requires (!simple-view<R>);
constexpr iterator<true> begin() const requires range<const R>;
constexpr auto end() requires (!simple-view<R>) {
if constexpr (!bidirectional_range<R> || (sized_range<R> && common_range<R>)) {
return iterator<false>(*this, ranges::end(base_), ranges::distance(base_) % stride_);
}
else {
return default_sentinel;
}
}
constexpr auto end() const requires range<const R> {
if constexpr (!bidirectional_range<R> || (sized_range<R> && common_range<R>)) {
return iterator<true>(*this, ranges::end(base_), ranges::distance(base_) % stride_);
}
else {
return default_sentinel;
}
}
constexpr auto size() requires (sized_range<R> && !simple-view<R>) {
return compute-distance(ranges::size(base_));
}
constexpr auto size() const requires sized_range<const R> {
return compute-distance(ranges::size(base_));
}
private:
R base_; // exposition only
range_difference_t<R> stride_ = 1; // exposition only
template<class I>
constexpr I compute-distance(I distance) const { // exposition only
const auto quotient = distance / static_cast<I>(stride_);
const auto remainder = distance % static_cast<I>(stride_);
return quotient + static_cast<I>(remainder > 0);
}
};
template<class R>
stride_view(R&&, range_difference_t<R>) -> stride_view<views::all_t<R>>;
}1 Preconditions: stride > 0.
2 Effects: Initializes base_ with base and stride_ with stride.
3 Effects: Equivalent to return base_;
4 Effects: Equivalent to return stride_;
5 Effects: Equivalent to return iterator<false>(*this);
6 Effects: Equivalent to return iterator<true>(*this);
stride_view::iterator [range.stride.iterator]namespace std::ranges {
template<input_range R>
requires view<R>
template<bool Const>
class stride_view<R>::iterator {
using Parent = conditional_t<Const, const stride_view, stride_view>; // exposition only
using Base = conditional_t<Const, const R, R>; // exposition only
friend iterator<!Const>;
Parent* parent_; // exposition only
iterator_t<Base> current_; // exposition only
range_difference_t<Base> step_; // exposition only
public:
using difference_type = range_difference_t<Base>;
using value_type = range_value_t<Base>;
using iterator_concept = see below;
using iterator_category = see below; // not always present
iterator() = default;
constexpr explicit iterator(Parent& parent);
constexpr iterator(Parent& parent, iterator_t<Base> end, difference_type step);
constexpr explicit iterator(iterator<!Const> other)
requires Const && convertible_to<iterator_t<R>, iterator_t<Base>>;
constexpr iterator_t<Base> base() const;
constexpr decltype(auto) operator*() const { return *current_; }
constexpr iterator& operator++();
constexpr void operator++(int);
constexpr iterator operator++(int) requires forward_range<Base>;
constexpr iterator& operator--() requires bidirectional_range<Base>;
constexpr iterator operator--(int) requires bidirectional_range<Base>;
constexpr iterator& operator+=(difference_type n) requires random_access_range<Base>;
constexpr iterator& operator-=(difference_type n) requires random_access_range<Base>;
constexpr decltype(auto) operator[](difference_type n) const
requires random_access_range<Base>
{ return *(*this + n); }
constexpr iterator& operator+(const iterator& x, difference_type n)
requires random_access_range<Base>;
constexpr iterator& operator+(difference_type n, const iterator& x)
requires random_access_range<Base>;
constexpr iterator& operator-(const iterator& x, difference_type n)
requires random_access_range<Base>;
constexpr difference_type operator-(const iterator& x, const iterator& y)
requires random_access_range<Base>;
constexpr friend bool operator==(const iterator& x, default_sentinel);
constexpr friend bool operator==(const iterator& x, const iterator& y)
requires equality_comparable<iterator_t<Base>>;
constexpr friend bool operator<(const iterator& x, const iterator& y)
requires random_access_range<Base>;
constexpr friend bool operator>(const iterator& x, const iterator& y)
requires random_access_range<Base>;
constexpr friend bool operator<=(const iterator& x, const iterator& y)
requires random_access_range<Base>;
constexpr friend bool operator>=(const iterator& x, const iterator& y)
requires random_access_range<Base>;
constexpr friend compare_three_way_result_t<iterator_t<Base>>
operator<=>(const iterator& x, const iterator& y)
requires random_access_range<Base> && three_way_comparable<iterator_t<Base>>;
constexpr friend range_rvalue_reference_t<R> iter_move(const iterator& i)
noexcept(noexcept(ranges::iter_move(i.current_)));
constexpr friend void iter_swap(const iterator& x, const iterator& y)
noexcept(noexcept(ranges::iter_swap(x.current_, y.current_)))
requires indirectly_swappable<iterator_t<R>>;
private:
constexpr iterator& advance(difference_type n) { // exposition only
if constexpr (!bidirectional_range<Parent>) {
ranges::advance(current_, n * parent_->stride_, ranges::end(parent_->base_));
return *this;
}
else {
if (n > 0) {
auto remaining = ranges::advance(current_, n * parent_->stride_, ranges::end(parent_->base_));
step_ = parent_->stride_ - remaining;
return *this;
}
if (n < 0) {
auto stride = step_ == 0 ? n * parent_->stride_
: (n + 1) * parent_->stride_ - step_;
ranges::advance(current_, stride);
stride_ = 0;
return *this;
}
return *this;
}
}
};
}1 iterator::iterator_concept is defined as follows:
(1.1) If R models random_access_range, then iterator_concept denotes random_access_iterator_tag.
(1.2) Otherwise, if R models bidirectional_range, then iterator_concept denotes bidirectional_iterator_tag.
(1.3) Otherwise, if R models forward_range, then iterator_concept denotes forward_iterator_tag.
(1.3) Otherwise, iterator_concept denotes input_iterator_tag.
2 The member typedef-name iterator_category is defined if and only if R models forward_range. In that case, iterator::iterator_category is defined as follows:
(2.1) Let C denote the type iterator_traits<iterator_t<R>>::iterator_category.
(2.2) If C models derived_from<random_access_iterator_tag>, then iterator_category denotes random_access_iterator_tag.
(2.3) Otherwise, iterator_category denotes C.
3 Effects: Initializes parent_ with addressof(parent) and current_ with ranges::begin(parent).
4 Effects: Initializes parent_ with addressof(parent) and current_ with std::move(end), and step_ with step.
constexpr explicit iterator(iterator<!Const> other)
requires Const && convertible_to<iterator_t<R>, iterator_t<Base>>;5 Effects: Initializes parent_ with other.parent_ and current_ with std::move(other.current_), and step_ with other.step_.
6 Effects: Equivalent to: return advance(1);
7 Effects: Equivalent to: advance(1);
8 Effects: Equivalent to:
9 Effects: Equivalent to: return advance(-1);
10 Effects: Equivalent to: return advance(n);
11 Effects: Equivalent to: return advance(-n);
12 Effects: Equivalent to: return x += n;
13 Effects: Equivalent to: return x += n;
constexpr iterator& operator-(const iterator& x, difference_type n)
requires random_access_range<Base>;14 Effects: Equivalent to: return x -= n;
constexpr difference_type operator-(const iterator& x, const iterator& y)
requires random_access_range<Base>;15 Effects: Equivalent to: return x.parent_->compute-distance(x.current_ - y.current_);
16 Effects: Equivalent to: return x.current_ == ranges::end(x.parent_->base_);
constexpr friend bool operator==(const iterator& x, const iterator& y)
requires equality_comparable<iterator_t<Base>>;16 Effects: Equivalent to: return x.current_ == y.current_;
constexpr friend bool operator<(const iterator& x, const iterator& y)
requires random_access_range<Base>;17 Effects: Equivalent to: return x.current_ < y.current_;
constexpr friend bool operator>(const iterator& x, const iterator& y)
requires random_access_range<Base>;18 Effects: Equivalent to: return y < x;
constexpr friend bool operator<=(const iterator& x, const iterator& y)
requires random_access_range<Base>;19 Effects: Equivalent to: return !(y < x);
constexpr friend bool operator>=(const iterator& x, const iterator& y)
requires random_access_range<Base>;20 Effects: Equivalent to: return !(x < y);
constexpr friend compare_three_way_result_t<iterator_t<Base>>
operator<=>(const iterator& x, const iterator& y)
requires random_access_range<Base> && three_way_comparable<iterator_t<Base>>;21 Effects: Equivalent to: return x.current_ <=> y.current_;
constexpr friend range_rvalue_reference_t<R> iter_move(const iterator& i)
noexcept(noexcept(ranges::iter_move(i.current_)));22 Effects: Equivalent to: return ranges::iter_move(i);
constexpr friend void iter_swap(const iterator& x, const iterator& x)
noexcept(noexcept(ranges::iter_swap(x.current_, y.current_)))
requires indirectly_swappable<iterator_t<R>>;23 Effects: Equivalent to: ranges::iter_swap(x.current_, y.current_);
Add the following macro definition to 17.3.2
[version.syn], header <version> synopsis, with the value selected by the editor to reflect the date of adoption of this paper:
The author would like to thank Tristan Brindle for providing editorial commentary on P1899, and also those who reviewed material for, or attended the aforementioned CppCon session or post-conference class, for their input on the design of the proposed stride_view.