views::to_input
Document #: | P3137R0 |
Date: | 2024-02-14 |
Project: | Programming Language C++ |
Audience: |
SG9 |
Reply-to: |
Tim Song <t.canens.cpp@gmail.com> |
This paper proposes the views::to_input
adaptor that downgrades a source range to an input-only, non-common range.
The motivation for this view is given in [P2760R1] and quoted below for convenience (with the name changed from as_input
to to_input
; see the naming discussion below):
Why would anybody want such a thing? Performance.
Range adaptors typically provide the maximum possible iterator category - in order to maximize functionality. But sometimes it takes work to do so. A few examples:
views::join(r)
is common whenr
is, which means it provides two iterators. The iterator comparison forjoin
does two iterator comparisons, for both the outer and the inner iterator, which is definitely necessary when comparing two iterators. But if all you want to do is compareit == end
, you could’ve gotten away with one iterator comparison. As such, iterating over a commonjoin_view
is more expensive than an uncommon one.views::chunk(r, n)
has a different algorithm for input vs forward. For forward+, you get a range ofviews::take(n)
- if you iterate through every element, then advancing from one chunk to the next chunk requires iterating through all the elements of that chunk again. For input, you can only advance element at a time.The added cost that
views::chunk
adds when consuming all elements for forward+ can be necessary if you need the forward iterator guarantees. But if you don’t need it, like if you’re just going to consume all the elements in order one time. Or, worse, the next adaptor in the chain reduces you down to input anyway, this is unnecessary.In this way,
r | views::chunk(n) | views::join
can be particularly bad, since you’re paying additional cost forchunk
that you can’t use anyway, sinceviews::join
here would always be an input range.r | views::to_input | views::chunk(n) | views::join
would alleviate this problem. It would be a particularly nice way to alleviate this problem if users didn’t have to write theviews::to_input
part!This situation was originally noted in [range-v3#704].
P2760R1 proposes as_input
, but the two as_meow
views we have (as_const
and as_rvalue
) are element-wise operations rather than operations on the view itself. So this paper proposes the name to_input
.
to_input
is conditionally borrowed, input-only (that’s its whole point), non-common, and conditionally const-iterable. As usual, wrapping is avoided if possible. The iterator only provides the minimal interface needed for an input iterator.
In theory, we could provide all the operations supported by the underlying iterator, and limit our change to the iterator concept. Such operations would be unlikely to see much use: to_input
is a facility for influencing generic algorithms, and generic algorithms generally have to rely on the concept to determine if an operation can be used. So we do not try to do so here.
This wording is relative to [N4971].
<ranges>
Add the following to 26.2 [ranges.syn], header <ranges>
synopsis:
// [...]
namespace std::ranges {
// [...]
// [range.to.input], to input view
template<input_range V>
requires view<V>
class to_input_view;
template<class V>
inline constexpr bool enable_borrowed_range<to_input_view<V>> =
enable_borrowed_range<V>;
namespace views {
inline constexpr unspecified to_input = unspecified;
}
}
to_input
Add the following subclause to 26.7 [range.adaptors]:
1 to_input_view
presents a view of an underlying sequence as an input-only non-common range. [ Note 1: This is useful to avoid overhead that may be necessary to provide support for the operations needed for greater iterator strength. — end note ]
2 The name views::to_input
denotes a range adaptor object (26.7.2 [range.adaptor.object]). Let E
be an expression and let T
be decltype((E))
. The expression views::to_input(E)
is expression-equivalent to:
views::all(E)
if T
models input_range
, does not model common_range
, and does not model forward_range
;to_input_view(E)
.to_input_view
[range.to.input.view]template<input_range V>
requires view<V>
class to_input_view : public view_interface<to_input_view<V>>{
V base_ = V(); // exposition only
template<bool Const>
class iterator; // exposition only
public:
to_input_view() requires default_initializable<V> = default;
constexpr explicit to_input_view(V base);
constexpr V base() const & requires copy_constructible<V> { return base_; }
constexpr V base() && { return std::move(base_); }
constexpr auto begin() requires (!simple-view<V>);
constexpr auto begin() const requires range<const V>;
constexpr auto end() requires (!simple-view<V>);
constexpr auto end() const requires range<const V>;
constexpr auto size() requires sized_range<V>;
constexpr auto size() const requires sized_range<const V>;
};
template<class R>
to_input_view(R&&) -> to_input_view<views::all_t<R>>;
1 Effects: Initializes
base_
withstd::move(base)
.
2 Effects: Equivalent to:
3 Effects: Equivalent to:
constexpr auto end() requires (!simple-view<V>);
constexpr auto end() const requires range<const V>;
4 Effects: Equivalent to:
constexpr auto size() requires sized_range<V>;
constexpr auto size() const requires sized_range<const V>;
5 Effects: Equivalent to:
to_input_view::iterator
[range.to.input.iterator]namespace std::ranges {
template<input_range V>
requires view<V>
template<bool Const>
class to_input_view<V>::iterator {
using Base = maybe-const<Const, V>; // exposition only
iterator_t<Base> current_ = iterator_t<Base>(); // exposition only
constexpr explicit iterator(iterator_t<Base> current); // exposition only
public:
using difference_type = range_difference_t<Base>;
using value_type = range_value_t<Base>;
using iterator_concept = input_iterator_tag;
iterator() requires default_initializable<iterator_t<Base>> = default;
iterator(iterator&&) = default;
iterator& operator=(iterator&&) = default;
constexpr iterator(iterator<!Const> i)
requires Const && convertible_to<iterator_t<V>, iterator_t<Base>>;
constexpr iterator_t<Base> base() &&;
constexpr const iterator_t<Base>& base() const & noexcept;
constexpr decltype(auto) operator*() const { return *current_; }
constexpr iterator& operator++();
constexpr void operator++(int);
friend constexpr bool operator==(const iterator& x, const sentinel_t<Base>& y);
friend constexpr range_rvalue_reference_t<Base> iter_move(const iterator& i)
noexcept(noexcept(ranges::iter_move(i.current_)));
friend constexpr void iter_swap(const iterator& x, const iterator& y)
noexcept(noexcept(ranges::iter_swap(x.current_, y.current_)))
requires indirectly_swappable<iterator_t<Base>>;
};
}
1 Effects: Initializes
current_
withstd::move(current)
.
constexpr iterator(iterator<!Const> i)
requires Const && convertible_to<iterator_t<V>, iterator_t<Base>>;
2 Effects: Initializes
current_
withstd::move(i.current_)
.
3 Returns:
std::move(current_)
.
4 Returns:
current_
.
5 Effects: Equivalent to:
6 Effects: Equivalent to:
++*this;
7 Returns:
x.current_ == y;
friend constexpr range_rvalue_reference_t<Base> iter_move(const iterator& i)
noexcept(noexcept(ranges::iter_move(i.current_)));
8 Effects: Equivalent to:
return ranges::iter_move(i.current_);
friend constexpr void iter_swap(const iterator& x, const iterator& y)
noexcept(noexcept(ranges::iter_swap(x.current_, y.current_)))
requires indirectly_swappable<iterator_t<Base>>;
9 Effects: Equivalent to:
ranges::iter_swap(x.current_, y.current_);
[N4971] Thomas Köppe. 2023-12-18. Working Draft, Programming Languages — C++.
https://wg21.link/n4971
[P2760R1] Barry Revzin. 2023-12-15. A Plan for C++26 Ranges.
https://wg21.link/p2760r1
[range-v3#704] Eric Niebler. 2017. Demand-driven view strength weakening.
https://github.com/ericniebler/range-v3/issues/704