elements_view
needs its own sentinel
Document #: | P1994R1 |
Date: | 2020-02-12 |
Project: | Programming Language C++ LWG |
Reply-to: |
Tim Song <t.canens.cpp@gmail.com> Christopher Di Bella <cjdb.ns@gmail.com> |
elements_view
needs its own sentinel
type. This paper resolves [LWG3386].
elements_view
is effectively a specialized version of transform_view
; the latter has a custom sentinel
type, and so should elements_view
.
More generally, if a range adaptor has a custom iterator, it should probably also have a custom sentinel. The rationale is that the underlying range’s sentinel could encode a generic predicate that is equally meaningful for the adapted range, leading to an ambiguity.
For example, consider:
struct S { // sentinel that checks if the second element is zero
friend bool operator==(input_iterator auto const& i, S) requires /* ... */
{ return get<1>(*i) == 0; }
};
void algo(input_range auto&& r) requires /* ... */ {
for (auto&& something : subrange{ranges::begin(r), S{}})
{
/* do something */
}
}
using P = pair<pair<char, int>, long>;
vector<P> something = /* ... */;
subrange r{something.begin(), S{}};
algo(r | view::keys); // checks the long, effectively iterating over r completely
algo(r | view::transform(&P::first)); // checks the int and stops at the first zero
algo
is trying to use the sentinel S
to stop at the first element e
for which get<1>(e)
is zero, and it works correctly for all ranges of pair<char, int>
… except things like r | view::keys
. In the latter case, ranges::begin(r | view::keys) == S{}
calls elements_view::iterator
’s operator==
instead, which compares the underlying range’s iterator against the sentinel. In the above example, this means that we check the long
instead of the int
, and effectively iterate over the entire range.
A custom sentinel is needed to avoid this problem. elements_view
is the only adaptor in the current WP that has a custom iterator but not a custom sentinel.
This wording is relative to [N4849].
[ Drafting note: These changes, including the overload set for end
, match the specification of transform_view
. This seems appropriate since elements_view
is just a special kind of transform. ]
Edit 24.7.15.2 [range.elements.view], class template elements_view
synopsis, as indicated:
namespace std::ranges { […] template<input_range V, size_t N> requires view<V> && has-tuple-element<range_value_t<V>, N> && has-tuple-element<remove_reference_t<range_reference_t<V>>, N> class elements_view : public view_interface<elements_view<V, N>> { public: […] + constexpr auto end() + { return sentinel<false>{ranges::end(base_)}; } + + constexpr auto end() requires common_range<V> + { return iterator<false>{ranges::end(base_)}; } + + constexpr auto end() const + requires range<const V> + { return sentinel<true>{ranges::end(base_)}; } + + constexpr auto end() const + requires common_range<const V> + { return iterator<true>{ranges::end(base_)}; } - constexpr auto end() requires (!simple-view<V>) - { return ranges::end(base_); } - constexpr auto end() const requires simple-view<V> - { return ranges::end(base_); } […] private: template<bool> struct iterator; // exposition only + template<bool> struct sentinel; // exposition only V base_ = V(); // exposition only }; }
Edit 24.7.15.3 [range.elements.iterator], class template elements_view<V, N>::iterator
synopsis, as indicated:
namespace std::ranges { template<class V, size_t N> template<bool Const> class elements_view<V, N>::iterator { // exposition only […] public: […] - friend constexpr bool operator==(const iterator& x, const sentinel_t<base-t>& y); […] - friend constexpr difference_type - operator-(const iterator<Const>& x, const sentinel_t<base-t>& y) - requires sized_sentinel_for<sentinel_t<base-t>, iterator_t<base-t>>; - friend constexpr difference_type - operator-(const iterator<base-t>& x, const iterator<Const>& y) - requires sized_sentinel_for<sentinel_t<base-t>, iterator_t<base-t>>; }; }
Delete the specification of these operators in 24.7.15.3 [range.elements.iterator] (p13, 23 and 24):
13 Effects: Equivalent to:
return x.current_ == y;
…
friend constexpr difference_type operator-(const iterator<Const>& x, const sentinel_t<base-t>& y) requires sized_sentinel_for<sentinel_t<base-t>, iterator_t<base-t>>;
23 Effects: Equivalent to:
return x.current_ - y;
friend constexpr difference_type operator-(const sentinel_t<base-t>& x, const iterator<Const>& y) requires sized_sentinel_for<sentinel_t<base-t>, iterator_t<base-t>>;
24 Effects: Equivalent to:
return -(y - x);
Add a new subclause after 24.7.15.3 [range.elements.iterator]:
elements_view::sentinel
[ranges.elements.sentinel]namespace std::ranges {
template<class V, size_t N>
template<bool Const>
class elements_view<V, N>::sentinel { // exposition only
private:
using Base = conditional_t<Const, const V, V>; // exposition only
sentinel_t<Base> end_ = sentinel_t<Base>(); // exposition only
public:
sentinel() = default;
constexpr explicit sentinel(sentinel_t<Base> end);
constexpr sentinel(sentinel<!Const> other)
requires Const && convertible_to<sentinel_t<V>, sentinel_t<Base>>;
constexpr sentinel_t<Base> base() const;
friend constexpr bool operator==(const iterator<Const>& x, const sentinel& y);
friend constexpr range_difference_t<Base>
operator-(const iterator<Const>& x, const sentinel& y)
requires sized_sentinel_for<sentinel_t<Base>, iterator_t<Base>>;
friend constexpr range_difference_t<Base>
operator-(const sentinel& x, const iterator<Const>& y)
requires sized_sentinel_for<sentinel_t<Base>, iterator_t<Base>>;
};
}
1 Effects: Initializes
end_
withend
.
constexpr sentinel(sentinel<!Const> other) requires Const && convertible_to<sentinel_t<V>, sentinel_t<Base>>;
2 Effects: Initializes
end_
withstd::move(other.end_)
.3 Effects: Equivalent to:
return end_;
4 Effects: Equivalent to:
return x.current_ == y.end_;
5 Effects: Equivalent to:
return x.current_ - y.end_;
friend constexpr range_difference_t<Base> operator-(const sentinel& x, const iterator<Const>& y) requires sized_sentinel_for<sentinel_t<Base>, iterator_t<Base>>;
6 Effects: Equivalent to:
return x.end_ - y.current_;
[LWG3386] Tim Song. elements_view needs its own sentinel type.
https://wg21.link/lwg3386
[N4849] Richard Smith. 2020. Working Draft, Standard for Programming Language C++.
https://wg21.link/n4849