1 Revision History

Since [P2214R1], updating with progress and links to other papers.

Since [P2214R0], updating with progress and links to other papers. Several changes have been made here:

• Pipe support for range adaptors has been added as a Tier 1 priority.
• cache1 has been lowered from Tier 1 to Tier 2 due to inherent issues with its design.
• as_const has been upgraded from Tier 3 to Tier 1 due to demand (and renamed from const_).
• flat_map has been lowered to Tier 3 (since now transform(f) | join is correct for all cases).
• transform_maybe has been lowered to Tier 2 (since it depends on cache1)
• the various set range adaptors were omitted previously, and are added as Tier 3.
• two more algorithms that weren’t rangified for C++20 added as Tier 1: shift_left and shift_right.
• added more color to the discussion of chunk_by

2 Introduction

When Ranges was merged into C++20 [P0896R4], it was knowingly incomplete. While it was based on the implementation experience in range-v3 [range-v3], only a small part of that library was adopted into C++20. The Ranges proposal was big enough already, a lot of the pieces were separable and so could be included later.

But now that the core of Ranges has been included, later has come and we have to figure out what to do for C++23. This is a particularly trying period in the committee’s history with the global pandemic and lack of face-to-face meetings. But we do already have a plan for C++23 [P0592R4] which laid out the following priorities:

and

We believe that adding more functionality to Ranges is important, even if it would technically be a 3rd priority item (unless you consider the spirit of the 2nd priority to include integration with itself).

But there is a lot of outstanding functionality that could be added. And while we think all of it should eventually be added (having more algorithms and more views is always a good thing), we realize that this is may be too much even in the C++23 time frame. Rather than having one-off papers that propose one bit of functionality (as in [P1255R6], [P1894R0], or [P2164R5]), we think it’s important to take a big picture view of what is out there and triage the various parts into three separate buckets:

1. Functionality that is really important for C++23. That which is frequently used and broadly applicable, and thus whose absence is frequently complained about.
2. Functionality that would be nice to have for C++23. Not as frequently needed as the first bucket, but still clearly want it in the standard - but more tolerable if this slips. Ideally C++23 anyway, but simply less critical.
3. Functionality that is less important or needs more design work.

This paper provides our opinion for how to categorize Ranges functionality into those three buckets. We go through, in turn: views-adjacent functionality, views, algorithms, and actions (which do not exist in C++20).

3 View adjuncts

C++20 Ranges, and the range-v3 that birthed it, isn’t just a collection of loosely related views and algorithms. There’s some important other functionality there.

One critical piece of missing functionality is ranges::to [P1206R7]. It’s not a view, but it is often used as the terminal component of a view pipeline to create a new trailing range - to finally collect the results of the computation being constructed. This is a top priority and is sorely missing.

Another criticial piece of functionality was pointed out by Walter Brown in the telecon discussing the initial draft of this paper: it is simply not possible for users to write their own range adaptors such that they smoothly interact with standard library (or other user) range adaptors. That is, it is possible (but a little tedious) for users to write an adaptor such that they can write r | my::thing | my::func(2), but it is not possible for them to write an adaptor such that they can write:

auto adaptor = my::thing | std::views::transform(f) | my::func(2);
auto result = r | adaptor;

In order to do that, standard library adaptors need to recognize user-defined adaptors as being adaptors. That needs library help and is also a top priority - since if users can define more adaptors, it becomes less critical that the standard library provide all of them. The standard library needs to provide pipe support for user-defined adaptors [P2387R3]

Another important piece of functionality is simply the ability to print views. In range-v3, views were printable, which made it easy to debug programs or to provide meaningful output. For instance, the following program using range-v3 happily compiles:

#include <range/v3/view/iota.hpp>
#include <range/v3/view/transform.hpp>
#include <range/v3/view/filter.hpp>
#include <iostream>

int main() {
    namespace rv = ranges::views;
    auto r = rv::iota(0, 20)
           | rv::filter([](int i) { return i % 2 == 0; })
           | rv::transform([](int i){ return i * i; });
    std::cout << r;
}

and prints [0,4,16,36,64,100,144,196,256,324].

Similarly, fmtlib supports printing ranges with fmt::join, which is slightly more tedious but is at least still a single line:

#include <range/v3/view/iota.hpp>
#include <range/v3/view/transform.hpp>
#include <range/v3/view/filter.hpp>
#include <fmt/format.h>

int main() {
    namespace rv = ranges::views;
    auto r = rv::iota(0, 20)
           | rv::filter([](int i) { return i % 2 == 0; })
           | rv::transform([](int i){ return i * i; });
    fmt::print("[{}]", fmt::join(r, ","));
}

But neither the ability to stream views directly nor fmt::join are in C++20, so there is no direct way to print a range at all.

We think it’s important that C++23 provides the ability to format all the ranges [P2286R6]. Since these are all standard library types, it is difficult for the user to be able to actually do this themselves and it’s frustrating to even have to.

4 Views

C++20 included a bunch of views, but range-v3 has a whole lot more. Views, much like algorithms, are the kind of thing where it’s just generally good to have more of them. The C++20 standard library has over 100 algorithms, but only 17 range adapters and view factories (excluding all and ref). We want more.

We’ll start this section by enumerating all the adapters in range-v3 (and a few that aren’t), noting their current status, and ranking them according to our view of their priority for C++23, before describing how we came up with such a ranking.

4.1 Full view or not full view

One question we have to ask is which of these views need to be full-blown view types and which do not. This is an important question to deal with in light of the very real limitation that is LWG’s bandwidth. Views that need to be full types necessitate more longer and more complex specification which require more LWG time. Views that need not be full types could save some time.

Consider views::tail. This is a very simple range adapter that simply drops its first element. As such, it could be specified entirely as:

namespace std::ranges::views {
    inline constexpr auto tail = drop(1);
}

The above is a semantically correct implementation. However, is it the implementation we would actually want for views::tail? There are a few extra things views::drop has to do. views::drop must store a count and a cache for the begin iterator for forward ranges (to satisfy O(1)), but views:tail has to do none of these things since 1 is a constant and invoking next() one time still satisfies O(1).

This puts us in an interesting position: we either adopt a known suboptimal implementation of tail with minimal LWG cost (such that we could likely adopt this for C++23) or we could hold off for the optimal implementation (in which case we could not in good conscience put tail as a Tier 1 view, as it is certainly not that important). As such, we have tentatively marked it as Tier 3.

Take a different view, unbounded. A perfectly valid implementation of it, in its entirely is:

namespace std::ranges::views {
    inline constexpr auto unbounded = [](input_iterator auto it){
        return subrange(std::move(it), unreachable_sentinel);
    };
}

Unlike tail, there isn’t really some other, better implementation here. Maybe we’d prefer to give unbounded_view<I> its own type rather than piggy-backing off of subrange, but it wouldn’t really affect the choice of functionality overall. Here the question is less, do we do it fast for C++23 or do it right for C++26 or C++20. Rather, the question is more: do we even need this at all? We think we don’t.

Consider two different, closely related views: views::zip and views::zip_transform (which range-v3 calls zip_with). Each could potentially be specified in terms of the other:

• views::zip(Es...) could be views::zip_transform(forward-as-tuple, Es...)
• views::zip_transform(F, Es...) could be views::zip(Es...) | views::transform(applied(F))

where forward-as-tuple is a function object version of std::forward_as_tuple and applied(F)(x) is equivalent to std::apply(F, x).

But they’re not quite equivalent — they differ in their handling of ranges that produce prvalues. zip_transform can’t differentiate between prvalues and xvalues, while zip would need to, so we lose that distinction by implementing zip in terms of zip_transform.

Likewise, a first-class zip_transform would construct those prvalues directly into the parameters of the function that gets passed in; whereas if we implemented zip_transform in terms of zip and transform those prvalues would have to first be materialized into a tuple and then moved into the function.

Even though these two views are very, very similar to each other, we still don’t want to specify one in terms of the other even if it means more specification effort. And we still propose that both be Tier 1 views due to their overall importance. It would be better to adopt zip on its own and provide a new function adapter applied, leaving the door open to a better zip_transform in the future, than specify zip_transform in terms of zip and transform.

Another interesting example is transform_maybe. As we’ll see later, transform_maybe(E, F) can easily be specified in terms of three adapters today (a transform followed by a filter followed by a transform). But while tail can be made a little bit better as a standalone view, transform_maybe can be substantially improved.

Ultimately, this question of full view or not fill view is one that should guide review of this paper.

4.2 The zip family

The zip family of range adapters is an extremely useful set of adapters with broad applicability (and is now proposed in [P2321R2]). It consists of five user-facing range adapters:

