Missing concept: the quest for `range_of`

│ Blog

Reeling back a bit

What is a range?

Let us have a look into the C++20 standard

1
2
3
4
5
template< class T >
concept range = requires( T& t ) {
    ranges::begin(t); // equality-preserving for forward iterators
    ranges::end (t);
};

A range is a C++ concept, a set of constraint, that must be fulfilled for a type to be called range. As per the definition above, any type T that provides valid definition for the calls to ranges::begin and ranges::end. Following decades of usage in the STL, well known (maybe dreaded) by C++ developers, a range consists in a pair of iterators returned by begin and end. Why those two instead of the existing std::beginand std::end ? Simply to enable more customization. Remember that except in some rare case (looking at you std::hash), thou shall not add, specialize, or overload anything in the std:: namespace ! A range can be satisfied by either providing member functions .begin() and .end() or via call to free functions begin() and end() that can be found via Argument Dependent Lookup.

A range for what ?

The principle behind ranges is to compose algorithms over data that can be iterated over in a more expressive, declarative, and concise way. Do you remember the good old algorithms header: std::accumulate, std::transform? Yes, me too, and I still wince thinking about it.

1
2
3
4
5
6
7
8
9
void unary_transform_example(std::string& hello, std::string world)
{
    // Transform string to uppercase in-place
    std::transform(hello.cbegin(), hello.cend(), hello.begin(), [](unsigned char c){return std::toupper(c);});
    std::cout << "hello = " << std::quoted(hello) << '\n';
    // for_each version (see Notes above)
    std::for_each(world.begin(), world.end(), [](char& c){c = to_uppercase(c);});
    std::cout << "world = " << std::quoted(world) << '\n';
}

Sorry for the jump scare, I know many of us have rough trauma typing all those begin/end all over the place 😄

An example to illustrate ranges could be

1
2
3
4
auto source = std::vector{-2,3,0,1,-5};
auto composition = source | std::views::filter([](auto x){return x < 0;}) 
                          | std::views::transform([](auto& x){return x*2;});
std::println("{}",composition);

The footprint is smaller and the intent is clearer, don’t you think so ? Moreover, it is not possible to compose regular algorithms because they are eager, and act directly on the input, which means filter would need to be implement as a for loop.

Alright, some may argue that lambdas are the new clutter, and I cannot really disagree with that, they do take a lot of visual space, as opposed to similar tools in other languages, e.g. Java, seen the extensive list given here. One can always go with Boost.Lambda or hardcore macros. Unfortunately, it is not easy, like everything in C++ dare I say, to get short lambda in the Core language due to every possibilities that must be considered, discussed, and approved.

What with a range ?

Thanks to the ranges library, one can easily restrict template functions to perform an operation on a sequence of elements. Let us consider briefly this slightly contrived example:

1
2
3
4
5
6
7
8
namespace my_views
{
    template<std::ranges::range R>
    auto cos(R&& range)
    {
        return std::views::transform(r,[](auto const& x){return std::cos(x);})
    }
}

Great isn’t it ? …or is it ? Yes we constrained the template from an infinite amount of possibilities, but to an infinite subset of possibilities. A simple range requirement is not sufficient to constrain meaningfully the function to our goal. Therefore, we would need to add further requires clauses, static_assert, or other techniques, cluttering the declaration and/or definition to harden it properly. Although, in the end, what we wish for is simply a range of floating point values.

Getting to the point

Now that the context is set, let us get back to the main topic of this post, and express how we wish we could write “a range of integers”. Like a wise man said “Design your abstractions from what you would like to type !” (Vincent Reverdy, at his talk from CppCon2023), which is a principle I strongly adhere.

1
2
3
4
5
// Like this 
void foo(range_of<int> auto&& r); // inline
// or with explicit template parameter list
template<range_of<int> R>
void foo(R&& r);

To make it work currently with standard library facilities (in C++20 and above), one would need to resort to the following

1
2
3
template<std::ranges::range R>
requires std::same_as<std::ranges::range_value_t<R>,int>
void foo(R&& r)

It works, it is verbose, and it needs to be done at every function where you wish to accept a range of something.

The direct path

The naïve way to go at it is to simply wrap the above snippet into a concept.

