Compile-time sizes for range adaptors
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>;
}
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
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 aconstexpr
size (i.e.tc::constexpr_size<Rng>
is well-formed), so shouldtc::transform(rng, fn)
. - Otherwise, if
rng
has a runtime size (i.e.tc::size(rng)
is well-formed), so shouldtc::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());
}
};
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());
}
};
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()) {};
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()
helperThe 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.
Do you have feedback? Send us a message at devblog@think-cell.com !
Sign up for blog updates
Don't miss out on new posts! Sign up to receive a notification whenever we publish a new article.
Just submit your email address below. Be assured that we will not forward your email address to any third party.
Please refer to our privacy policy on how we protect your personal data.