views::chunk
and views::slide
Document #: | P2442R1 |
Date: | 2021-12-05 |
Project: | Programming Language C++ |
Audience: |
LWG |
Reply-to: |
Tim Song <t.canens.cpp@gmail.com> |
<ranges>
chunk
chunk_view
for input ranges [range.chunk.view.input]chunk_view::outer-iterator
[range.chunk.outer.iter]chunk_view::outer-iterator::value_type
[range.chunk.outer.value]chunk_view::inner-iterator
[range.chunk.inner.iter]chunk_view
for forward ranges [range.chunk.view.fwd]chunk_view<V>::iterator
for forward ranges [range.chunk.fwd.iter]slide
This paper proposes two range adaptors, views::chunk
and views::slide
, as described in section 3.5 of [P2214R0].
std::vector v = {1, 2, 3, 4, 5};
fmt::print("{}\n", v | std::views::chunk(2)); // [[1, 2], [3, 4], [5]]
fmt::print("{}\n", v | std::views::slide(2)); // [[1, 2], [2, 3], [3, 4], [4, 5]]
Both of these range adaptors are well-known quantities that have been shipped in range-v3 for years and are further discussed in section 3.5 of [P2214R0]. The discussion below assumes familiarity with that paper.
chunk
The basic idea of chunk
is simple: views::chunk(R, N)
divides R
into non-overlapping N-sized chunks, except that the last chunk can be smaller than N
in size. It is a precondition that N
is positive.
Matching the range-v3 implementation, the proposed chunk
supports input ranges, even though the algorithm necessary for such support is significantly different.
In particular, for input ranges, the underlying iterator as well as related iteration state is tracked in the chunk_view
object itself. This means that this chunk_view
can only support non-const
iteration. As a point of departure from range-v3, both outer and inner iterators are move-only input iterators.
Because the inner iterator and outer iterator share state, and moving from the stored underlying iterators can invalidate both iterators, only the non-mutating base() const&
overload is provided for the inner iterator to avoid this sort of spooky-action-at-a-distance invalidation:
auto v = some_input_view | views::chunk(2);
auto outer = v.begin();
auto range = *outer;
range.begin().base(); // if this moved the underlying iterator, outer would be invalidated
Providing base()
for the outer iterator would be misleading as the stored iterator mutates when the inner range is being iterated over.
For input ranges, chunk
has a bespoke value type that is itself an input view. For forward and stronger ranges, chunk
defers to views::take
for its value type.
In range-v3, chunk
is never a common range. chunk
as proposed here is a common range if the underlying range is forward, common, and either sized or non-bidirectional.
For bidirectional and stronger ranges, the need to size the last chunk correctly from the end iterator requires the underlying range to be sized.
As with range-v3, this paper proposes that chunk
is borrowed if the underlying view is forward and borrowed.
For input ranges, chunk_view
stores
current_
); andremainder_
).Incrementing the inner iterator increments current_
and decrements remainder_
, setting it to zero if the end of the chunk is reached.
Incrementing the outer iterator increments current_
remainder_
times so that we start at the next N-element chunk even if the inner view isn’t iterated to end, and then sets remainder_
to the chunk size.
For forward and stronger ranges, chunk_view
’s iterator
stores an exposition-only data member missing_
. This data member can only be nonzero when the iterator is the past-the-end iterator, in which case it represents the difference between N and the size of the last chunk.
slide
views::slide(R, N)
produces a range of ranges such that the M-th range is a view into the M-th through (M+N-1)-th elements of R
. It is similar to views::adjacent
([P2321R2]), except that the size of the window N is provided at runtime. It is a precondition that N is positive.
Unlike chunk
, and similar to adjacent
, slide
does not support input ranges. It might be possible to support a window size of 1 - but then users can just use chunk
instead. Caching elements is not considered a viable approach, essentially for the reasons discussed in section 4.3.4 of [P2321R2].
slide
defers to views::counted
for its value type.
slide
is a common range if the underlying range is (or can be trivially made one), and is a borrowed range if the underlying range is.
There are basically two strategies for slide
. For simplicity the discussion below ignores the case where the number of elements in the source view is less than N
.
slide
can go back N - 1
elements from that iterator to find the first iterator that can’t start a range. In this case, slide
’s iterator need only store the first iterator of the window i
and the window size N
.slide
’s iterator must also store the iterator to the last element in the window (that is, i + (N - 1)
). When that iterator compares equal to the end of the source range, the iterator is past-the-end (since we can no longer produce a range of N
elements).Both chunk
and slide
(under the name sliding
) have been implemented in range-v3, and much of the subtler aspects of the implementation logic in the wording below are taken from there (any errors are mine, of course, though hopefully there isn’t any).
I also have implemented a version that directly follows the proposed wording below without issue.
<ranges>
Add the following to 24.2 [ranges.syn], header <ranges>
synopsis:
// [...]
namespace std::ranges {
// [...]
// [range.chunk], chunk view
template<view V>
requires input_range<V>
class chunk_view;
template<view V>
requires forward_range<V>
class chunk_view<V>;
template<class V>
inline constexpr bool enable_borrowed_range<chunk_view<V>> =
forward_range<V> && enable_borrowed_range<V>;
namespace views {
inline constexpr unspecified chunk = unspecified;
}
// [range.slide], slide view
template<view V>
requires forward_range<V>
class slide_view;
template<class V>
inline constexpr bool enable_borrowed_range<slide_view<V>> =
enable_borrowed_range<V>;
namespace views {
inline constexpr unspecified slide = unspecified;
}
}
chunk
Add the following subclause to 24.7 [range.adaptors].
1 chunk_view
takes a view
and a number N and produces a range of views that are N-sized non-overlapping successive chunks of the elements of the original view, in order. The last view in the range can have fewer than N elements.
2 The name views::chunk
denotes a range adaptor object (24.7.2 [range.adaptor.object]). Given subexpressions E
and N
, the expression views::chunk(E, N)
is expression-equivalent to chunk_view(E, N)
.
vector v = {1, 2, 3, 4, 5};
for (auto r : v | views::chunk(2)) {
cout << '[';
auto sep = "";
for(auto i : r) {
cout << sep << i;
sep = ", ";
}
cout << "] ";
}
// prints: [1, 2] [3, 4] [5]
chunk_view
for input ranges [range.chunk.view.input]namespace std::ranges {
template<class I>
constexpr I div-ceil(I num, I denom) { // exposition only
I r = num / denom;
if (num % denom) {
++r;
}
return r;
}
template<view V>
requires input_range<V>
class chunk_view : public view_interface<chunk_view<V>>{
V base_ = V(); // exposition only
range_difference_t<V> n_ = 0; // exposition only
range_difference_t<V> remainder_ = 0; // exposition only
non-propagating-cache<iterator_t<V>> current_; // exposition only
// [range.chunk.outer.iter], class chunk_view::outer-iterator
class outer-iterator; // exposition only
// [range.chunk.inner.iter], class chunk_view::inner-iterator
class inner-iterator; // exposition only
public:
chunk_view() requires default_initializable<V> = default;
constexpr explicit chunk_view(V base, range_difference_t<V> n);
constexpr V base() const & requires copy_constructible<V> { return base_; }
constexpr V base() && { return std::move(base_); }
constexpr outer-iterator begin();
constexpr default_sentinel_t end() noexcept;
constexpr auto size() requires sized_range<V>;
constexpr auto size() const requires sized_range<const V>;
};
template<class R>
chunk_view(R&& r, range_difference_t<R>) -> chunk_view<views::all_t<R>>;
}
1 Preconditions:
n > 0
istrue
.2 Effects: Initializes
base_
withstd::move(base)
andn_
withn
.
3 Effects: Equivalent to:
4 Returns:
default_sentinel
.
constexpr auto size() requires sized_range<V>;
constexpr auto size() const requires sized_range<const V>;
5 Effects: Equivalent to:
chunk_view::outer-iterator
[range.chunk.outer.iter]namespace std::ranges {
template<view V>
requires input_range<V>
class chunk_view<V>::outer-iterator {
chunk_view* parent_; // exposition only
constexpr explicit outer-iterator(chunk_view& parent); // exposition only
public:
using iterator_concept = input_iterator_tag;
using difference_type = range_difference_t<V>;
// [range.chunk.outer.value], class chunk_view::outer-iterator::value_type
struct value_type;
outer-iterator(outer-iterator&&) = default;
outer-iterator& operator=(outer-iterator&&) = default;
constexpr value_type operator*() const;
constexpr outer-iterator& operator++();
constexpr void operator++(int);
friend constexpr bool operator==(const outer-iterator& x, default_sentinel_t);
friend constexpr difference_type operator-(default_sentinel_t y, const outer-iterator& x)
requires sized_sentinel_for<sentinel_t<V>, iterator_t<V>>;
friend constexpr difference_type operator-(const outer-iterator& x, default_sentinel_t y)
requires sized_sentinel_for<sentinel_t<V>, iterator_t<V>>;
};
}
1 Effects: Initializes
parent_
withaddressof(parent)
.
2 Preconditions:
*this == default_sentinel
isfalse
.3 Returns:
value_type(*parent_)
.
4 Preconditions:
*this == default_sentinel
isfalse
.5 Effects: Equivalent to:
6 Effects: Equivalent to
++*this
.
7 Effects: Equivalent to:
return *x.parent_->current_ == ranges::end(x.parent_->base_) && x.parent_->remainder_ != 0;
friend constexpr difference_type operator-(default_sentinel_t y, const outer-iterator& x)
requires sized_sentinel_for<sentinel_t<V>, iterator_t<V>>;
8 Effects: Equivalent to:
friend constexpr difference_type operator-(const outer-iterator& x, default_sentinel_t y)
requires sized_sentinel_for<sentinel_t<V>, iterator_t<V>>;
9 Effects: Equivalent to:
return -(y - x);
chunk_view::outer-iterator::value_type
[range.chunk.outer.value]namespace std::ranges {
template<view V>
requires input_range<V>
struct chunk_view<V>::outer-iterator::value_type : view_interface<value_type> {
chunk_view* parent_; // exposition only
constexpr explicit value_type(chunk_view& parent); // exposition only
public:
constexpr inner-iterator begin() const noexcept;
constexpr default_sentinel_t end() const noexcept;
constexpr auto size() const
requires sized_sentinel_for<sentinel_t<V>, iterator_t<V>>;
};
}
1 Effects: Initializes
parent_
withaddressof(parent)
.
2 Returns:
inner-iterator(*parent_)
.
3 Returns:
default_sentinel
.
4 Effects: Equivalent to:
return ranges::min(parent_->remainder_, ranges::end(parent_->base_) - *parent_->current_);
chunk_view::inner-iterator
[range.chunk.inner.iter]namespace std::ranges {
template<view V>
requires input_range<V>
class chunk_view<V>::inner-iterator {
chunk_view* parent_; // exposition only
constexpr explicit inner-iterator(chunk_view& parent) noexcept; // exposition only
public:
using iterator_concept = input_iterator_tag;
using difference_type = range_difference_t<V>;
using value_type = range_value_t<V>;
inner-iterator(inner-iterator&&) = default;
inner-iterator& operator=(inner-iterator&&) = default;
constexpr const iterator_t<V>& base() const &;
constexpr range_reference_t<V> operator*() const;
constexpr inner-iterator& operator++();
constexpr void operator++(int);
friend constexpr bool operator==(const inner-iterator& x, default_sentinel_t);
friend constexpr difference_type operator-(default_sentinel_t y, const inner-iterator& x)
requires sized_sentinel_for<sentinel_t<V>, iterator_t<V>>;
friend constexpr difference_type operator-(const inner-iterator& x, default_sentinel_t y)
requires sized_sentinel_for<sentinel_t<V>, iterator_t<V>>;
};
}
1 Effects: Initializes
parent_
withaddressof(parent)
.
2 Effects: Equivalent to:
return *parent_->current_;
3 Preconditions:
*this == default_sentinel
isfalse
.4 Effects: Equivalent to:
return **parent_->current_;
5 Preconditions:
*this == default_sentinel
isfalse
.6 Effects: Equivalent to:
7 Effects: Equivalent to
++*this
.
8 Returns:
x.parent_->remainder_ == 0
.
friend constexpr difference_type operator-(default_sentinel_t y, const inner-iterator& x)
requires sized_sentinel_for<sentinel_t<V>, iterator_t<V>>;
9 Effects: Equivalent to:
return ranges::min(x.parent_->remainder_, ranges::end(x.parent_->base_) - *x.parent_->current_);
friend constexpr difference_type operator-(const inner-iterator& x, default_sentinel_t y)
requires sized_sentinel_for<sentinel_t<V>, iterator_t<V>>;
10 Effects: Equivalent to:
return -(y - x);
chunk_view
for forward ranges [range.chunk.view.fwd]namespace std::ranges {
template<view V>
requires forward_range<V>
class chunk_view<V> : public view_interface<chunk_view<V>> {
V base_ = V(); // exposition only
range_difference_t<V> n_ = 0; // exposition only
template<bool> class iterator; // exposition only
public:
chunk_view() requires default_initializable<V> = default;
constexpr explicit chunk_view(V base, range_difference_t<V> n);
constexpr V base() const & requires copy_constructible<V> { return base_; }
constexpr V base() && { return std::move(base_); }
constexpr auto begin() requires (!simple-view<V>) {
return iterator<false>(this, ranges::begin(base_));
}
constexpr auto begin() const requires forward_range<const V> {
return iterator<true>(this, ranges::begin(base_));
}
constexpr auto end() requires (!simple-view<V>) {
if constexpr (common_range<V> && sized_range<V>) {
auto missing = (n_ - ranges::distance(base_) % n_) % n_;
return iterator<false>(this, ranges::end(base_), missing);
}
else if constexpr (common_range<V> && !bidirectional_range<V>) {
return iterator<false>(this, ranges::end(base_));
}
else {
return default_sentinel;
}
}
constexpr auto end() const requires forward_range<const V> {
if constexpr (common_range<const V> && sized_range<const V>) {
auto missing = (n_ - ranges::distance(base_) % n_) % n_;
return iterator<true>(this, ranges::end(base_), missing);
}
else if constexpr (common_range<const V> && !bidirectional_range<const V>) {
return iterator<true>(this, ranges::end(base_));
}
else {
return default_sentinel;
}
}
constexpr auto size() requires sized_range<V>;
constexpr auto size() const requires sized_range<const V>;
};
}
1 Preconditions:
n > 0
istrue
.2 Effects: Initializes
base_
withstd::move(base)
andn_
withn
.
constexpr auto size() requires sized_range<V>;
constexpr auto size() const requires sized_range<const V>;
3 Effects: Equivalent to:
chunk_view<V>::iterator
for forward ranges [range.chunk.fwd.iter]namespace std::ranges {
template<view V>
requires forward_range<V>
template<bool Const>
class chunk_view<V>::iterator {
using Parent = maybe-const<Const, chunk_view>; // exposition only
using Base = maybe-const<Const, V>; // exposition only
iterator_t<Base> current_ = iterator_t<Base>(); // exposition only
sentinel_t<Base> end_ = sentinel_t<Base>(); // exposition only
range_difference_t<Base> n_ = 0; // exposition only
range_difference_t<Base> missing_ = 0; // exposition only
constexpr iterator(Parent* parent, iterator_t<Base> current, // exposition only
range_difference_t<Base> missing = 0);
public:
using iterator_category = input_iterator_tag;
using iterator_concept = see below;
using value_type = decltype(views::take(subrange(current_, end_), n_));
using difference_type = range_difference_t<Base>;
iterator() = default;
constexpr iterator(iterator<!Const> i)
requires Const && convertible_to<iterator_t<V>, iterator_t<Base>>
&& convertible_to<sentinel_t<V>, sentinel_t<Base>>;
constexpr iterator_t<Base> base() const;
constexpr value_type operator*() const;
constexpr iterator& operator++();
constexpr iterator operator++(int);
constexpr iterator& operator--() requires bidirectional_range<Base>;
constexpr iterator operator--(int) requires bidirectional_range<Base>;
constexpr iterator& operator+=(difference_type x)
requires random_access_range<Base>;
constexpr iterator& operator-=(difference_type x)
requires random_access_range<Base>;
constexpr value_type operator[](difference_type n) const
requires random_access_range<Base>;
friend constexpr bool operator==(const iterator& x, const iterator& y);
friend constexpr bool operator==(const iterator& x, default_sentinel_t);
friend constexpr bool operator<(const iterator& x, const iterator& y)
requires random_access_range<Base>;
friend constexpr bool operator>(const iterator& x, const iterator& y)
requires random_access_range<Base>;
friend constexpr bool operator<=(const iterator& x, const iterator& y)
requires random_access_range<Base>;
friend constexpr bool operator>=(const iterator& x, const iterator& y)
requires random_access_range<Base>;
friend constexpr auto operator<=>(const iterator& x, const iterator& y)
requires random_access_range<Base> &&
three_way_comparable<iterator_t<Base>>;
friend constexpr iterator operator+(const iterator& i, difference_type n)
requires random_access_range<Base>;
friend constexpr iterator operator+(difference_type n, const iterator& i)
requires random_access_range<Base>;
friend constexpr iterator operator-(const iterator& i, difference_type n)
requires random_access_range<Base>;
friend constexpr difference_type operator-(const iterator& x, const iterator& y)
requires sized_sentinel_for<iterator_t<Base>, iterator_t<Base>>;
friend constexpr difference_type operator-(default_sentinel_t y, const iterator& x)
requires sized_sentinel_for<sentinel_t<Base>, iterator_t<Base>>;
friend constexpr difference_type operator-(const iterator& x, default_sentinel_t y)
requires sized_sentinel_for<sentinel_t<Base>, iterator_t<Base>>;
};
}
1 iterator::iterator_concept
is defined as follows:
Base
models random_access_range
, then iterator_concept
denotes random_access_iterator_tag
.Base
models bidirectional_range
, then iterator_concept
denotes bidirectional_iterator_tag
.iterator_concept
denotes forward_iterator_tag
.2 Effects: Initializes
current_
withcurrent
,end_
withranges::end(parent->base_)
,n_
withparent->n_
, andmissing_
withmissing
.
constexpr iterator(iterator<!Const> i)
requires Const && convertible_to<iterator_t<V>, iterator_t<Base>>
&& convertible_to<sentinel_t<V>, sentinel_t<Base>>;
3 Effects: Initializes
current_
withstd::move(i.current_)
,end_
withstd::move(i.end_)
,n_
withi.n_
, andmissing_
withi.missing_
.
4 Returns:
current_
.
5 Preconditions:
current_ != end_
istrue
.6 Returns:
views::take(subrange(current_, end_), n_)
7 Preconditions:
current_ != end_
istrue
.8 Effects: Equivalent to:
9 Effects: Equivalent to:
10 Effects: Equivalent to:
11 Effects: Equivalent to:
12 Preconditions: If
x
is positive,ranges::distance(current_, end_) > n_ * (x - 1)
istrue
. [ Note 1: Ifx
is negative, the Effects: paragraph implies a precondition. — end note ]13 Effects: Equivalent to:
14 Effects: Equivalent to:
return *this += -x;
15 Returns:
*(*this + n)
.
16 Returns:
x.current_ == y.current_
.
17 Returns:
x.current_ == x.end_;
friend constexpr bool operator<(const iterator& x, const iterator& y)
requires random_access_range<Base>;
18 Returns:
x.current_ < y.current_
.
friend constexpr bool operator>(const iterator& x, const iterator& y)
requires random_access_range<Base>;
19 Effects: Equivalent to:
return y < x;
friend constexpr bool operator<=(const iterator& x, const iterator& y)
requires random_access_range<Base>;
20 Effects: Equivalent to:
return !(y < x);
friend constexpr bool operator>=(const iterator& x, const iterator& y)
requires random_access_range<Base>;
21 Effects: Equivalent to:
return !(x < y);
friend constexpr auto operator<=>(const iterator& x, const iterator& y)
requires random_access_range<Base> &&
three_way_comparable<iterator_t<Base>>;
22 Returns:
x.current_ <=> y.current_
.
friend constexpr iterator operator+(const iterator& i, difference_type n)
requires random_access_range<Base>;
friend constexpr iterator operator+(difference_type n, const iterator& i)
requires random_access_range<Base>;
23 Effects: Equivalent to:
friend constexpr iterator operator-(const iterator& i, difference_type n)
requires random_access_range<Base>;
24 Effects: Equivalent to:
friend constexpr difference_type operator-(const iterator& x, const iterator& y)
requires sized_sentinel_for<iterator_t<Base>, iterator_t<Base>>;
25 Returns:
(x.current_ - y.current_ + x.missing_ - y.missing_) / x.n_
.
friend constexpr difference_type operator-(default_sentinel_t y, const iterator& x)
requires sized_sentinel_for<sentinel_t<Base>, iterator_t<Base>>;
26 Returns:
div-ceil(x.end_ - x.current_, x.n_)
.
friend constexpr difference_type operator-(const iterator& x, default_sentinel_t y)
requires sized_sentinel_for<sentinel_t<Base>, iterator_t<Base>>;
27 Effects: Equivalent to:
return -(y - x);
slide
Add the following subclause to 24.7 [range.adaptors].
1 slide_view
takes a view
and a number N and produces a view
whose M th element is a view over the M th through (M + N - 1)th elements of the original view. If the original view has fewer than N elements, the resulting view is empty.
2 The name views::slide
denotes a range adaptor object (24.7.2 [range.adaptor.object]). Given subexpressions E
and N
, the expression views::slide(E, N)
is expression-equivalent to slide_view(E, N)
.
vector v = {1, 2, 3, 4};
for (auto i : v | views::slide(2)) {
cout << '[' << i[0] << ', ' << i[1] << "] "; // prints: [1, 2] [2, 3] [3, 4]
}
slide_view
[range.slide.view]namespace std::ranges {
template<class V>
concept slide-caches-nothing = random_access_range<V> && sized_range<V>; // exposition only
template<class V>
concept slide-caches-last = !slide-caches-nothing<V> && bidirectional_range<V> && common_range<V>; // exposition only
template<class V>
concept slide-caches-first = !slide-caches-nothing<V> && !slide-caches-last<V>; // exposition only
template<forward_range V>
requires view<V>
class slide_view : public view_interface<slide_view<V>>{
V base_ = V(); // exposition only
range_difference_t<V> n_ = 0; // exposition only
template<bool> class iterator; // exposition only
class sentinel; // exposition only
public:
slide_view() requires default_initializable<V> = default;
constexpr explicit slide_view(V base, range_difference_t<V> n);
constexpr auto begin()
requires (!(simple-view<V> && slide-caches-nothing<const V>));
constexpr auto begin() const requires slide-caches-nothing<const V>;
constexpr auto end()
requires (!(simple-view<V> && slide-caches-nothing<const V>));
constexpr auto end() const requires slide-caches-nothing<const V>;
constexpr auto size() requires sized_range<V>;
constexpr auto size() const requires sized_range<const V>;
};
template<class R>
slide_view(R&& r, range_difference_t<R>) -> slide_view<views::all_t<R>>;
}
1 Effects: Initializes
base_
withstd::move(base)
andn_
withn
.
2 Returns:
- (2.1) If
V
modelsslide-caches-first
,iterator<false>(ranges::begin(base_), ranges::next(ranges::begin(base_), n_ - 1, ranges::end(base_)), n_)
.- (2.2) Otherwise,
iterator<false>(ranges::begin(base_), n_)
.3 Remarks: In order to provide the amortized constant-time complexity required by the
range
concept, this function caches the result within theslide_view
for use on subsequent calls whenV
modelsslide-caches-first
.
4 Returns:
iterator<true>(ranges::begin(base_), n_)
.
5 Returns:
- (5.1) If
V
modelsslide-caches-nothing
,iterator<false>(ranges::begin(base_) + range_difference_t<V>(size()), n_)
;- (5.2) Otherwise, if
V
modelsslide-caches-last
,iterator<false>(ranges::prev(ranges::end(base_), n_ - 1, ranges::begin(base_)), n_)
;- (5.3) Otherwise, if
V
modelscommon_range
,iterator<false>(ranges::end(base_), ranges::end(base_), n_)
;- (5.4) Otherwise,
sentinel(ranges::end(base_))
.6 Remarks: In order to provide the amortized constant-time complexity required by the
range
concept, this function caches the result within theslide_view
for use on subsequent calls whenV
modelsslide-caches-last
.
7 Returns:
begin() + range_difference_t<const V>(size())
.
constexpr auto size() requires sized_range<V>;
constexpr auto size() const requires sized_range<const V>;
8 Effects: Equivalent to:
slide_view::iterator
[range.slide.iterator]namespace std::ranges {
template<forward_range V>
requires view<V>
template<bool Const>
class slide_view<V>::iterator {
using Base = maybe-const<Const, V>; // exposition only
iterator_t<Base> current_ = iterator_t<Base>(); // exposition only
iterator_t<Base> last_ele_ = iterator_t<Base>(); // exposition only, present only if Base models slide-caches-first
range_difference_t<Base> n_ = 0; // exposition only
constexpr iterator(iterator_t<Base> current, range_difference_t<Base> n) // exposition only
requires (!slide-caches-first<Base>);
constexpr iterator(iterator_t<Base> current, iterator_t<Base> last_ele, range_difference_t<Base> n) // exposition only
requires slide-caches-first<Base>;
public:
using iterator_category = input_iterator_tag;
using iterator_concept = see below;
using value_type = decltype(views::counted(current_, n_));
using difference_type = range_difference_t<Base>;
iterator() = default;
constexpr iterator(iterator<!Const> i)
requires Const && convertible_to<iterator_t<V>, iterator_t<Base>>;
constexpr auto operator*() const;
constexpr iterator& operator++();
constexpr iterator operator++(int);
constexpr iterator& operator--() requires bidirectional_range<Base>;
constexpr iterator operator--(int) requires bidirectional_range<Base>;
constexpr iterator& operator+=(difference_type x)
requires random_access_range<Base>;
constexpr iterator& operator-=(difference_type x)
requires random_access_range<Base>;
constexpr auto operator[](difference_type n) const
requires random_access_range<Base>;
friend constexpr bool operator==(const iterator& x, const iterator& y);
friend constexpr bool operator<(const iterator& x, const iterator& y)
requires random_access_range<Base>;
friend constexpr bool operator>(const iterator& x, const iterator& y)
requires random_access_range<Base>;
friend constexpr bool operator<=(const iterator& x, const iterator& y)
requires random_access_range<Base>;
friend constexpr bool operator>=(const iterator& x, const iterator& y)
requires random_access_range<Base>;
friend constexpr auto operator<=>(const iterator& x, const iterator& y)
requires random_access_range<Base> &&
three_way_comparable<iterator_t<Base>>;
friend constexpr iterator operator+(const iterator& i, difference_type n)
requires random_access_range<Base>;
friend constexpr iterator operator+(difference_type n, const iterator& i)
requires random_access_range<Base>;
friend constexpr iterator operator-(const iterator& i, difference_type n)
requires random_access_range<Base>;
friend constexpr difference_type operator-(const iterator& x, const iterator& y)
requires sized_sentinel_for<iterator_t<Base>, iterator_t<Base>>;
};
}
1 iterator::iterator_concept
is defined as follows:
Base
models random_access_range
, then iterator_concept
denotes random_access_iterator_tag
.Base
models bidirectional_range
, then iterator_concept
denotes bidirectional_iterator_tag
.iterator_concept
denotes forward_iterator_tag
.2 If the invocation of any non-const member function of iterator
exits via an exception, the iterator acquires a singular value.
constexpr iterator(iterator_t<Base> current, range_difference_t<Base> n)
requires (!slide-caches-first<Base>);
3 Effects: Initializes
current_
withcurrent
andn_
withn
.
constexpr iterator(iterator_t<Base> current, iterator_t<Base> last_ele, range_difference_t<Base> n)
requires slide-caches-first<Base>;
4 Effects: Initializes
current_
withcurrent
,last_ele_
withlast_ele
, andn_
withn
.
constexpr iterator(iterator<!Const> i)
requires Const && (convertible_to<iterator_t<V>, iterator_t<Base>>;
5 Effects: Initializes
current_
withstd::move(i.current_)
andn_
withi.n_
. [ Note 1:iterator<true>
can only be formed whenBase
modelsslide-caches-nothing
, in which caselast_ele_
is not present. — end note ]
6 Returns:
views::counted(current_, n_)
.
7 Preconditions:
current_
andlast_ele_
(if present) are incrementable.8 Postconditions:
current_
andlast_ele_
(if present) are each equal toranges::next(i)
, where i is the value of that data member before the call.9 Returns:
*this
.
10 Effects: Equivalent to:
11 Preconditions:
current_
andlast_ele_
(if present) are decrementable.12 Postconditions:
current_
andlast_ele_
(if present) are each equal toranges::prev(i)
, where i is the value of that data member before the call.13 Returns:
*this
.
14 Effects: Equivalent to:
15 Preconditions:
current_ + x
andlast_ele_ + x
(if present) have well-defined behavior.16 Postconditions:
current_
andlast_ele_
(if present) are each equal toi + x
, where i is the value of that data member before the call.17 Returns:
*this
.
18 Preconditions:
current_ - x
andlast_ele_ - x
(if present) have well-defined behavior.19 Postconditions:
current_
andlast_ele_
(if present) are each equal toi - x
, where i is the value of that data member before the call.20 Returns:
*this
.
21 Effects: Equivalent to:
return views::counted(current_ + n, n_);
22 Returns: If
last_ele_
is present,x.last_ele_ == y.last_ele_
; otherwise,x.current_ == y.current_
.
friend constexpr bool operator<(const iterator& x, const iterator& y)
requires random_access_range<Base>;
23 Returns:
x.current_ < y.current_
.
friend constexpr bool operator>(const iterator& x, const iterator& y)
requires random_access_range<Base>;
24 Effects: Equivalent to:
return y < x;
friend constexpr bool operator<=(const iterator& x, const iterator& y)
requires random_access_range<Base>;
25 Effects: Equivalent to:
return !(y < x);
friend constexpr bool operator>=(const iterator& x, const iterator& y)
requires random_access_range<Base>;
26 Effects: Equivalent to:
return !(x < y);
friend constexpr auto operator<=>(const iterator& x, const iterator& y)
requires random_access_range<Base> &&
three_way_comparable<iterator_t<Base>>;
27 Returns:
x.current_ <=> y.current_
.
friend constexpr iterator operator+(const iterator& i, difference_type n)
requires random_access_range<Base>;
friend constexpr iterator operator+(difference_type n, const iterator& i)
requires random_access_range<Base>;
28 Effects: Equivalent to:
friend constexpr iterator operator-(const iterator& i, difference_type n)
requires random_access_range<Base>;
29 Effects: Equivalent to:
friend constexpr difference_type operator-(const iterator& x, const iterator& y)
requires sized_sentinel_for<iterator_t<Base>, iterator_t<Base>>;
30 Returns: If
last_ele_
is present,x.last_ele_ - y.last_ele_
; otherwise,x.current_ - y.current_
.
slide_view::sentinel
[range.slide.sentinel]namespace std::ranges {
template<forward_range V>
requires view<V>
class slide_view<V>::sentinel {
sentinel_t<V> end_ = sentinel_t<V>(); // exposition only
constexpr explicit sentinel(sentinel_t<V> end); // exposition only
public:
sentinel() = default;
friend constexpr bool operator==(const iterator<false>& x, const sentinel& y);
friend constexpr range_difference_t<V>
operator-(const iterator<false>& x, const sentinel& y)
requires sized_sentinel_for<sentinel_t<V>, iterator_t<V>>;
friend constexpr range_difference_t<V>
operator-(const sentinel& y, const iterator<false>& x)
requires sized_sentinel_for<sentinel_t<V>, iterator_t<V>>;
};
}
1 [ Note 1: sentinel
is only used when slide-caches-first<V>
is true
. — end note ]
2 Effects: Initializes
end_
withend
.
3 Returns:
x.last_ele_ == y.end_
.
friend constexpr range_difference_t<V>
operator-(const iterator<false>& x, const sentinel& y)
requires sized_sentinel_for<sentinel_t<V>, iterator_t<V>>;
4 Returns:
x.last_ele_ - y.end_
.
friend constexpr range_difference_t<V>
operator-(const sentinel& y, const iterator<false>& x)
requires sized_sentinel_for<sentinel_t<V>, iterator_t<V>>;
5 Returns:
y.end_ - x.last_ele_
.
Add the following macro definitions 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:
#define __cpp_lib_ranges_chunk 20XXXXL // also in <ranges>
#define __cpp_lib_ranges_slide 20XXXXL // also in <ranges>
[P2214R0] Barry Revzin, Conor Hoekstra, Tim Song. 2020-10-15. A Plan for C++23 Ranges.
https://wg21.link/p2214r0
[P2321R2] Tim Song. 2021-06-11. zip.
https://wg21.link/p2321r2