views::transform_join

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

Abstract

This paper proposes the Tier 1 adaptor in P2760: views::transform_join to improve the C++26 ranges facilities, which is a simple composition of views::transform and views::join.

Revision history

R0

Initial revision.

Discussion

views::transform_join, called flat_map in most languages, is a commonly-used operation on data streams. It transforms the input elements into an output sequence through the transformation function, and flattens the resulting sequence of the sequence.

Benefiting from the enhancement of join_view in P2328, views::transform_join(E, F) is now completely equivalent to views::join(views::transform(E, F)). We no longer need to use views::cache_last (P3138) to cache the prvalue range returned by the transform function, join_view already do this internally for us.

Given that P2760 considers this adaptor a high priority, the commonness of such operation in other languages, and the convenience brought by reducing the user's typing, the author believes that it is time to bring views::transform_join into the standard.

After this, the famous Pythagorean triples formula in range/v3 now can be written as:

    // Define an infinite range containing all the Pythagorean triples:
    auto triples = views::iota(1) | views::transform_join([](int z) {
      return views::iota(1, z + 1) | views::transform_join([=](int x) {
        return views::iota(x, z + 1) | views::transform_join([=](int y) {
          return views::repeat(tuple(x, y, z), x * x + y * y == z * z ? 1 : 0);
        });
      });
    });

    // Display the first 100 triples
    for (auto triple : triples | views::take(100))
      println("{}", triple);

Design

Should we name it views::flat_map?

Nope.

It's worth noting that range/v3 calls it views::for_each, which might be a more confusing name so is not considered here.

Should we introduce a new transform_join_view class?

Nope.

Although this will bring an adaptor that combines two existing adaptors to the standard for the first time, the author believes that such change is still worthwhile.

First of all, the cost of creating a new transform_join_view class and associated iterator is quite high because join_view is already a complex view. Especially when its functionality can be completely synthesized by simply combining two adaptors, introducing new classes has no observable benefit except bringing unnecessary complexity and redundancy.

Second, by combining two adaptors, views::transform_join can automatically inherit their previous and subsequent enhancements, such as support for stashing iterators (P2770) and extension for conditionally borrowed (P3117, hope so?), because views::transform_join is essentially a specialized join_view.

In summary, the authors stick with the current design. Note that the design is also consistent with the implementation in range/v3.

Should we spell it views::join(views::transform(E, F)) or join_view(transform_view(E, F))?

As currently worded, views::transform(E, F) is expression-equivalent to transform_view(E, F) and views::join(E) is expression-equivalent to join_view<views::all_t<decltype((E))>>{E}. Since the latter's E is always transform_view, this causes views::all_t to have no effect.

That is to say, views::join(views::transform(E, F)) is exactly join_view(transform_view(E, F)). In this case, the author prefers to use the more primitive form of the latter as the wording.

Implementation experience

The author implemented views::transform_join based on libc++. The details are relatively simple in less than 20 lines, see here.

Proposed change

This wording is relative to N4971.

References