1. zip
2. zip_transform — zip_with in range-v3
3. enumerate — enumerate(E) is roughly equivalent to zip(iota(0), E)
4. adjacent — adjacent(E) is equivalent to zip(E, E | drop(1))
5. adjacent_transform — is to adjacent what zip_transform is to zip

Indeed, we have many algorithms that exist largely because we don’t have zip (and prior to Ranges, didn’t have the ability to compose algorithms). We have several algorithms that have single-range-unary-function and a two-range-binary-function flavors. What if you wanted to ranges::transform 3 ranges? Out of luck. But in all of these cases, the two-range-binary-function flavor could be written as a single-range that is a zip of the two ranges, adjacent_difference is adjacent_transform, inner_product is zip_transform followed by accumulate, and so on and so on. This is why we think zip is the top priority view.

range-v3 uses the name zip_with, but here we are instead proposing zip_transform. The reason is that what we’re doing is, quite simply, a transform and in C++, we don’t really have a strong association of that with the _with suffix. Instead, we have algorithms like begins_with and concepts like swappable_with and totally_ordered_with, which have nothing to do with this sort of thing.

range-v3 implements zip and zip_with in terms of an underlying adaptor named iter_zip_with, which takes an n-ary invocable and n ranges and combines those into a single range whose values are the result of f(is...), where the is are the iterators into those ranges (note: iterators, not what they refer to). The size of an iter_zip_with is the minimum size of its ranges. The reference type is the type of f(*is...) while the value_type is V (described in more detail later along with the specific choices for Vzip_transform and Vzip used below).

But it turned out that these two views have enough differences that this doesn’t aid in the specification effort that much, and so [P2321R2] did not do it this way. Instead, zip_transform_view<F, V...> is specified in terms of a member zip_view<V...>.

