Document number | P3230R0 |
Date | 2024-04-05 |
Audience | LEWG, SG9 (Ranges) |
Reply-to | Hewill Kang <hewillk@gmail.com> |
views::(take|drop)_exactly
This paper proposes Tier 1 adaptors in P2760:
views::drop_exactly
and views::take_exactly
, which are cousins of drop
and take
, to improve the C++26
ranges facilities.
Initial revision.
drop_exactly
and take_exactly
are very similar to drop
and take
,
the only difference is that the former requires that N
must not be greater than the number of
elements in the original range; otherwise, it will be NB, which is exactly the "exactly" part.
Since there is no bounds check, views::meow_exactly
is more efficient than
views::meow
for situations where the user already knows that there are enough elements
in the range.
drop_exactly_view
/take_exactly_view
classes?
Although both can achieve similar effects with existing utilities, e.g.
take_exactly(r, N)
is somewhat equivalent to views::counted(ranges::begin(r), N)
, and
drop_exactly
is somewhat equivalent to
subrange(ranges::next(std::ranges::begin(r), N), ranges::end(r))
, these are not fully replaceable
due to certain limitations.
The main issue is that both need to apply ranges::begin
to extract the iterator of the origin range,
which
may be ill-formed when taking rvalue ranges,
not to mention that drop_exactly_view
also needs to cache the result to meet the time complexity
requiring by the range
concept.
Since we've already assumed that the range is large enough, out-of-bounds cases are ignored in the implementation,
which means that meow_exactly_view
is just a
reduced version of meow_view
. So introducing these classes doesn't bring much complexity to the
standard.
Currently, both take
and drop
have optimized the return type, that is, when it takes an object of range type empty_view
,
span
, string_view
, subrange
, iota_view
and
repeat_view
, it will return an object of the same type to reduce template instantiation. There is no
reason not to apply similar optimizations to take_exactly
and drop_exactly
.
However, it should be noted that compared to the former, since we no longer care whether the specialized type
models
sized_range
, views::meow_exactly
applied to the infinite range may downgrade it to
a
finite
range.
For example, views::iota(0) | views::take_exactly(5)
will produce
views::iota(0, 5)
, and views::iota(0) | views::drop_exactly(5)
will produce
views::iota(5)
, this applies to subrange<int*, unreachable_sentinel_t>
as well.
take_exactly
and drop_exactly
, it is natural to think
whether we need slice_exactly
, take_last_exactly
and drop_last_exactly
, etc.
Considering the bandwidth of LEWG, this paper does not intend to introduce these potentially useful utilities.
The author implemented views::(take|drop)_exactly
based on libstdc++, see here.
This wording is relative to N4971.
Add a new feature-test macro to 17.3.2 [version.syn]:
#define __cpp_lib_ranges_take_exactly 2024XXL // freestanding, also in <ranges>#define __cpp_lib_ranges_drop_exactly 2024XXL // freestanding, also in <ranges>
Modify 26.2 [ranges.syn], Header <ranges> synopsis, as indicated:
#include <compare> // see [compare.syn] #include <initializer_list> // see [initializer.list.syn] #include <iterator> // see [iterator.synopsis] namespace std::ranges { […] namespace views { inline constexpr unspecified take = unspecified; } // freestanding // [range.take.exactly], take exactly view template<view> class take_exactly_view; // freestanding template<class T> constexpr bool enable_borrowed_range<take_exactly_view<T>> = // freestanding enable_borrowed_range<T>; namespace views { inline constexpr unspecified take_exactly = unspecified; } // freestanding […] namespace views { inline constexpr unspecified drop = unspecified; } // freestanding // [range.drop.exactly], drop exactly view template<view V> class drop_exactly_view; // freestanding template<class T> constexpr bool enable_borrowed_range<drop_exactly_view<T>> = // freestanding enable_borrowed_range<T>; namespace views { inline constexpr unspecified drop_exactly = unspecified; } // freestanding […] }
Add 26.7.? Take exactly view [range.take.exactly] after 26.7.10 [range.take] as indicated:
[26.7.?.1] Overview [range.take.exactly.overview]
-1- take_exactly_view
produces a view of the first N
elements from another
view.
The behavior is undefined if the adapted view contains fewer than N
elements.
-2- The name views::take_exactly
denotes a range adaptor object (26.7.2 [range.adaptor.object]).
Let E
and F
be expressions, let T
be
remove_cvref_t<decltype((E))>
,
and let D
be range_difference_t<decltype((E))>
.
If decltype((F))
does not model convertible_to<D>
,
views::take_exactly(E, F)
is ill-formed. Otherwise, the expression views::take_exactly(E, F)
is expression-equivalent to:
(2.1) — if T
is a specialization of empty_view
(26.6.2.2 [range.empty.view]),
then ((void)F, decay-copy(E))
, except that the evaluations of E
and F
are indeterminately sequenced.
(2.2) — Otherwise, if T
models random_access_range
and is a specialization of span
(24.7.2.2 [views.span]),
basic_string_view
(23.3 [string.view]),
or
ranges::subrange
(26.5.4 [range.subrange]), then U(ranges::begin(E), ranges::begin(E) +
static_cast<D>(F))
, except that E
is evaluated only once,
where U
is a type determined as follows:
(2.2.1) — if T
is a specialization of span
, then U
is
span<typename T::element_type>
;
(2.2.2) — otherwise, if T
is a specialization of basic_string_view
,
then
U
is T
;
(2.2.3) — otherwise, T
is a specialization of subrange
,
and U
is subrange<iterator_t<T>>
;
(2.3) — otherwise, if T
is a specialization of iota_view
(26.6.4.2 [range.iota.view]) that models
random_access_range
, then
iota_view(*ranges::begin(E), *(ranges::begin(E) + static_cast<D>(F)))
,
except that E
is evaluated only once.
(2.4) — Otherwise, if T
is a specialization of repeat_view
(26.6.5.2 [range.repeat.view]), then
views::repeat(*E.value_, static_cast<D>(F))
.
(2.5) — Otherwise, take_exactly_view(E, F)
.
-3- [Example 1:
auto ints = views::iota(0) | views::take_exactly(10); for (auto i : ints | views::reverse) { cout << i << ' '; // prints 9 8 7 6 5 4 3 2 1 0 }— end example]
[26.7.?.2] Class template take_exactly_view
[range.take.exactly.view]
namespace std::ranges { template<view V> class take_exactly_view : public view_interface<take_exactly_view<V>> { private: V base_ = V(); // exposition only range_difference_t<V> count_ = 0; // exposition only public: take_exactly_view() requires default_initializable<V> = default; constexpr explicit take_exactly_view(V base, range_difference_t<V> count); constexpr V base() const & requires copy_constructible<V> { return base_; } constexpr V base() && { return std::move(base_); } constexpr auto begin() requires (!simple-view<V>) { if constexpr (random_access_range<V>) return ranges::begin(base_); else return counted_iterator(ranges::begin(base_), count_); } constexpr auto begin() const requires range<const V> { if constexpr (random_access_range<const V>) return ranges::begin(base_); else return counted_iterator(ranges::begin(base_), count_); } constexpr auto end() requires (!simple-view<V>) { if constexpr (random_access_range<V>) return ranges::begin(base_) + count_; else return default_sentinel; } constexpr auto end() const requires range<const V> { if constexpr (random_access_range<const V>) return ranges::begin(base_) + range_difference_t<const V>(count_); else return default_sentinel; } constexpr auto size() const noexcept { return to-unsigned-like(count_); } }; template<class R> take_exactly_view(R&&, range_difference_t<R>) -> take_exactly_view<views::all_t<R>>; }
constexpr explicit take_exactly_view(V base, range_difference_t<V> count);
-1- Preconditions:
count <= ranges::distance(base)
istrue
.-2- Effects: Initializes
base_
withstd::move(base)
andcount_
withcount
.
Add 26.7.? Drop exactly view [range.drop.exactly] after 26.7.12 [range.drop] as indicated:
[26.7.?.1] Overview [range.drop.exactly.overview]
-1- drop_exactly_view
produces a view excluding the first N
elements from
another view.
The behavior is undefined if the adapted view contains fewer than N
elements.
-2- The name views::drop_exactly
denotes a range adaptor object (26.7.2 [range.adaptor.object]).
Let E
and F
be expressions, let T
be
remove_cvref_t<decltype((E))>
,
and let D
be range_difference_t<decltype((E))>
.
If decltype((F))
does not model convertible_to<D>
,
views::drop_exactly(E, F)
is ill-formed. Otherwise, the expression views::drop_exactly(E, F)
is expression-equivalent to:
(2.1) — if T
is a specialization of empty_view
(26.6.2.2 [range.empty.view]),
then ((void)F, decay-copy(E))
, except that the evaluations of E
and F
are indeterminately sequenced.
(2.2) — Otherwise, if T
models random_access_range
and is
(2.2.1) — a specialization of span
(24.7.2.2 [views.span]),
(2.2.2) — a specialization of basic_string_view
(23.3 [string.view]),
(2.2.3) — a specialization of iota_view
(26.6.4.2 [range.iota.view]), or
(2.2.4) — a specialization of subrange
(26.5.4 [range.subrange])
where T::StoreSize
is false
,
then U(ranges::begin(E) + static_cast<D>(F), ranges::end(E))
,
except that E
is evaluated only once, where U
is span<typename
T::element_type>
if T
is a specialization of span
and T
otherwise.
(2.3) — Otherwise, if T
is a specialization of subrange
(26.5.4 [range.subrange]) that models
random_access_range
and sized_range
, then
T(ranges::begin(E) + static_cast<D>(F), ranges::end(E),
to-unsigned-like(ranges::distance(E) - static_cast<D>(F)))
,
except that E
and F
are each evaluated only once.
(2.4) — Otherwise, if T
is a specialization of repeat_view
(26.6.5.2 [range.repeat.view]):
(2.4.1) — if T
models sized_range
, then
views::repeat(*E.value_, ranges::distance(E) - static_cast<D>(F))except that
E
is evaluated only once;
(2.4.2) — otherwise, ((void)F, decay-copy(E))
, except that the
evaluations of
E
and F
are indeterminately sequenced.
(2.5) — Otherwise, drop_exactly_view(E, F)
.
-3- [Example 1:
vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; for (int i : is | views::drop_exactly(6) | views::take_exactly(3)) { cout << i << ' '; // prints 6 7 8 }— end example]
[26.7.?.2] Class template drop_exactly_view
[range.drop.exactly.view]
namespace std::ranges { template<view V> class drop_exactly_view : public view_interface<drop_exactly_view<V>> { public: drop_exactly_view() requires default_initializable<V> = default; constexpr explicit drop_exactly_view(V base, range_difference_t<V> count); constexpr V base() const & requires copy_constructible<V> { return base_; } constexpr V base() && { return std::move(base_); } constexpr auto begin() requires (!(simple-view<V> && random_access_range<const V>)); constexpr auto begin() const requires random_access_range<const V>; constexpr auto end() requires (!simple-view<V>) { return ranges::end(base_); } constexpr auto end() const requires range<const V> { return ranges::end(base_); } constexpr auto size() requires sized_range<V> { return ranges::size(base_) - static_cast<range_size_t<V>>(count_); } constexpr auto size() const requires sized_range<const V> { return ranges::size(base_) - static_cast<range_size_t<const V>>(count_); } private: V base_ = V(); // exposition only range_difference_t<V> count_ = 0; // exposition only }; template<class R> drop_exactly_view(R&&, range_difference_t<R>) -> drop_exactly_view<views::all_t<R>>; }
constexpr explicit drop_exactly_view(V base, range_difference_t<V> count);
-1- Preconditions:
count <= ranges::distance(base)
istrue
.-2- Effects: Initializes
base_
withstd::move(base)
andcount_
withcount
.
constexpr auto begin() requires (!(simple-view<V> && random_access_range<const V>)); constexpr auto begin() const requires random_access_range<const V>
-3- Returns:
ranges::next(ranges::begin(base_), count_)
.-4- Remarks: In order to provide the amortized constant-time complexity required by the
[Note 1: Without this, applying arange
concept whendrop_exactly_view
modelsforward_range
, the first overload caches the result within thedrop_exactly_view
for use on subsequent calls.reverse_view
over adrop_exactly_view
would have quadratic iteration complexity. — end note]