elements_view needs its own sentinel

Document #: P1994R1
Date: 2020-02-12
Project: Programming Language C++
LWG
Reply-to: Tim Song
<>
Christopher Di Bella
<>

1 Abstract

elements_view needs its own sentinel type. This paper resolves [LWG3386].

2 Revision history

3 Discussion

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.

4 Wording

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):

friend constexpr bool operator==(const iterator& x, const sentinel_t<base-t>& y);

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]:

?.?.?.? Class template 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>>;
  };
}
constexpr explicit sentinel(sentinel_t<Base> end);

1 Effects: Initializes end_ with end.

constexpr sentinel(sentinel<!Const> other)
  requires Const && convertible_to<sentinel_t<V>, sentinel_t<Base>>;

2 Effects: Initializes end_ with std::move(other.end_).

constexpr sentinel_t<Base> base() const;

3 Effects: Equivalent to: return end_;

friend constexpr bool operator==(const iterator<Const>& x, const sentinel& y);

4 Effects: Equivalent to: return x.current_ == y.end_;

friend constexpr range_difference_t<Base>
  operator-(const iterator<Const>& x, const sentinel& y)
    requires sized_sentinel_for<sentinel_t<Base>, iterator_t<Base>>;

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_;

5 References

[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