views::take_before

• • Abstract
  • Revision history
  • Discussion
  • Design
  • Implementation experience
  • Proposed change
  • References

Abstract

This paper proposes the Tier 1 adaptor in P2760: views::delimit, which is renamed into views::take_before along with its corresponding view class to improve the C++29 ranges facilities.

Revision history

R0

Initial revision.

R1

Rename views::delimit to views::take_before based on feedback from SG9 in Sofia.

Extend conditional borrowed ranges for views::take_before(p, '\0').

R2

Extend borrowed when value type satisfies tidy-obj (which has the exact same definition as the tiny-func in P3117) based on feedback from Kona SG9.

R3

Removing support for single iterators based on feedback from LEWG.

Improving the wording slightly.

Discussion

views::take_before accepts a range and a specified value and produces a range ending with the first occurrence of that value. One common usage is to construct a NTBS range without calculating its actual length, for example:

  const char* p = /* from elsewhere */;
  const auto ntbs = views::take_before(subrange(p, unreachable_sentinel), '\0');

In other words, it is somewhat similar to the value-comparison version of views::take_while, which was originally classified into the take/drop family in P2214. Following the schedule of C++23 high-priority adaptors, views::take_before has now been moved from Tier 2 to Tier 1, as it provides an intuitive way to treat an element with a specific value as a sentinel.

Design

Why not aliasing to r | views::take_while(...)?

r | views::take_before(v) is basically equivalent to r | views::take_while([v](const auto& e) { return e != v; }), which suggests that implementing it via views::take_while might be sufficient. However, doing so is not an appropriate choice for the following reasons.

First, it's unclear whether to save v in a lambda or use bind_front(ranges::not_equal_to, v) for a more general purpose, which introduces extra indirection anyway. In other words, if we only want to compare *it == v, it will be done indirectly by:

invoke(bind_front(ranges::not_equal_to, v), *it) ---> ranges::not_equal_to(v , *it) ---> *it == v

in case of using views::take_while. As a result, As a result, we inevitably pay the cost of two extra function calls. This can introduce performance overhead, as it is unrealistic to assume that compilers can optimize out these calls in every scenario.

Secondly, additional specific constraints need to be introduced. Take lambda as an example, we should ensure that [v = forward<V>(v)](const auto& e) -> bool { return e != v; } is well-formed, but we cannot just spell it using requires-clause like

requires requires { [v = forward<V>(v)](const auto& e) -> bool { return e != v; }; }

because a capture list can produce hard errors, and the statement in the function body would also require corresponding constraints. This indicates that at least constructible_from<decay_t<V>, V> and equality_comparable_with<range_reference_t<R>, V> need to be added for the adaptor, such a lengthy constraint seems bloated and ugly. Note that this is also true when using bind_front, as it is not a constraint function either.

Instead, if a new take_before_view class is introduced, we can just check whether take_before_view(E, F) is well-formed because the view class already has the correct constraints.

Finally, if the bottom layer of views::take_before is take_while_view, then the former will have a pred() member which returns the internal functor. This can lead to significant confusion; users pass in a value, but what they get back is an unspecified predicate, which provides little practical utility.

To sum up, it is necessary to introduce a new take_before_view class which is not that complicated.

What are the constraints for take_before_view?

The implementation of take_before_view is very similar to take_while_view. The difference is that we need to save a value instead of a predicate, and its sentinel needs to compare the current element with the value instead of invoking the predicate.

First, the value type needs to model move_constructible to be wrapped by movable-box:

    template<view V, move_constructible T>
      requires input_range<V> && is_object_v<T> && /* */
    class take_before_view : public view_interface<take_before_view<V, T>> {
      V base_ = V();                                // exposition only
      movable-box<T> value_;                        // exposition only
      […]  
    };

However, the author prefers to use indirect_binary_predicate<ranges::equal_to, iterator_t<V>, const T*> to further comply with the mathematical sound for cross-type equality comparison:

    template<view V, move_constructible T>
    requires input_range<V> && is_object_v<T> &&
             indirect_binary_predicate<ranges::equal_to, iterator_t<V>, const T*>
    class take_before_view  : public view_interface<take_before_view<V, T>> {
      V base_ = V();                                // exposition only
      movable-box<T> value_;                        // exposition only
      […]  
    };

even if this requires that range_value_t<R> needs to be comparable with V which does not involve in the implementation. This makes the constraints of take_before_view corresponding to take_while_view consistent with ranges::find corresponding to ranges::find_if.

Should we provide in-place constructors for take_before_view?

Nope.

take_before_view takes ownership of the value which might be more efficient to construct it via in-place construction, so it seems reasonable to provide such a constructor like take_before_view(V base, in_place_t, Args&&... args).

Should we support the iterator version of views::take_before?

range/v3's views::take_before also supports accepting an iterator begin that returns subrange(begin, unreachable_sentinel) | views::take_before(v). However, supporting both the range and the iterator is not in line with the current standard design of range adaptor objects and users are free to make subrange(begin, unreachable_sentinel) through an iterator. To maintain a minimal and consistent API surface, this paper does not provide a separate iterator overload.

Do we need to introduce views::c_str as well?

views::c_str is also classified in T1 in P2760, which allows us to view a null-terminated character array as a range. It produces a sized subrange<const char*, const char*> when taking const char (&)[N] such as string literals, and views::take_before(p, '\0') when taking a character pointer p.

Since the former can be easily achieved through views::all("hello") or subrange("hello"), and the latter is just another way of writing views::take_before('\0'), the author believes its value is limited and thus chooses not to introduce it in this paper.

views::take_before vs views::take_until?

Should views::take_before(p, '\0') be a borrowed range?

In R0, the specified value is always stored in take_before_view with its sentinel storing a pointer to take_before_view for accessing the value, which makes take_before_view never a borrowed range.

During Sofia, SG9 raised concerns that this might not be desirable since such non-borrowability would inconvenience users.

For example, for trivial values such as integers, we can store them in the sentinel so that views::take_before(p, '\0') or views::take_before(r, 42) can be a borrowed range, which also eliminates indirect access to the value when checking for end.

However, during Kona, SG9 preferred to use the implementation-only trait consistent with P3117 to extend borrowability to allow views::take_before(r, cw<42>), although this made the previous example no longer borrowable, and it also meant that the view class and sentinel class no longer needed to store the value, which reduces the binary size.

Implementation experience

The author implemented views::take_before based on libc++, see here.

Proposed change

This wording is relative to N5014.

References