Compile-time sizes for range adaptors

  1. Home
  2. Career
  3. Developer blog
  4. Compile-time sizes for range adaptors

6 min read — by Jonathan Müller

In my previous blog post, we've discussed the static constexpr std::integral_constant idiom to specify the size of a range at compile-time. Unlike the standard, our ranges library at think-cell already supports compile-time sizes natively, so I was eager to try the idiom there and see how it works out in practice.

namespace tc {
	template <typename Rng>
	constexpr auto size(Rng&& rng); // runtime-size of a range, like std::ranges::size
	
	template <typename Rng> requires tc::has_constexpr_size<Rng>
	constexpr auto constexpr_size = …; // compile-time size of a range given its type
}
tc::size and tc::constexpr_size

We have two ways to query the size: One size function that returns an integer like std::ranges::size, and one constexpr_size variable template that determines the compile-time size given the type of the range. In the latter case, we can directly apply the idiom by making constexpr_size a variable template of std::integral_constant type. That way the user has full flexibility in the interface:

template <typename Rng>
void foo(Rng&& rng) {
	std::size_t runtime_size = tc::size(rng);
	constexpr std::size_t compile_time_size = tc::constexpr_size<Rng>();
	constexpr std::integral_constant compile_time_size_constant = tc::constexpr_size<Rng>;
}
The interface of tc::size and tc::constexpr_size

That leaves the implementation of tc::constexpr_size. The status quo was using trait specializations. Note that providing an implementation for tc::constexpr_size automatically supports tc::size as well.

template <typename Rng>
struct constexpr_size_impl; // no definition

template <typename Rng>
constexpr auto constexpr_size = constexpr_size_impl<std::remove_cvref_t<Rng>>{};

// Real implementation delegates all tuple-like types to std::tuple_size, omitted here.
template <typename T, std::size_t N>
struct constexpr_size_impl<std::array<T, N>> : std::integral_constant<std::size_t, N> {};

// more specializations
The previous implementation of tc::constexpr_size.

Can we use static constexpr std::integral_constant in the implementation?

I wanted to change it to somehow leverage the static constexpr std::integral_constant idiom instead. That is, the implementation of tc::constexpr_size checks for the well-formedness of Rng::size as the default implementation. We then only need trait specializations to provide implementations for types we can't control like std::array. While it worked great for range factories where the size is always known, like std::array, tc::empty_range, or tc::all_values<Enum>, it does not work for range adaptors.

Consider tc::transform_adaptor (our std::ranges::transform_view), which returns a range whose elements are the underlying range elements transformed by applying a function. Crucially, it does not change the size of the range: If the underlying range rng has N elements, tc::transform(rng, fn) also has N elements. Thus we want to forward the size properties of rng transparently:

  • If rng has a constexpr size (i.e. tc::constexpr_size<Rng> is well-formed), so should tc::transform(rng, fn).
  • Otherwise, if rng has a runtime size (i.e. tc::size(rng) is well-formed), so should tc::transform(rng, fn).
  • Otherwise, it has neither constexpr nor runtime size.

A naive attempt using static constexpr std::integral_constant for tc::constexpr_size can look like this:

template <typename Rng, typename Fn>
struct transform_adaptor {
	// for tc::constexpr_size and tc::size
	static constexpr std::integral_constant size = tc::constexpr_size<Rng>; // somehow constrained

	// for tc::size
	constexpr std::size_t size() const
		requires tc::has_size<Rng> && (!tc::has_constexpr_size<Rng>)
	{
		return tc::size(base_rng());
	}
};
A naive attempt

The issue here is the "somehow constrained" comment: static member variables, unlike functions, cannot be constrained, nor overloaded with member functions. So we'd have to conditionally inherit the constexpr size only if Rng has a constexpr size, which is ugly.

We also don't have any benefit from using static constexpr std::integral_constant —users shouldn't directly call rng.size(), they should use tc::size or tc::constexpr_size instead. So there is no upside to using static constexpr std::integral_constant in the implementation.

Conditionally returning std::integral_constant from .size()

So let's just have a single size() function that returns either std::size_t or std::integral_constant, the "most constexpr" version of the range size. This approach continues to work for range factories, but now we can also write our adaptors:

template <typename Rng, typename Fn>
struct transform_adaptor {
	// for tc::size and tc::constexpr_size
	constexpr auto size() const& requires tc::has_size<Rng> {
		if constexpr (tc::has_constexpr_size<Rng>)
			return tc::constexpr_size<Rng>;
		else
			return tc::size(base_rng());
	}
};
A better implementation

The corresponding specialization of tc::constexpr_size calls the function inside decltype to get the result:

// Rng has a size function that returns an integral_constant.
template <typename Rng> requires requires { decltype(std::declval<Rng&>().size())::value; }
struct constexpr_size_impl<Rng> : decltype(std::declval<Rng&>().size()) {};
New tc::constexpr_size specialization.

The runtime version tc::size doesn't need to be changed, as the range continues to have a .size() member function that returns the size, just possible encoded in the return type itself.

Avoiding code duplication

While the approach is nice, there is a bit of code duplication. This becomes especially apparent for more complex ranges like tc::concat_adaptor, whose size is the sum of all sub-range sizes:

template <typename ... Rng>
struct concat_adaptor {
	constexpr auto size() const
		requires (tc::has_size<Rng> && ...)
	{
		if constexpr ((tc::has_constexpr_size<Rng> && ...))
			return std::integral_constant<std::size_t, (tc::constexpr_size<Rng>() + ...)>{};
		else
			return std::apply([](auto const& ... base_rng) {
				return (tc::size(base_rng) + ...);
			}, base_rng_tuple);
	}
};
size() for tc::concat_adaptor

We are computing the same value twice: once as a std::integral_constant, and once as std::size_t. We can unify it by splitting the size computation and the result wrapping using a helper function:

template <auto Fn, typename ... Rng>
constexpr auto compute_range_adaptor_size(Rng&&... rng) {
	if constexpr ((tc::has_constexpr_size<Rng> && ...)) {
		auto constexpr value = Fn(tc::constexpr_size<Rng>()...);
		return std::integral_constant<std::size_t, value>{};
	} else {
		auto const value = Fn(tc::size(std::forward<Rng>(rng))...);
		return value;
	}
}

template <typename ... Rng>
struct concat_adaptor {
	constexpr auto size() const
		requires (tc::has_size<Rng> && ...)
	{
		return std::apply([](auto const& ... base_rng) {
			return tc::compute_range_adaptor_size<[](auto const ... n) {
				return (n + ...);
			}>(base_rng...);
		}, base_rng_tuple);
	}
};
size() for tc::concat_adaptor using tc::compute_range_adaptor_size() helper

The helper function compute_range_adaptor_size() takes all sub-ranges and computes the most constexpr version of their sizes. This is then passed to a lambda to compute the derived size, and returned in the most constexpr way. Note that the lambda has to be passed as a non-type template parameter, so we can use its result in a constexpr context.

concat_adaptor::size() then just needs to call compute_range_adaptor_size() with an appropriate lambda and the subranges, and it will automatically work.

Conclusion

The size of a range adaptor can be available at compile-time or runtime. We can forward that information easily by returning std::integral_constant whenever possible, the most constexpr version of the size.

The pattern can be applied to more situations. For example, I've recently added support to tc::filter predicates that return std::true_type or std::false_type. That way, we can filter e.g. a std::tuple by type with the same mechanism used to filter a runtime range by value.

We are hiring
  • Enough time to make sure that every detail of your solution is perfect
  • Become part of an international team of brilliant minds
  • No scheduled meetings
Join as a C++ developer