1
2
template<typename T, typename U>
concept range_of = std::ranges::range<T> && std::same_as<U,std::ranges::range_value_t<T>>;

The magic of the standard allows us to use concepts as simply as this:

1
2
template<range_of<int> R>
void foo(R&& r) {}

Because the argument R is automagically injected as the first argument of the constraint (type-constraint in the standard linguo), so that the compiler effectively checks: range_of<R,int>

Concepts can also be named in a type-constraint, as part of
type template parameter declaration,
placeholder type specifier,
compound requirement.
In a type-constraint, a concept takes one less template argument than its parameter list demands, because the contextually deduced type is implicitly used as the first argument of the concept.
1
2
3
4
5
template<class T, class U>
concept Derived = std::is_base_of<U, T>::value;
 
template< Derived<Base> T >
void f(T); // T is constrained by Derived<T, Base>

The exact wording can be checked in the released C++20 standard document, or more conveniently (and freely) in the working draft

Limitations

L minor 🎵

What if we want to query something else than the range value type, but the range reference type, like explained here

1
2
template <typename R, typename V>
concept range_of = std::ranges::range<R> and std::same_as<V,std::ranges::range_reference_t<R>>;

One can get away with this problem relatively simply by adding the argument in the template argument list, at the cost of a slightly heavier interface.

1
2
template <typename R, typename V, template<typename> typename E = std::ranges::range_value_t>
concept range_of = std::ranges::range<R> and std::same_as< V, E<R> >;

L major 🎶

The other issue is much hairier, what if instead of a range of just integers, we want to accept a range of integral types ? Suddenly our concrete type is abstracted away and must satisfy a generic constraint ! We would like to be able to write:

1
2
template<range_of<std::integral> R>
void foo(R&& r) {}

Which would translate into

1
2
template <typename R, concept V, template<typename> typename E = std::ranges::range_value_t>
concept range_of = std::ranges::range<R> and std::same_as< V<E<R>> , E<R> >;

Can your compiler do it ? At least not at the time of release of this post ! Still living in C++23 or below here, my sweet reader from the future with cutting edge compilers.

The standard will save us all…

Hopefully, some brave souls are heralding the fight for change with proposal P2841 ~~aimed to land~~ landing in C++26. It would enable concept argument in the template argument list.

1
2
template <typename T, template <typename> concept C>
concept decays_to = C<std::decay_t<T>>;

Until it reaches us mere common developer, the proposal provides a compiler explorer link listing exhaustively possible workarounds to pass constraints concepts around, from least palatable but more efficient via lambda tricks, to inefficient but user friendly via type indirection.

…or not

Unfortunately, the proposal does not solve a second major issue at hand: what if we want to use our concept with a direct type?

1
2
3
4
5
6
7
8
9
// For the given definition of the concept `range_of`
template <typename R, template <typename> concept V, template<typename> typename E = std::ranges::range_value_t>
concept range_of = std::ranges::range<R> and std::same_as< V<E<R>> , E<R> >;

template<range_of<std::integral> R>  // ✅ passing a concept to a concept argument
void foo(R&& r) {}

template<range_of<int> R> 			// ❌ passing a typename to a concept argument
void bar(R&& r) {}

The standard does not do not allow redefinition of concepts, and template arguments will have to be either a concept or a type, precluding the other from existing. Stalemate ! Maybe this will all be resolved with Universal Template Parameters, a proposal for unifying template parameters (type, variable, concepts) into a single representation ?

Everything can be solved with (yet) another layer of indirection

Let us dig the idiom 4 from the list of alternatives above as a starting point.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// Idiom 4: Use a metafunction class convention
namespace mfc_idiom {
    namespace mfc {
        struct Copyable {
          template <class T>
          struct apply : std::bool_constant<std::copyable<T>> {};
        };
	} // namespace mfc
    
    template <typename T, class /* "concept" */ C>
    concept decays_to = C::template apply<std::decay_t<T>>::value;

    template <decays_to<mfc::Copyable> T>
    auto f(T&& x) {}
};

