More Ranges Please

Ranges are one of the major additions of C++20, in which our main abstraction for sequences shifted from iterator-pairs into full fledged concepts, allowing better composability, expressibility and safety when working with bounded and even unbounded one dimensional sequences of data.

The fluent use of the pipe-operator gave us power to write complex functional-style algorithms which are both highly readable and perfomant. The ranges library, especially with some recent C++23 additions also better exposes us to the notion of 'range-of-ranges' and multi-dimentional spans, which weren't in focus of the STL in prior versions of the language.

One key feature of the STL since the last century was the large number of algorithms and building blocks which seemed woven together and gave us a vocabulary by which algorithms could be expressed with little need to work with raw loops.

Together with the introduction of ranges, the STL has also gained various range-based algorithms (as well as views and adapters), yet most of those algorithms were basic adaptations of the ones that are available in the iterator-pair model.

In a talk from 2002, the primary designer of STL described the process of gathering, currating and solidifying the algorithms in the STL circa 1998 (Stepanov: STL and its Design Principles). My talk aims to apply a similar process to the universe of C++20/C++23 ranges, and propose potential additions to our vocabulary when developing range-based algorithms.

In this talk, we will start with an introduction to the ranges library as an example of a breakthrough library, and discuss various aspects of composability which makes the library shine.

Then, we will go over a variety of algorithms which currently don't exist for ranges, describe their potential value, and discuss whether they can or should be added to the standard.

A few examples of algorithms which will be covered: Algorithms for sorted ranges, such as take_between and histogram, ... Algorithm for ranges-of-(sorted-)ranges, such as merge, set_union, set_intersection, ... Algorithms which might require some helper data structures, such as histogram (for non sorted ranges) Algorithms related to generation and processing of permutations, such as order.

As we go through the various examples, we'll discuss what might be good candidates for addition to the STL (and reference prior talks on the topic), the notion of sorted ranges, and hopefully leave the talk with a good desire to compose algorithms in the brave new world of ranges