views::delimit

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

Abstract

This paper proposes the Tier 1 adaptor in P2760: views::delimit along with delimit_view to improve the C++26 ranges facilities.

Revision history

R0

Initial revision.

Discussion

views::delimit accepts a range (or iterator) 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* s = /* from elsewhere */;
  const auto ntbs = views::delimit(s, '\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::delimit 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 just r | views::take_while(...)?

r | views::delimit(v) is basically equivalent to r | views::take_while([v](const auto& e) { return e != v; }), which seems that it is sufficient to just implement it via views::take_while. 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, we inevitably pay the cost of two extra function calls, which may bring performance issues because it is unrealistic to assume that the compiler can optimize out these calls in any case.

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; } can be constructed, but we cannot just put it in the requires-clause because capture list can produce hard errors, and the return statement also requires corresponding constraint. This indicates that at least constructible_from<decay_t<V>, V> and equality_comparable_with<range_reference_t<R>, V> need to be added to the adaptor's call operator, 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 delimit_view class is introduced, we can just check whether delimit_view(E, F) is well-formed because the class already has the correct constraints.

Finally, if the bottom layer of views::delimit is take_while_view, then the former will have a pred() member which returns the internal lambda. This can lead to untold confusion, as the user passes in a value, but all he gets back is an unspecified predicate, and there's really not much use in getting such an unspecified object.

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

What are the constraints for delimit_view?

The implementation of delimit_view is very similar to take_while. 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 delimit_view : public view_interface<delimit_view<V, T>> {
      […]
    };

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, even if this require that range_value_t<R> needs to be comparable with V which does not involve in the implementation.

This makes the constraints of delimit_view corresponding to take_while_view consistent with ranges::find corresponding to ranges::find_if.

Should we provide in-place constructors for delimit_view?

Nope.

delimit_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 delimit_view(V base, in_place_t, Args&&... args).

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

range/v3's views::delimit also supports accepting an iterator it that returns subrange(it, unreachable_sentinel) | views::delimit(v). Providing such overloading does have a certain value, because sometimes we may only have const char*.

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::delimit(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::delimit('\0'), the author believes that the value it provides is limited, so it is not introduced in this paper. However, the author remains neutral.

Implementation experience

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

Proposed change

This wording is relative to N4971.

References