Having those two, enumerate(E) is expression-equivalent to zip(index-view(E), E). We will discuss why index-view(E) instead of iota(range_size_t<decltype(E)>(0) later.

But we do not want to define adjacent(E) as zip(E, E | drop(1)). The primary reason to avoid doing this, and to make adjacent a first-class view type despite the added specification effort, is that it allows supporting move-only views. On top of that, it has the benefit of not having to store the view twice or the other cruft that drop has to store (see also the drop/tail discussion earlier).

Similar to how zip_transform_view<F, V...> is specified in terms of a member zip_view<V...>, adjacent_transform_view<V, F, N> is specified as having a member adjacent_view<V, N>.

In short, we get five extremely useful ranges largely from the price of two of them (plus a lot of boilerplate). Which is why we think they should be considered and adopted as a group.

But in order to actually adopt zip and friends into C++23, we need to resolve several problems.

4.2.1 A tuple that is writable

Consider the following:

std::vector<int> vi = /* ... */;
std::vector<std::string> vs = /* ... */;
ranges::sort(views::zip(vi, vs));

Does this operation make sense? Definitely! It would be very useful if this compiled. Unfortunately, as-is, it will not. We need to go back and understand why this won’t compile today and what we need to do to fix it.

In [range-v3.573], user Jarod42 pointed out that the following program used to compile, yet provide a non-sensical answer:

struct C
{
    explicit C(std::string a) : bar(a) {}

    std::string bar;
};

int main()
{
    std::vector<C> cs = { C("z"), C("d"), C("b"), C("c") };

    ranges::sort(cs | ranges::view::transform([](const C& x) {return x.bar;}));

    for (const auto& c : cs) {
        std::cout << c.bar << std::endl;
    }
}

The range was not sorted, the emitted output was still in the same order as the input… because we’re sorting a range of prvalue std::strings, and trying to swap prvalue std::strings makes little sense because it doesn’t do anything.

But the reason it compiled was that the constraints checked if the iterators were assignable-through, which in this case was equivalent to checking if std::string() = std::string() is a valid expression… and it, unfortunately, is. Assignment operators simply are not reference-qualified - they could not have been for a long time, and they are not now. The question became then - how can the library ensure that the above nonsense does not compile?

As discussed in [stl2.381]:

Which is how we ended up with the indirectly_writable (the concept formerly known as Writable) requiring const-assignability.

Hence, in order to make ranges::sort(zip(vi, vs)) compile, we need to make zip_view<R...>::iterator model indirectly_writable, which means we need to make std::tuple const-assignable. That is, adding the following assignment operators, appropriately constrained:

  // [tuple.assign], tuple assignment
  constexpr tuple& operator=(const tuple&);
+ constexpr tuple& operator=(const tuple&) const;
  constexpr tuple& operator=(tuple&&) noexcept(see below);
+ constexpr tuple& operator=(tuple&&) const noexcept(see below);

  template<class... UTypes>
    constexpr tuple& operator=(const tuple<UTypes...>&);
+ template<class... UTypes>
+   constexpr tuple& operator=(const tuple<UTypes...>&) const;
  template<class... UTypes>
    constexpr tuple& operator=(tuple<UTypes...>&&);
+ template<class... UTypes>
+   constexpr tuple& operator=(tuple<UTypes...>&&) const;

Or, rather than change std::tuple, we can have zip_view<R...>::value_type and zip_view<R...>::reference be an entirely different tuple type than std::tuple, introducing a second tuple type into the standard library: std2::tuple2. This just seems like a facially terrible idea, we already have one tuple type, we should just have it solve this problem for is.

We therefore propose that std::tuple<T...> be const-assignable whenever all of T... are const-assignable. And likewise for std::pair<T, U>, for consistency, the other proxy reference type in the standard libary: std::vector<bool>::reference.

4.2.2 A tuple that is readable

We encourage everyone to review Eric Niebler’s four-part series on iterators [niebler.iter.0] [niebler.iter.1] [niebler.iter.2] [niebler.iter.3], as this problem is covered in there in some depth.

There is a fundamental problem with standard library algorithms and how they interact with proxy iterators. One example used in the series is unique_copy:

// Copyright (c) 1994
// Hewlett-Packard Company
// Copyright (c) 1996
// Silicon Graphics Computer Systems, Inc.
template <class InIter, class OutIter, class Fn,
          class _Tp>
OutIter
__unique_copy(InIter first, InIter last,
              OutIter result,
              Fn binary_pred, _Tp*) {
  _Tp value = *first;
  *result = value;
  while (++first != last)
    if (!binary_pred(value, *first)) {
      value = *first;
      *++result = value;
    }
  return ++result;
}

std::vector<bool> vb{true, true, false, false};
using R = std::vector<bool>::reference;
__unique_copy(
  vb.begin(), vb.end(),
  std::ostream_iterator<bool>{std::cout, " "},
  [](R b1, R b2) { return b1 == b2; }, (bool*)0 );

if (!binary_pred(value, *first)) { /*...*/

The blog goes on to point out that one way to resolve this is by having the lambda take both parameters as auto&&. But having to require a generic lambda is a bit… much. This was the reason we have the idea of a common_reference. Rewriting the above to be:

using R = std::iter_common_reference_t<std::vector<bool>::reference>;
__unique_copy(
  vb.begin(), vb.end(),
  std::ostream_iterator<bool>{std::cout, " "},
  [](R b1, R b2) { return b1 == b2; }, (bool*)0 );

This now works. And that is now the requirement that we have for iterators, that they be indirectly_readable - which, among other things, requires that there be a common_reference between the iterator’s reference type and the iterator’s value_type&:

template<class In>
  concept indirectly-readable-impl =
    requires(const In in) {
      typename iter_value_t<In>;
      typename iter_reference_t<In>;
      typename iter_rvalue_reference_t<In>;
      { *in } -> same_as<iter_reference_t<In>>;
      { ranges::iter_move(in) } -> same_as<iter_rvalue_reference_t<In>>;
    } &&
    common_reference_with<iter_reference_t<In>&&, iter_value_t<In>&> &&
    common_reference_with<iter_reference_t<In>&&, iter_rvalue_reference_t<In>&&> &&
    common_reference_with<iter_rvalue_reference_t<In>&&, const iter_value_t<In>&>;

template<class In>
  concept indirectly_readable =
    indirectly-readable-impl<remove_cvref_t<In>>;

template<class I>
  concept input_iterator =
    input_or_output_iterator<I> &&
    indirectly_readable<I> &&
    requires { typename ITER_CONCEPT(I); } &&
    derived_from<ITER_CONCEPT(I), input_iterator_tag>;

How does this relate to zip?

Letting I be zip_view<R...>::iterator for some set of ranges R..., it just follows from first principles that iter_reference_t<I> should be std::tuple<range_reference_t<R>...> — dereferencing a zip iterator should give you a tuple of dereferencing all the underlying ranges’ iterators. And then it sort of follows from symmetry that iter_value_t<I> should be std::tuple<range_value_t<R>...>. We’ll discuss this in more depth in a later section.

But then what does iter_common_reference_t<I> end up being?

Let’s pick some concrete types. Taking our earlier example of:

std::vector<int> vi = /* ... */;
std::vector<std::string> vs = /* ... */;
ranges::sort(views::zip(vi, vs));

We have a value type of std::tuple<int, std::string> and a reference type of std::tuple<int&, std::string&>. The common reference of those exists: the reference type is convertible to the value type but not in the other direction, so the common reference is just the value type of std::tuple<int, std::string>. This might be odd, having a common reference type that has no reference semantics, but it does work. And in some cases you can’t really do better (as in the vector<bool> example from the blog series, the common reference is bool).

But where we really run into problems is with non-copyable types. If instead of zipping a std::vector<int> and a std::vector<std::string>, we changed the first range to be a std::vector<std::unique_ptr<int>>, what happens? We have a value type of std::tuple<std::unique_ptr<int>, std::string> and a reference type of std::tuple<std::unique_ptr<int>&, std::string&>, similar to before. But now, neither is convertible to the other.

The constructor overload set of std::tuple is… intense to say the least. But the relevant ones are:

constexpr explicit(see below) tuple();
constexpr explicit(see below) tuple(const Types&...);         // only if sizeof...(Types) >= 1
template<class... UTypes>
  constexpr explicit(see below) tuple(UTypes&&...);           // only if sizeof...(Types) >= 1

tuple(const tuple&) = default;
tuple(tuple&&) = default;

template<class... UTypes>
  constexpr explicit(see below) tuple(const tuple<UTypes...>&);
template<class... UTypes>
  constexpr explicit(see below) tuple(tuple<UTypes...>&&);

template<class U1, class U2>
  constexpr explicit(see below) tuple(const pair<U1, U2>&);   // only if sizeof...(Types) == 2
template<class U1, class U2>
  constexpr explicit(see below) tuple(pair<U1, U2>&&);        // only if sizeof...(Types) == 2

We have a converting constructor from std::tuple<U...> const&, viable if (constructible_from<T, U const&> && ...), and a converting constructor std::tuple<U...>&&, viable if (constructible_from<T, U&&> && ...). In both cases, we’re just distributing the qualifiers.

When trying to construct a std::tuple<std::unique_ptr<int>, std::string> from a std::tuple<std::unique_ptr<int>&, std::string&>, we reject the converting constructor of lines 9-10 because we can’t construct a std::unique_ptr<int> from a std::unique_ptr<int> const&. std::unique_ptr isn’t copyable, and that’s not going to change.

When trying to construct a std::tuple<std::unique_ptr<int>&, std::string&> from an lvalue std::tuple<std::unique_ptr<int>, std::string> (the fact that it’s an lvalue is important), we reject that very same converting constructor because we can’t construct a std::unique_ptr<int>& from a std::unique_ptr<int> const&. Can’t bind a non-const lvalue reference to a const lvalue. But we can of course bind a non-const lvalue reference to a non-const lvalue.

And indeed that’s how close this is to working. All we need is one more constructor (although we added two here for completeness):

  constexpr explicit(see below) tuple();
  constexpr explicit(see below) tuple(const Types&...);         // only if sizeof...(Types) >= 1
  template<class... UTypes>
    constexpr explicit(see below) tuple(UTypes&&...);           // only if sizeof...(Types) >= 1

  tuple(const tuple&) = default;
  tuple(tuple&&) = default;

+ template<class... UTypes>
+   constexpr explicit(see below) tuple(tuple<UTypes...>&);
  template<class... UTypes>
    constexpr explicit(see below) tuple(const tuple<UTypes...>&);
  template<class... UTypes>
    constexpr explicit(see below) tuple(tuple<UTypes...>&&);
+ template<class... UTypes>
+   constexpr explicit(see below) tuple(const tuple<UTypes...>&&);

  template<class U1, class U2>
    constexpr explicit(see below) tuple(const pair<U1, U2>&);   // only if sizeof...(Types) == 2
  template<class U1, class U2>
    constexpr explicit(see below) tuple(pair<U1, U2>&&);        // only if sizeof...(Types) == 2

If only we had a way to express “a forwarding reference to tuple<UTypes...>” in the language. But if we add these constructors, then suddenly we can construct a std::tuple<std::unique_ptr<int>&, std::string&> from an lvalue std::tuple<std::unique_ptr<int>, std::string>. And that would just end up binding the references as you would expect.

Such a change to the constructor set of std::tuple means that all of our zip_view iterators can actually be indirectly_readable, which means they can actually count as being iterators. In all cases then, the common reference type of zip iterators would become the reference type. Indeed, this even fixes the issue we mentioned earlier - where even when our underlying types were copyable, we originally ended up with a common reference type of std::tuple<int, std::string>, a type that does not have reference semantics. But now it would have a common reference type of std::tuple<int&, std::string&>, which certainly has reference semantics.

We therefore propose that to extend the constructor overload set of std::tuple<T...> to add converting constructors from std::tuple<U...>& and std::tuple<U...> const&&. And likewise for std::pair<T, U>, for consistency.

4.2.3 zip and zip_transform’s value_type

Returning to our favorite example again:

std::vector<int> vi = /* ... */;
std::vector<std::string> vs = /* ... */;

auto a = views::zip(vi, vs);

Let’s talk about a. The reference type of a is std::tuple<int&, std::string&>. That’s really the only option, it’s the whole point of zip. range_reference_t<zip_view<R...>> needs to be std::tuple<range_reference_t<R>...>.

But what’s the value_type of a? We ideally want the value_type to be something without reference semantics, something that we can properly hold onto and have a real copy. For a lot of ranges, the reference type is some T& or T const& and so the value_type is just T. But here, our reference is a prvalue. So we have a choice.

We could do std::remove_cvref_t on the reference as usual, that would give us just reference back, so the value_type of a would be std::tuple<int&, std::string&>. Not really an independent, value type.

Or, since we know what zip is, we don’t have to guess what a good value_type might be. We could use the ranges themselves to tell us what that is. Each constituent R already provides a range_value_t<R>, and if those choices are good enough for the Rs, they should be good enough for zip. That is, std::tuple<range_value_t<R>...>. Which, for a, would be std::tuple<int, std::string>.

But there’s a wrinkle here, consider:

auto b = views::zip_transform([](auto&... r){
    return std::tie(r...);
}, vi, vs);

The reference type of b is necessarily determined by the callable here: invoke_result_t<F&, range_reference_t<R>...>. In this case, this gives us std::tuple<int&, std::string&>. Notably, this is exactly the same reference type as with saw with a.

But what’s the value_type of b? Unlike in the case of zip, with zip_transform we really have no idea where the reference type came from. It need not be any kind of reference at all, it could be… int. For zip_transform, we really can’t do much better than remove_cvref_t<invoke_result_t<F&, range_reference_t<R>...>> — which again gets us back to the same std::tuple<int&, std::string&>.

A hypothetical different direction would be to introduce a type trait that would inform range adapters how to turn a reference-semantic type to a value type. Something that would turn std::vector<bool>::reference into bool, or std::tuple<T&...> into std::tuple<T...>. Then other range adapters could have used it themselves.

But views::transform already exists, and is very similar in nature to views::zip_transform. Indeed, views::zip_transform(F, E...) is very nearly views::zip(E...) | views::transform([=](auto&& tup){ return std::apply(F, std::forward<decltype(tup)>(tup)); }), so any attempt to make zip_transform’s value_type line up with zip’s would mean changing the existing behavior of views::transform. That makes it unviable to pursue (assuming it were even a good idea to begin with).

The other way to get zip_transform’s value_type to be consistent with zip’s is to abandon the aforementioned symmetry and just use remove_cvref_t to determine zip’s value_type as well. But we find this questionable — we shouldn’t sacrifice zip at the altar of consistency. It’s really not that big of a deal, it’s an inconsistency that only really surfaces when users would use zip_transform to do exactly what zip already does. But why would they do that, when they have zip?

In short, we propose that:

Or for this specific example:

We think these would be the most valuable choices.

4.2.4 enumerate’s first range

We wrote earlier that enumerate(r) can be defined as zip(iota(range_size_t<R>(0)), r), but it turns out that this isn’t quite right, and we need to do something slightly different.

It turns out iota is a fairly complicated view due to wanting to avoid undefined behavior in its difference_type [P1522R1]. iota_view has to choose a type that is wide enough to properly compute differences. One of the important points in that paper is that integer-like types are:

Similarly, iota(range_size_t<R>(0)) need not be valid [range-v3.1141]. And, even if it were valid, it may be a wider integer type than would be strictly necessary. But enumerate is not as general-purpose as iota. From Eric Niebler:

And this is what range-v3 does: enumerate(r) is defined as zip(index-view<range_size_t<R>, range_difference_t<R>>(), r), where index-view<S, D> is basically a specialized version of iota such that range_size_t<index-view<S, D>> is S and range_difference_t<index-view<S, D>> is D. That is, rather than trying to compute a size and difference types to fit the range, we just use the provided range’s size and difference types. If it’s good enough for R, it’s good enough for enumerate_view<R>!

This index-view can be exposition-only, it’s effectively an implementation detail of enumerate.

4.2.5 Does adjacent mean 2 or n?

In C++20, we have the range adapters keys and values which are actually specified as elements<0> and elements<1>, respectively, where elements<N> is a generic range adapter that picks the Nth part from a range of tuples.

Now consider adjacent. This view could simply mean to take elements two-at-a-time, taking a range of T and producing a range of (T, T) (as a tuple). But there isn’t anything particularly special about two, just that it’d probably be the most used value. There’s not much additional specification effort to create a range adapter that takes elements n-at-a-time and produces a range of n-tuple. In that case, we could specify adjacent as slide_as_tuple<2> (this closely resembles the algorithm slide described later, the difference being that here we need the value as a constant expression to produce a range of tuples, while there we produce a range of ranges). Alternatively, adjacent itself could be the generic algorithm and we could introduce a specialized name to mean adjacent<2>. For instance, Python calls this pairwise and Kotlin calls it zipWithNext.

4.3 The group_by family

This family, as the name suggests, take a range of T and groups them based on some provided function function. group_by is one of the most consistently named algorithms across all languages (modulo choice of spelling, as in groupBy or group-by) yet there are actually three-ish different approaches to what this algorithm actually means:

1. Take a binary predicate, (T, T) -> bool, and invoke this predicate on consecutive elements and start a new group when that predicate returns false. Using Haskell notation, we’re taking a [T] (range of T) and producing a [[T]] (range of range of T).
2. Take a unary function, T -> U (such that U models equality_comparable), and group consecutive elements with the same U. Following the law of useful return, these algorithms don’t just give you a [[T]] back, they rather give you a [(U, [T])] — the algorithm had to compute the Us for each element so they should give it to the user.
3. Take a unary function, T -> U, and return a dictionary that maps every U to a list of Ts that mapped to it.

Haskell, Elixir, D (chunkBy), and range-v3 (~ish) provide the first kind. Rust, Python, D (also chunkBy — it allows both uses), and F# provide the second. Clojure, Kotlin, and Scala provide the third.

Swift recently announced its own set of algorithms [swift.algorithms]. It provides the first kind as chunked(by: f) and the second kind as chunked(on: f) (Swift allows overloading based on named function arguments).

range-v3 is mostly in the first category, except its implementation choice is quite different from the other languages. It always compares the first element in each subrange with each subsequent one, while the others always compare consecutive elements. As such, they may yield very different results:

>>> groupBy (<=) [1,2,2,3,1,2,0,4,5,2]
[[1,2,2,3],[1,2],[0,4,5],[2]] -- Haskell's implementation
[[1,2,2,3,1,2],[0,4,5,2]]     -- range-v3's implementation

In Haskell, the second 1 starts a new group because we’re comparing it with its previous element and 3 <= 1 is false. But in range-v3, the second 1 does not start a new group because we’re comparing it with the first element of the group, and 1 <= 1 is true. We think the Haskell/Elixir/D choice is more familiar and more useful.

It’s also worth noting that technically Haskell has two different groupBy functions: Data.List.groupBy (which does what range-v3 does) and Data.List.GroupBy.groupBy (which does what we’re stating Haskell’s implementation really is). This newer one is even called the “Replacement definition” in its docs [haskell.groupby].

The question is which one of the three options would we want to pick for C++Next?

Well, when it comes to algorithms, the more the better. We think it’s clear we wouldn’t want to pick the 3rd option (we can easily produce a dictionary from the 2nd option), so the question is between the first two. While the binary version of group_by is more generic (since you approximate the unary version in terms of it, even it’s a different shape) and thus more broadly applicable, the unary version also comes up frequently and as such we feel that we should provide both.

We could hypothetically follow the D model and provide both under the same name, selecting based on whether the provided callable is a unary invocable or a binary predicate — but we’re not sure if that’s the best idea.

Given the time and bandwidth pressure, we think the top priority is the binary group_by and the unary form, while still very useful, should be a Tier 2 addition.

As far as naming goes, our preferred naming is:

• chunk_by takes a binary predicate
• chunk_on (or perhaps chunk_by_key or chunk_on_key) takes a unary transform and produces a range of pairs (as D, Rust, and Python do, but Swift does not)

This would give us three range adaptors that produce non-overlapping ranges of ranges that include every element of the original range exactly once:

• chunk, which takes a number (described here)
• chunk_by, which takes a binary predicate
• chunk_on (or whatever), which takes a unary projection

And we think that it’s nice that all of these algorithms have the same root. There are other algorithms that produces ranges of ranges, but they either exclude some elements (split) or repeat some elements (slide).

Additionally, just recently, range-v3 just added a views::chunk_by that does exactly as suggested here (comparing consecutive elements, as opposed to range-v3 preexisting views::group_by which compares against the first in group).

This is proposed in [P2443R0].

4.4 Monadic binds

We added views::transform in C++20, but there are closely related views in that family, which several other languages also provide.

views::transform takes a range of T and a function T -> U and produces a range of U. But we can play around with the shape of the callable to produce two other extremely useful adapters:

• we can take a function T -> RangeOf<U> and produce a range of U. That is, take the resulting range and flatten it out into a single range.
• we can take a function T -> optional<U> and produce a range of U from those resulting optionals that are engaged.

The former is commonly known as flat_map (because it’s a map followed by a flatten), although C++20’s version of flatten is named join and C++20’s version of map is named transform. So perhaps this adapter should be named join_transform or transform_join? Eughh?

The latter is called filter_map in Rust and compactMap in Swift. Neither strike us as great names either. A Haskell package calls this mapMaybe which informs our proposed name: transform_maybe.

There really aren’t any particular thorny library issues to resolve here, simply a question of specification.

4.4.1 flat_map

flat_map(E, F) is, following the adoption of [P2328R1], exactly join(transform(E, F)).

Prior to that paper, it used to be the case that if the callable returned a prvalue range that is not a view (a seemingly specific constraint that is actually a very common use-case - consider a function returning a vector<int>), then the join would fail. The workaround for this was a range adaptor in range-v3 called cache1, but that adaptor has other design issues (described in the above paper) and as a result is not considered a high priority right now.

Given that, we could specify views::flat_map(E, F) as expression-equivalent to views::join(views::transform(E, F)). It’s not clear that there is a more efficient way to implement this (unlike the case of, say, views::tail vs views::drop(1) described earlier), so we could add this as a trivial alias. We don’t have examples of aliases like this in the standard library today (keys is an alias for elements<0>, but that’s still a single adaptor).

4.4.2 transform_maybe

For transform_maybe, [P1255R6] seeks to address this problem but requires using three chained adapters:

inline constexpr auto transform_maybe1 = [](auto&& f){
    return views::transform(FWD(f))
         | views::transform(views::maybe)
         | views::join;
};

This is an expensive implementation. Not only do we need three adapters, but join is a very complex adapter and we have an extremely specialized case here that is much simpler. Moreover, the result of transform_maybe1 is always an input range only (we are joining a range of prvalue ranges).

We could get the same behavior out of three simpler adapters in a different way in C++20:

inline constexpr auto transform_maybe2 = [](auto&& f){
    return views::transform(FWD(f))
         | views::filter([](auto&& e) -> decltype(static_cast<bool>(e)) {
               return static_cast<bool>(e);
           })
         | views::transform([](auto&& e) -> decltype(decay-copy(*FWD(e))) {
               return decay-copy(*FWD(e));
           });
};

This implementation can now potentially be a bidirectional range (instead of input-only) thanks to avoiding join, but it still uses three adapters.

Both of these implementations have the issue of doing unnecessary extra copies. Let’s say we have a range of T and a bunch of example functions, what would we want the resulting filter_map’s reference type to be?

The maybe implementation always yields lvalue references, the transform-filter-transform implementation always yields prvalues. The latter is predictable - we always copy out - whereas the former doesn’t need to copy the D, although it does copy the B despite perhaps looking as if it does not (it does copy the C, and needs to, although it likewise might appear as if it does not).

We can provide the desired result with a more complex version of the final transform by only decaying xvalues:

inline constexpr auto transform_maybe3 = [](auto&& f){
    return views::transform(FWD(f))
         | views::filter([](auto&& e) -> decltype(static_cast<bool>(e)) {
               return static_cast<bool>(e);
           })
         | views::transform([](auto&& e) requires requires { *e; } -> decltype(auto) {
               if constexpr (std::is_rvalue_reference_v<decltype(*FWD(e))>) {
                   return decay-copy(*FWD(e));
               } else {
                   return *FWD(e);
               }
           });
};

This is certainly quite a bit more complicated than the views::tail implementation suggested earlier!

But we don’t want to specify it like that either. Even transform3 has a huge problem: how many times do we invoke the callable? Ideally, if we’re just traversing the resulting range one time, we’d invoke the function one time per element in the input range. But that’s not actually the case here - we would have to end up invoking the function twice in the case that it yields an engaged optional. This follows directly from the underlying iterator model: the transform_view’s iterator::operator* invokes the function, while filter_view’s iterator::operator++ does a find_if. For elements that are filtered in, there would be one dereference during the operator++ to stop searching and then again to actually propagate the value in the filter_view’s iterator::operator*. This could be resolved by adding yet another adapter that we already mentioned:

inline constexpr auto transform_maybe4 = [](auto&& f){
    return views::transform(FWD(f))
         | views::cache_latest
         | views::filter([](auto&& e) -> decltype(static_cast<bool>(e)) {
               return static_cast<bool>(e);
           })
         | views::transform([](auto&& e) requires requires { *e; } -> decltype(auto) {
               if constexpr (std::is_rvalue_reference_v<decltype(*FWD(e))>) {
                   return decay-copy(*FWD(e));
               } else {
                   return *FWD(e);
               }
           });
};

We think that transform_view merits a first-class view to accomplish this functionality not only because the above is very involved but also because it still has unnecessary overhead - it’d be nice to avoid instantiating four views when one is sufficient, along with all the wrapping that entails.

However, because of the cache_latest dependency (see also [P2328R1]), we’re kicking this one down to Tier 2.

4.5 The sliding family

Conor talks about this family of ranges in a CppCon 2019 lighting talk [hoekstra.cppcon].

• chunk(N) breaks a range into non-overlapping ranges of length N. views::iota(0,10) | views::chunk(4) yields [[0,1,2,3],[4,5,6,7],[8,9]]. Note that the last range has length less than 4. See [P2442R0].
• slide(N) is very similar to chunk except its subranges are overlapping and all have length exactly N. views::iota(0,10) | views::slide(4) yields [[0,1,2,3],[1,2,3,4],[2,3,4,5],[3,4,5,6],[4,5,6,7],[5,6,7,8],[6,7,8,9]]. Note that slide(2) is similar to adjacent, except that the latter yields a range of tuples (i.e. having compile-time size) whereas here we have a range of ranges (still having runtime size). range-v3 calls this sliding, which has a different tense from the other two, so we change it to slide here. See [P2442R0].
• stride(N) takes every Nth element. views::iota(0, 10) | views::stride(4) yields [0,4,8]. Note that unlike the other two, this one is not a range of ranges, but still fits in with this family. See [P1899R2].

These are three specific examples of a general algorithm that takes three parameters: the size of the subranges to return, the size of the step to take after each subrange, and whether to include partial ranges. Kotlin calls this algorithm windowed, Scala calls it sliding, D calls it slide, Haskell calls it divvy, and Clojure calls it partition.

The above table isn’t quite right - since stride does not give you a range of ranges, so it would unfortunately not be implementable in terms of generic. And as with tail vs drop, we have the question here of should chunk and slide each be first-class views or should they both be implemented in terms of generic? Implementing in terms of generic saves specification effort and gives us a more generic algorithm, but means we would have to store two extra data members than would be necessary in first-class implementation.

Moreover, as a language without named arguments, we have a different problem when it comes to generic here. It takes two ints and a bool. There is no natural order for these parameters, so who knows what generic(1, 4, false) means — especially since generic(false, 1, 4) would also compile. This suggests simply not having it as a user-facing algorithm. Or we could use an aggregate to mock up named arguments via designated-initializers, as in generic({.step=1, .size=4, .partial=false}). This is a very useful pattern, but one which has no precedent in the standard library as of this writing.

Ultimately, we don’t think an algorithm like generic would necessarily be useful for C++, and it wouldn’t really help much in specifying either chunk or slide (and definitely not stride). But these are important algorithms that come up frequently enough to be in consideration for Tier 1.

4.6 The take/drop family

In C++20 already we have several views that pass through some subset of the initial range — without modifying any of the elements. Those are: take, take_while, drop, and drop_while. There are actually many more algorithms in this family that are all quite similar. Nearly all of these range adapters can be implemented in terms of adapters that already exist, although we can typically do better if we make them all first-class. The question is really what is it that we want to do here?

We already discussed the example of tail earlier — should this be a first-class view or is drop(1) sufficient? The same question applies to most of the views in this list, and we generally have the same answer for all of them: if we’re okay with derivative implementations, then we might as well make all of them Tier 1 since they would all have single-sentence specifications; but if we want better implementations, then they’re certainly not important enough to gain get top priority, so we would move them down to Tier 2 or Tier 3.

The potential adoption of |> as a language feature [P2011R1] also affects the calculus here, as most of these could also be implemented as simple functions and relying on |> instead of | to do the piping. For example, tail could be implemented ([P1739R4] notwithstanding):

template <viewable_range R>
auto tail(R&& range) {
    auto b = ranges::begin(range);
    auto e = ranges::end(range);
    if (b != e) {
        ++b;
    }
    return subrange(b, e);
}

We’ll go through the other potential range adapters in this family and discuss how they could be implemented in terms of existing adapters:

• take_last(N) and drop_last(N). views::take_last(N) is equivalent to views::reverse | views::take(N) | views::reverse. But this is somewhat expensive, especially for non-common views. For random-access, sized ranges, we’re probably want r | views::take_last(N) to evaluate as r | views::drop(r.size() - N), and that desire is really the crux of this whole question — is the equivalent version good enough or should we want to do it right?
• take_last_while(P) and drop_last_while(P). These likewise could be implemented in terms of double-reverse, but take_last_while could not be implemented in terms of drop_while.
• take_exactly(N) and drop_exactly(N). These are similar to take and drop except not checked. iota(0, 3) | take(5) is a valid empty range, while iota(0, 3) | take_exactly(5) is undefined behavior.
• slice(M, N) is equivalent to views::drop(M) | views::take(N - M), and you couldn’t do much better as a first class view. range-v3 also supports a flavor that works as views::slice(M, end - N) for a special variable end, which likewise be equivalent to r | views::drop(M) | views::drop_last(N).
• head is equivalent to views::drop_last(1).
• tail is equivalent to views::drop(1).
• trim(P) is equivalent to views::drop_while(P) | views::drop_last_while(P).
• delimit(V) has two flavors. When called with a range, r | views::delimit(V) is equivalent to r | views::take_while([V](auto&& e) { return !(e == V); }). But it also allows wrapping an iterator, such that views::delimit(it, V) is equivalent to subrange(it, unreachable_sentinel) | views::delimit(V).

We’re tentatively labelling the more complicated ones here Tier 2 and the more trivial (i.e. head, tail, and slice) and possibly less needed (i.e. meow_exactly) ones Tier 3.

4.7 Generative factories

There are several views on the list that are simply factories — they cannot be piped into. So we’ll consider them as their own family:

• cartesian_product(E...) takes a bunch of ranges and yields a range of tuples that are the Cartesian product of those ranges.
• concat(E...) concatenates a bunch of ranges together, it must be a standalone range. It is also sometimes called chain.
• generate(F) takes a nullary function F and produces an infinite range of invoking that function.
• generate_n(F, N) is equivalent to generate(F) | views::take(N).
• linear_distribute(B, E, N) produces a range of N values linearly distributed from B to E.
• repeat(V) is an infinite range of a single value, equivalent to generate([V]{ return V; }).
• repeat_n(V, N) is N copies of V, equivalent to generate_n([V]{ return V; }, N).

These vary wildly in complexity (repeat is certainly far simpler than cartesian_product). But cartesian_product comes up sufficiently often and are sufficiently complicated to merit Tier 1 priority.

The rest, we consider lower priority. And generate and generate_n in particular need special care to deal with 16.4.6.10 [res.on.data.races]. The current implementation of generate_n in range-v3 has a data race.

4.8 Other view adapters

Other range adapters that we haven’t talked about yet, but aren’t sure how to group exactly, are:

• adjacent_filter(P) is an extension of filter that rather than taking a unary predicate and going one element at a take takes a binary predicate and goes pairwise through the elements. Similar to adjacent | filter(applied(P)) | views::keys except that it always keeps the first element.
• adjacent_remove_if(P) is similar to adjacent_filter(not_fn(P)), except that it always keeps the last element.
• cycle(R) produces an infinite ranges that, well, cycles through R repeatedly.
• scan(R, F, V) is the lazy view version of std::inclusive_scan, except not having a defaulted binary operation.
• intersperse(V) produces a new range alternating selecting elements from the source range and the value V
• join_with(V). C++20 has a version of join that does not take a delimiter, but we really do need a version that provides one as well. The issue with taking a delimiter is that there is an ambiguity with what r | views::join(v) means, if v happens to itself be a joinable range. range-v3 assumes that if v is a joinable range that views::join(v) joins it without a delimiter. We think this ship has sailed in C++20, and it would be better to introduce join_with that requires a delimiter. See [P2441R0].
• partial_sum(R) is equivalent to scan(R, std::plus<>()).
• split_when(P) is a more complicated version of split that rather than taking a value or a range, instead takes a predicate that could also return an iterator.
• sample(N) yields a random sample of the given length.

There are other combinatoric generators that also could be explored. For example, Python has itertools.product, itertools.combinations, and itertools.combination_with_replacement which all operate on a single range of T and produce a range of range of T.

Of these, views::join_with fills in an incomplete aspect of the already-existing views::join, so we feel that it is a Tier 1 view. The rest we consider to have lower priority.

4.9 Derivatives of transform

Several of the above views that are labeled “not proposed” are variations on a common theme: addressof and indirect are basically wrappers around transform that take std::addressof and std::dereference (a function object we do not have at the moment), respectively. Basically, but not exactly, since one of those functions doesn’t exist yet and the other we can’t pass as an argument anyway.

But some sort of broader ability to pass functions into functions would mostly alleviate the need for these. views::addressof is shorter than views::transform(LIFT(std::addressof)) (assuming a LIFT macro that wraps a name and emits a lambda), but we’re not sure that we necessarily need to add special cases of transform for every useful function.

There are two that stand out as being slightly different though.

4.9.1 views::as_const

views::as_const isn’t quite the same as a transform over std::as_const, because of the existence of proxy references. std::as_const only accepts lvalues, so something like:

std::vector<int> v;
views::zip(v) | views::transform(LIFT(std::as_const));

would not compile. And were it to compile, what should it actually mean? zip’s reference type here, as previously discussed, should be std::tuple<int&>. What would a const view over this range mean? Should we transparently propagate prvalues, thereby being a shallow const, and produce a new range whose reference is std::tuple<int&>? Or should we somehow come up with a way to do deep const-ness here and yield a range whose reference is std::tuple<int const&>? The latter noting that we are not doing this sort of introspection for views::zip_transform.

In range-v3, the reference type is common_reference_t<range_value_t<R> const&&, range_reference_t<R>>. In this particular example, that would be std::tuple<int const&> (following the various tuple changes performed to implement zip in [P2321R2]), which is exactly what you want.

Having a const view over a range is something that seems inherently useful and is more complex than simply a transform over std::as_const, and has proven to be in high demand. The full design is explored in [P2278R2] and is Tier 1 material.

4.9.2 views::as_rvalue

Similarly, views::as_rvalue ([P2446R2], renamed from views::move following a long discussion) isn’t quite the same as a transform over std::move, both because of proxy references (where std::move isn’t the right operation to do, since we don’t want to end up with an rvalue reference to a proxy reference) and prvalues (where it’s already a prvalue, so we don’t need to std::move it).

This is one of the easiest range adaptors to specify, since we already have std::move_iterator<I> which already does the right thing. Typically, the challenge in specifying range adaptors is getting the iterator right. We don’t have to do that here. It’s also fairly imporant in the context of ranges::to. Given both the ease of specification and its value, seems important to have this adaptor sooner.

5 Algorithms

The largest chunk of C++20 Ranges were the algorithms, and the work here has been very thorough. All the <algorithm>s have been range-ified, which has been fantastic.

But there are a few algorithms that aren’t in <algorithm> that do not have range-based versions: those that are in <numeric>. These are often the last algorithms considered for anything, they were the last algorithms that were made constexpr ([P1645R1]) and now are the last to become range-based. They are:

What to do about these algorithms? Well, one of the big motivations for Ranges was the ability to actually compose algorithms. This severely reduces the need for the combinatorial explosion of algorithms - all the transform_meow algorithms are transform followed by meow, so we probably don’t need separate range-based algorithms for those.

Four of these (accumulate, reduce, transform_reduce, and inner_product) return a value, while the other seven output a range (one through a pair of writable iterators and the other six through an output iterator). We’ll consider these separately.

5.1 Algorithms that Output a Value (Catamorphisms)

5.1.1 std::accumulate → ranges::fold

We think having a range-based left-fold algorithm in the standard library is very important, since this is such a fundamental algorithm. Indeed, several of the other standard library algorithms are simple folds — for instance count, count_if, max_element, min_element, minmax_element, and inner_product. We don’t have a generic range-based max or min (just ones that takes an initializer_list), but those would also be a left-folds. As such , we think adding such a left-fold to the standard library is a top tier priority for C++23. Except that we think this algorithm should be named ranges::fold - the problem with the name accumulate is that it is strongly suggestive of addition, which makes uses of it over different operations just very strange. fold is what the algorithm is, and has no such emphasis. It’s the more generic name, for the most generic algorithm.

[P1813R0] goes through the work of introducing a set of constraints for these algorithms, and its suggestion for this algorithm is:

template <input_range R, movable T, class Proj = identity,
          indirect_magma<const T*, projected<iterator_t<R>, Proj>, T*> BOp = ranges::plus>
constexpr accumulate_result<safe_iterator_t<R>, T>
    accumulate(R&& r, T init, BOp bop = {}, Proj proj = {});

We think this is a bad direction, for three reasons.

First, we should not default the binary operation at all. Having a default fold operation doesn’t make much sense - it’s reasonable for ranges::sort to default to sorting by <, since the entire standard library is built on < as the primary comparison operator, but that doesn’t really hold for +. Instead, we should add separate named algorithms ranges::sum and ranges::product that just invoke ranges::fold with std::plus() and std::multiplies() – or more likely that these invoke ranges::reduce instead as the more efficient algorithm with more constraints.

Second, the above definition definitely follows Alexander Stepanov’s law of useful return [stepanov] (emphasis ours):

But it makes the usage of the algorithm quite cumbersome. The point of a fold is to return the single value. We would just want to write:

int total = ranges::sum(numbers);

Rather than:

auto [_, total] = ranges::sum(numbers);

or:

int total = ranges::sum(numbers, 0).value;

ranges::fold should just return T. This would be consistent with what the other range-based folds already return in C++20 (e.g. ranges::count returns a range_difference_t<R>, ranges::any_of - which can’t quite be a fold due to wanting to short-circuit - just returns bool).

Third, these constraints are far too restrictive. Copying the proposed definition of magma and indirect_magma here for readability:

// section 3.2.2 from P1813R0
template <class BOp, class T, class U>
concept magma =
    common_with<T, U> &&
    regular_invocable<BOp, T, T> &&
    regular_invocable<BOp, U, U> &&
    regular_invocable<BOp, T, U> &&
    regular_invocable<BOp, U, T> &&
    common_with<invoke_result_t<BOp&, T, U>, T> &&
    common_with<invoke_result_t<BOp&, T, U>, U> &&
    same_as<invoke_result_t<BOp&, T, U>, invoke_result_t<BOp&, U, T>>;

// section 3.2.11 from P1813R0
template <class BOp, class I1, class I2, class O>
concept indirect_magma =
    readable<I1> &&
    readable<I2> &&
    writable<O, indirect_result_t<BOp&, I1, I2>> &&
    magma<BOp&, iter_value_t<I1>&, iter_value_t<I2>&> &&
    magma<BOp&, iter_value_t<I1>&, iter_reference_t<I2>&> &&
    magma<BOp&, iter_reference_t<I1>, iter_value_t<I2>&> &&
    magma<BOp&, iter_reference_t<I1>, iter_reference_t<I2>> &&
    magma<BOp&, iter_common_reference_t<I1>, iter_common_reference_t<I2>>;

We see here again the heavy association of plus with accumulate, hence again the desire to rename the algorithm to fold. But the important thing to consider here is the requirement that the binary function need be invokable on each type and that there need be a common type for the result. We’ve already been through this process with the ranges comparison algorithms in [P1716R3] and removed those restrictions.

Consider a simple fold counting the occurences of a string (i.e. how you would implement ranges::count with ranges::fold):

std::vector<std::string> words = /* ... */;
int n = ranges::fold(words, 0, [](int accum, std::string const& w){
    return accum + (w == "range");
});

Such an algorithm would not meet the requirements laid out in P1813. There’s no common type between int and string, that lambda is only invocable with one of the possible four orders of arguments. But it’s a perfectly reasonable fold. Instead, the only allowed implementation would be:

int n = ranges::fold(words, 0, ranges::plus{}, [](std::string const& w) { return w == "ranges"; });

But we’re hard-pressed to explain why this would be considered better. In the general case, there may not even be an allowed implementation. Consider wanting to score a word in Scrabble. In Scrabble, each letter has a value but each tile can either multiply the score of a single letter or multiple the score of the whole word. One way to compute the score then is to use two folds, one to figure out the world multiplier and another to figure out the letter sum:

struct Square { int letter_multiplier, word_multiplier; };
vector<Square> squares = /* ... */;
vector<int> letters = /* ... */;

int score = fold(squares, 1, multiplies(), &Square::word_multiplier)
          * fold(zip_transform(multiplies(),
                          squares | views::transform(&Square::letter_multiplier),
                          letters),
                 0, plus());

Another way is to keep a running sum of the two parts separately, and do a manual multiply:

struct Accum {
    int result() const { return total * multiplier; };
    int multiplier, total;
};
int score = fold(zip(squares, letters), Accum(), [](Accum a, auto const& sq_let){
        auto [sq, letter] = sq_letter;
        return Accum{
            .multiplier = a.multiplier * sq.word_multiplier,
            .total = a.total + sq.letter_multiplier * letter
        };
    }).result();

We’re not trying to argue that the second solution is necessarily better than the first - merely that it is a perfectly adequate solution, that happens to not be able to meet the constraints as laid out in P1813.

Instead, we suggest a much lighter set of restrictions on fold: simply that this is a binary operation:

template <class F, class T, class U>
concept foldable =
    regular_invocable<F&, T, U> &&
    convertible_to<invoke_result_t<F&, T, U>, T>;

template <class F, class T, class I>
concept indirectly-binary-foldable =
    indirectly_readable<I> &&
    copy_constructible<F> &&
    foldable<F, T, iter_value_t<I>> &&
    foldable<F, T, iter_reference_t<I>> &&
    foldable<F, T, iter_common_reference_t<I>>;

template <input_range R, movable T, class Proj = identity,
    indirectly-binary-foldable<T, projected<iterator_t<R>, Proj>> BinaryOperation>
constexpr T fold(R&& r, T init, BinaryOperation op, Proj proj = {}) {
    range_iterator_t<R> b = begin(r);
    range_sentinel_t<R> e = end(r);
    for (; b != e; ++b) {
        init = op(std::move(init), proj(*b));
    }
    return init;
}

For more on this fold, along with several other fold algorithms, see [P2322R4].

5.1.2 ranges::reduce

We have this interesting situation in the standard library today where std::accumulate has a name strongly suggestive of addition, yet because it’s specified to invoke its binary operation serially, it has no additional requirements on that operation. But we also have std::reduce, which is a much more generic name with no suggested underlying operation, yet has very strong semantic constraints on its operation: it must be both associative and commutative. This comes from [N3408], emphasis ours:

While ranges::fold should have minimal constraints, that is not the case for a future ranges::reduce. As with std::reduce, we would need to enforce that the binary operation is both associative and commutative. This calls for the kinds of constrains that [P1813R0] is proposing. As it is a more complex set of constraints, we suggest that this is a Tier 2 algorithm, with no default operation. Given the previous suggestion of ranges::fold not having a default operation either, we also suggest the addition of a ranges::sum and a ranges::product that simply invoke ranges::reduce with std::plus() and std::multiplies(), respectively, with an initial value defaulted to range_value_t<R>() and range_value_t<R>{1}, respectively.

The naming here is somewhat problematic. reduce is, in general, a much better name than accumulate as it does not have any particular operation connotation. But it has additional requirements on the operation. With the suggested change in name, we would end up having both fold and reduce — names that seem synonymous and interchangeable, though they are not. We feel that this is probably okay though, since people already frequently think reduce is “just” the parallel version of accumulate and perhaps having fold and reduce both would make users more likely to consult the documentation?

5.1.3 ranges::transform_reduce and ranges::inner_product

These two algorithms are different from the previous two in that they are less fundamental. transform_reduce is a binary transform followed by reduce while inner_product is a binary transform followed by accumulate. First, inner_product, much like accumulate, is a bad name for the algorithm as it strongly prejudices product as the binary transform operation and as such uses of the algorithm with any other function simply look bizarre. From the cppreference example for inner_product:

#include <numeric>
#include <iostream>
#include <vector>
#include <functional>
int main()
{
    std::vector<int> a{0, 1, 2, 3, 4};
    std::vector<int> b{5, 4, 2, 3, 1};

    int r1 = std::inner_product(a.begin(), a.end(), b.begin(), 0);
    std::cout << "Inner product of a and b: " << r1 << '\n';

    int r2 = std::inner_product(a.begin(), a.end(), b.begin(), 0,
                                std::plus<>(), std::equal_to<>());
    std::cout << "Number of pairwise matches between a and b: " <<  r2 << '\n';
}

Second, and more importantly, with Ranges allowing us to compose algorithms properly, do we even need these at all? Consider again the above example and how it might be written with and without specialized algorithms:

ranges::inner_product(a, b, 0,
    std::plus(), std::equal_to());

ranges::fold(views::zip_transform(std::equal_to(), a, b),
    0, std::plus());
ranges::sum(views::zip_transform(std::equal_to(), a, b));

Even though the ranges::fold construction is more complicated, it’s also easier to see the groupings and understand what’s going on. The composed construction also allows for arbitrarily many ranges, not simply two.

There is also the question of projections. With transform_reduce and inner_product, there are three ranges that could be projected: each range into the binary grouping operation, and the result of that grouping. This makes it exceedingly awkward if you only want to provide exactly one of those projections:

ranges::inner_product(a, b, 0,
    std::plus(), std::multiplies(),
    p1);

ranges::fold(views::zip_transform(std::multiplies(),
        a | views::transform(p1), b),
    0, std::plus());

ranges::inner_product(a, b, 0,
    std::plus(), std::multiplies(),
    {}, p2);

ranges::fold(views::zip_transform(std::multiplies(),
        a, b | views::transform(p2)),
    0, std::plus());

ranges::inner_product(a, b, 0,
    std::plus(), std::multiplies(),
    {}, {}, p3);

ranges::fold(views::zip_transform(std::multiplies(), a, b)
           | views::transform(p3),
    0, std::plus());

We think that once we add ranges::fold as Tier 1 [P2322R2] and ranges::reduce as Tier 2, we do not actually have a need for either a ranges::transform_reduce or a ranges::inner_product (which would also save us from having to come up with a name for the latter).

5.2 Algorithms that Output a Range (Anamorphisms)

iota is the easiest one to consider here. We already have views::iota in C++20, which importantly means that we already have all the correct constraints in place. In that sense, it almost takes less time to adopt ranges::iota than it would take to discuss whether or not it’s worth spending time adopting it.

But that does not hold for the other algorithms.

5.2.1 shift_left and shift_right

shift_left and shift_right fall into a similar boat as iota, but aren’t completely without questions. [P1243R4] originally proposed these, but were dropped from the paper based on discussion about the return type. shift_right has a straightforward return type of subrange(new_first, last). But what should shift_left return?

If, for consistency, it returns subrange(first, new_last) then we don’t return last — even though we probably had to to compute it, unlike most of the other ranges algorithms. Most, but not all (is_sorted, count, and the proposed fold do not, for instance). Also, if n == 0 or n >= last - first, then shift_left(r, n) does nothing - so should it just return subrange(first, first)? That question will still have to be answered.

5.2.2 std::adjacent_difference → ranges::adjacent_transform

std::adjacent_difference joins std::accumulate and std::inner_product in the list of algorithms prejudicially named after a specific operation. We do not yet have views::adjacent_transform (Tier 1 above), and this would be the algorithm version of those views:

ranges::adjacent_difference(r, o);

ranges::copy(views::adjacent_transform(r, std::minus()), o);

ranges::adjacent_difference(r, o, f);

ranges::copy(views::adjacent_transform(r, f), o);

Even though we’re increasing the length of the expression as we go, and arguably increasing the complexity of the construction as well, we’re also lowering the surface area of the API by taking advantage of composition. These become even better with the adoption of the pipeline operator in [P2011R1]:

ranges::adjacent_difference(r, o);

views::adjacent_transform(r, std::minus()) |> ranges::copy(o);

ranges::adjacent_difference(r, o, f);

views::adjacent_transform(r, f) |> ranges::copy(o);

This begs the question: do we actually need to have a ranges::adjacent_transform at all? This question needs to be answered, and its existence lowers the priority of the range-ification of such algorithms relative to the adoption of their corresponding range adapters.

5.2.3 std::partial_sum → ranges::partial_fold and std::{in,ex}clusive_scan

We saw in the catamorphism section that we have a pair of algorithms, std::accumulate and std::reduce, that solve basically the same problem except that one prejudices a particular operation (std::accumulate suggests +) while the other has the more generic name yet is actually more restrictive (std::reduce requires both the operation to be both associative and commutative, std::accumulate does not require either).

We have the exact same issue here, std::partial_sum is strongly suggestive of +, while std::inclusive_scan is the more generically-named algorithm that nevertheless imposes the stronger restriction (in this case, just associativity).

Our suggestion for what to do with std::partial_sum and std::{in,ex}clusive_scan thus mirrors our suggestion for what we did with std::accumulate and std::reduce:

• rename std::partial_sum to ranges::partial_fold (since it’s a fold that also yields partial results), which will have neither a defaulted binary operation nor associativity requirements.
• introduce ranges::{in,ex}clusive_scan
• introduce ranges::partial_sum that is hard-coded to use std::plus() as the binary operation, which internally forwards to ranges::inclusive_scan (not ranges::partial_fold, since we know addition is associative).

As we discussed with the question of the need for adjacent_difference, there would also be the question of whether we need these algorithms at all. As such, we ascribe them fairly low priority.

5.2.4 transform_{in,ex}clusive_scan

Similar to the question of transform_reduce and inner_product, we don’t think we need a:

ranges::transform_inclusive_scan(r, o, f, g);

once we can write

ranges::inclusive_scan(r | views::transform(g), o, f);

or even

ranges::copy(r | views::transform(g) | views::inclusive_scan(f), o);

The latter two having the nice property that you don’t have to remember the order of operations of the operations. We don’t think we need these at all.

5.3 Parallel Algorithms

One of the C++17 additions was the introduction of the parallel algorithms by way of the Parallelism TS [P0024R2]. But with Ranges, we don’t have parallel overloads of any of the algorithms yet. How should we prioritize adding parallel overloads for the range algorithms?

The most important issue to consider is: with all the ongoing work on executors, we very much want to ensure that the parallel overloads we define will end up working. The status quo in the standard library is that the ExecutionPolicy parameter is constrained on is_execution_policy_v<remove_cvref_t<ExecutionPolicy>>. Is that good enough for executors? It might not be, and it would be extremely disappointing to adopt executors in a way that is incompatible with a bunch of parallel algorithms we just added. This needs careful consideration by somebody familiar with executors.

The second issue is that there are additional requirements imposed on the parallel overloads as compared to the sequential ones (see 25.3 [algorithms.parallel] as well as [P0836R1]). Those requirements would need to be somehow captured in concepts. Even if the type trait is considered sufficient for executors going forward, the concepts work is still necessary.

And for those algorithms which we do not yet have range-based overloads, we still have exactly the same issue for why we don’t have range-based overloads yet: what are the concepts that we need to constrain the various parameters?

Due to the executor dependency and the need to be careful about specifying the concepts for parallel requirements, we consider this Tier 2.

6 Actions

There are really three kinds of operations that exist in range-v3:

• Algorithms are operations that eagerly either mutate an input range (e.g. sort), produce a value (e.g. max_element), both (partition), or produce a new range by way of an output iterator or output range (e.g. copy).
• Views are operations that lazily produce a new range.
• Actions are operations that eagerly produce a new range.

While we have range-based algorithms and views in C++20, we do not yet have any actions. range-v3 comes with many actions, some of which are the action flavor of views and some of which are the action flavor of algorithms. The full list is: drop, drop_while, erase, insert, join, push_back, push_front, remove_if, remove, reverse, shuffle, slice, sort, split, stable_sort, stride, take, take_while, transform, unique, and unstable_remove_if.

The advantage of these actions is that unlike the algorithms, they compose, and unlike the views, you can pass rvalue ranges to them. From the examples in the range-v3 documentation [range-v3.docs]:

extern std::vector<int> read_data();
using namespace ranges;
std::vector<int> vi = read_data() | actions::sort | actions::unique;

vi = std::move(vi) | actions::sort | actions::unique;

vi |= actions::sort | actions::unique;

actions::unique(actions::sort(vi));

Indeed, ranges actions do seem very useful — and provide the ability to pipeline operations that we cannot do today. There is, nor will there ever be, a views::sort, so the only option today is:

std::vector<int> vi = read_data();
ranges::sort(vi);
ranges::unique(vi);

But while it might be nicer to provide a pipeline approach, we feel this whole space simply needs more research. It is an immediate source of frustration for users when they discover that while you can pipe a view into an action, you cannot do the reverse.

Given that the actions don’t provide any functionality that we don’t already have, simply adding the ability to compose some operations better, we give them pretty low priority relative to the wealth of new functionality many of the other operations here provide.

7 Plan Summary

To summarize the above descriptions, we want to triage a lot of outstanding ranges algorithms, views, actions, and other utilities into three tiers based on our opinions of their importance. While ideally we could just add everything into C++23, we realize that this is not realistic with the amount of available LWG bandwidth, so our tier 1 here is trying to be as small as possible while still hitting as many major pain points as possible.

The following includes links ot papers that currently exist so far, and their status as of the writing of this revision.

7.1 Tier 1

• ranges::to ([P1206R7], adopted for C++23 ✔️)
• the ability for user-defined range adaptors to properly cooperate with standard library ones ([P2387R3], adopted for C++23 ✔️)
• the ability to format ranges with std::format ([P2286R6], approved by LEWG)
• the addition of the following range adapters:
  • views::adjacent ([P2321R2], adopted for C++23 ✔️)
  • views::adjacent_transform ([P2321R2], adopted for C++23 ✔️)
  • views::as_const ([P2278R2], approved by LEWG, pending name)
  • views::as_rvalue ([P2446R2], approved by LEWG and LWG, pending name)
  • views::cartesian_product ([P2374R3], approved by LEWG)
  • views::chunk ([P2442R1], adopted for C++23 ✔️)
  • views::chunk_by ([P2443R1], adopted for C++23 ✔️)
  • views::enumerate ([P2164R5])
  • views::join_with ([P2441R2], adopted for C++23 ✔️)
  • views::slide ([P2442R1], adopted for C++23 ✔️)
  • views::stride ([P1899R2], approved by LEWG)
  • views::zip ([P2321R2], adopted for C++23 ✔️)
  • views::zip_transform ([P2321R2], adopted for C++23 ✔️)
• the addition of the following range algorithms:
  • ranges::iota ([P2440R1], adopted for C++23 ✔️)
  • ranges::fold ([P2322R5], , approved by LEWG)
  • ranges::shift_left ([P2440R1], adopted for C++23 ✔️)
  • ranges::shift_right ([P2440R1], adopted for C++23 ✔️)
• the following other changes to standard library (necessary for the zip family, all handled by [P2321R2], and adopted for C++23 ✔️):
  • pair<T, U> should be const-assignable whenever T and U are both const-assignable
  • pair<T&, U&> should be constructible from pair<T, U>&
  • tuple<T...> should be const-assignable whenever T... are const-assignable
  • tuple<T&...> should be constructible from tuple<T...>&.
  • vector<bool>::reference should be const-assignable
• the following other changes since C++20 that were not previously mentioned in this plan but are added here for completeness:
  • Enabling list-initialization for ranges algorithms ([P2248R4], approved by LEWG)
  • ranges::contains ([P2302R2], approved by LEWG)
  • Allowing C++20 iterators to be used in more C++17 algorithms ([P2408R4], approved by LEWG)
  • Supporting move-only types in certain range adaptors ([P2494R1], approved by LEWG)

7.2 Tier 2

• the addition of the following range adapters:
  • views::cache1
  • views::chunk_on
  • views::concat
  • views::cycle
  • views::delimit
  • views::drop_last
  • views::drop_last_while
  • views::generate
  • views::generate_n
  • views::group_by_key
  • views::intersperse
  • views::partial_sum
  • views::remove
  • views::remove_if
  • views::repeat ([P2474R1], approved by LEWG)
  • views::replace
  • views::replace_if
  • views::scan
  • views::split_when
  • views::take_last
  • views::take_last_while
  • views::transform_maybe
  • views::trim
  • views::unique
• the addition of the following range algorithms:
  • parallel overloads of all the existing algorithms in std::ranges that have a parallel overload in std
  • ranges::reduce
  • ranges::sum
  • ranges::product

7.3 Tier 3

• the addition of the following range adapters:
  • views::adjacent_filter
  • views::adjacent_remove_if
  • views::drop_exactly
  • views::flat_map (possibly unnecessary given [P2328R1])
  • views::head
  • views::linear_distribute
  • views::sample
  • views::set_difference
  • views::set_intersection
  • views::set_union
  • views::set_symmetric_difference
  • views::slice
  • views::tail
  • views::take_exactly
• the addition of the following range algorithms:
  • ranges::adjacent_transform
  • ranges::partial_fold
  • ranges::inclusive_scan
  • ranges::exclusive_scan
  • ranges::partial_sum
• the addition of ranges actions

8 References