The idiom converts a concept down to a type, which can be passed around as template arguments more easily (thereby nullifying the benefits of concept as core language construct, but this is the topic for another day). Adapted to our situation, it becomes

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
// Library code
namespace comcept::trt 
{
	struct integral { template <class T> static constexpr bool value = std::integral<T>; };
}
namespace comcept
{
    template <typename R, class /* "concept" */ C, template<class...> typename E = std::ranges::range_value_t>
    concept range_of = std::ranges:range<R> && C::template value<E<R>>;
};
// End-user example
template <comcept::range_of<comcept::trt::integral> R>
auto f(R&& x) {}

It is a fine workaround, but it does not solve yet our previous issue of being able to pass either type or constraint. By resorting to logical short-circuiting, we can reach the desired result.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
// Library code
namespace comcept::trait 
{
	struct integral { template <class T> static constexpr bool value = std::integral<T>; };
}
namespace comcept
{   
    template <typename R, class /* type or "concept" */ C, template<class...> typename E = std::ranges::range_value_t>
    concept range_of = std::ranges:range<R> && (std::same_as<C, E<R>> || C::template value<E<R>>);
}
// End-user example
template <comcept::range_of<comcept::trait::integral> R>
auto f(R&& x) {}

template <comcept::range_of<int> R>
auto f(R&& x) {}

Generalization for binary, ternary, n-ary constraints

In the end, we convert concepts back into type traits, where they themselves somewhat originate from, indeed type traits were used along with SFINAE to replicate to some extents constraint on templates. Type traits in C++ were introduced at a time where variable template were not part of the standard, hence the generic definition pooling all types within the outermost template argument list. For example, for std::is_same

1
2
3
4
5
template<class T, class U>
struct is_same : std::false_type {};
 
template<class T>
struct is_same<T, T> : std::true_type {};

All type traits were then given a direct boolean access thanks to the introduction of variable template.

1
2
template<typename T, typename U>
constexpr bool is_same_v = is_same<T, U>::value;

Those ways of defining type traits do not enable composition as all arguments must be known at instantiation point, which is not feasible during composition where the queried type is unknown until the last step. Yet, we can use the language feature to reformulate type traits into a two-phase look-up process, more suitable for our goal.

1
2
3
4
5
6
template<class U>
struct is_same
{
    template<class T>
    static constexpr bool value = std::is_same_v<T,U>;
};

Now the queried type T is left unevaluated until requested, and we can carry the generic constraint as a concrete type. We can therefore create is_same<int> and check if any other type is actually similar to the curried requirement is_base_of<int>::value<double> at the last moment. The principle is straightforwardly extended to concepts, and for any arity (ternay, n-ary).

1
2
3
4
5
6
template<class U>
struct same_as
{
    template<class T>
    static constexpr bool value = std::same_as<T,U>;
};

Range of range of range of

Equipped with this new definition of type traits, we can create concepts which are compatible for composition, like range_of. Since concepts are not composable unto themselves, we just have to apply the same process of typification, type traitification (or whatever is the name), and convert that concept into a type, thereby enabling composable range of.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
// Library code
namespace comcept::trait 
{
	struct integral { template <class T> static constexpr bool value = std::integral<T>; };
}
namespace comcept
{   
    template <typename R, class /* type or "concept" */ C, template<class...> typename E = std::ranges::range_value_t>
    concept range_of = std::ranges:range<R> && (std::same_as<C, E<R>> || C::template value<E<R>>);
};
namespace comcept::trait 
{
    template <class /* type or "concept" */ C, template<class...> typename E = std::ranges::range_value_t>
	struct range_of { template <class R> static constexpr bool value = comcept::range_of<R,C,E>; };
}
// End-user example
namespace ccpt = ::comcept;
namespace trt  = ::comcept::trait;
template <ccpt::range_of<trt::range_of<trt::integral>> R>
auto f(R&& x) {}

Conclusion

In this post, we have seen how to build a friendly composable concept through the often desired range_of example. The solution was not about achieving top compilation speed, but instead, about developer-friendly API (well, at least, according to my taste). Nevertheless, handling type traits via dependent template variable reduces the amount of type instantiation, which might be easier for the compiler to generate, if variables are less costly to instantiate than types.

I wrapped up the outcome of this little exploration into a library named comcept, the contraction of composable concept. The next steps would be enriching the library with more composable concepts, such as tuple_of and discuss about concept definition and limitations.

Missing concept: the quest for range_of