Removing Duplicates in C++ CRTP Base Classes
At the beginning of the summer, we talked on Fluent C++ about 7 projects to get better at C++ during the summer. Reader Sergio Adán has taken up the challenge, and picked up Project #1 about how to avoid duplicates in a variadic CRTP. Today as summer is drawing to an end, Sergio shares with us his solution in a guest post!
Sergio Adán is a Spanish C++ programmer. He began programming when he was 5 years old and his parents offered him an Amstrad CPC. Sergio has been programming in C++ for six years and he really likes code looks clean and expressive.
Interested to write on Fluent C++ too? Check out the guest posting area.
As we can see in the original post, if some packs have the same feature, our class will inherit the same base clase two or more times and then the direct call of the feature will fail:
We need to modify the inheritance to ensure each feature will be inherited only once. The solution I propose is to join, at compile time, all feature packs into a single pack removing all duplicates.
An additional level of indirection
To perform some compile-time work on the set of skill packs so as to remove the duplicates among skills, we introduce an additional level of indirection: the ExtraFeatures class. This class takes the packs as template parameters and does some cutting work that we’ll see in details just afterwards. Features packs such as ExtraFeaturesA use it to declare their set of skills.
template<typename Derived, template<typename> typename ... Features>
struct ExtraFeatures : Features<Derived>...
{ };
So once the declaration is in our project, feature packs must be declared as below:
template<typename Derived> using ExtraFeaturesA = ExtraFeatures<Derived,ExtraFeature1,ExtraFeature2>; template<typename Derived> using ExtraFeaturesB = ExtraFeatures<Derived,ExtraFeature2,ExtraFeature3>; template<typename Derived> using ExtraFeaturesC = ExtraFeatures<Derived,ExtraFeature1,ExtraFeature3>;
Let’s now see how to remove duplicate skills across the packs.
Checking if a feature is in a pack
As a first step we need a tool that checks if a given feature is already in a list. A first attempt could look like this:
template<typename Derived,
template<typename> typename ToCheck,
template<typename> typename Current,
template<typename> typename ... Features>
constexpr bool HasFeature()
{
if constexpr( std::is_same<ToCheck<Derived>,Current<Derived>>::value )
return true;
else if constexpr( sizeof...(Features) == 0 )
return false;
else
return HasFeature<Derived,ToCheck,Features...>();
}
The function HasFeature receives the type to be checked and a list of types. Then the function iterates over the list and check if the ToCheck template is in the list. The function works properly but it has a problem: it relies on recursion.
Compilers limit the maximum number of iterations done at compile time, and even if we remain with the authorised limits, recursion incurs more compilations time, so the common practice for operating on a list of types is to avoid recursion.
One solution is to use C++17’s fold expressions:
template<typename Derived,
template<typename> typename ToCheck,
template<typename> typename ... Features>
constexpr bool HasFeature()
{
return (std::is_same<ToCheck<Derived>,Features<Derived>>::value || ...);
}
The function now looks more simple and expressive, and it no longer uses recursion.
Merging two packs together
Now we need an utility that merges two feature packs into a new one, ensuring that each feature exists only once in the new feature pack:
To implement this functionality we can start with a recursive approach again:
template<typename ...>
struct JoinTwoExtraFeatures;
template<typename Derived,
template<typename> typename Feature,
template<typename> typename ... Features1,
template<typename> typename ... Features2>
struct JoinTwoExtraFeatures<
ExtraFeatures<Derived,Features1...>,
ExtraFeatures<Derived,Feature,Features2...>
>
{
using type= typename
std::conditional<
HasFeature<Derived,Feature,Features1...>(),
typename JoinTwoExtraFeatures<
ExtraFeatures<Derived,Features1...>,
ExtraFeatures<Derived,Features2...>
>::type,
typename JoinTwoExtraFeatures<
ExtraFeatures<Derived,Features1...,Feature>,
ExtraFeatures<Derived,Features2...>
>::type
>::type;
};
template<typename Derived,
template<typename> typename ... Features1>
struct JoinTwoExtraFeatures<
ExtraFeatures<Derived,Features1...>,
ExtraFeatures<Derived>
>
{
using type= ExtraFeatures<Derived,Features1...>;
};
But unlike HasFeature utility, I haven’t been able to find a way to avoid the recursion. If you see how to refactor this code to remove the recursion, please let us know by leaving a comment below.
Merging any number of packs
Now we are able to merge two feature packs into a new one. Our next step is to build an utility that merges any number of feature packs into a new one:
template<typename ...>
struct JoinExtraFeatures;
template<typename Derived,
typename ... Packs,
template<typename> typename ... Features1,
template<typename> typename ... Features2>
struct JoinExtraFeatures<
ExtraFeatures<Derived,Features1...>,
ExtraFeatures<Derived,Features2...>,
Packs...
>
{
using type= typename
JoinExtraFeatures<
typename JoinExtraFeatures<
ExtraFeatures<Derived,Features1...>,
ExtraFeatures<Derived,Features2...>
>::type,
Packs...
>::type;
};
template<typename Derived,
template<typename> typename ... Features1,
template<typename> typename ... Features2>
struct JoinExtraFeatures<
ExtraFeatures<Derived,Features1...>,
ExtraFeatures<Derived,Features2...>
>
{
using type= typename
JoinTwoExtraFeatures<
ExtraFeatures<Derived,Features1...>,
ExtraFeatures<Derived,Features2...>
>::type;
};
The library now has all its components, and you can find all the code put together here.
Reducing the amount of comparisons
The library so far does the job, but we can add an additional optimization. As you can see JoinExtraFeatures adds the unique features from the second feature pack to the first one. What happens if the second feature pack is larger than the first one? Then we are forcing the compiler to perform more iterations, for nothing:
Indeed, the algorithm here is to check if a feature from pack 2 is already in pack 1, and to add it if it’s not. So pack 1 is growing with some the features of pack 2. So to consider a feature of pack 2, we need to compare it with all the initial features of pack 1, plus the features of pack 2 added so far. So the smaller pack 2, the less comparisons.
Another way to put it is that the algorithm ends up comparing the features coming from pack 2 with each other, which it doesn’t do for pack 1. And this comparison is not necessary since we can assume that features are unique within a single pack.
Note that this solution ensures that pack 2 is the smallest of the two, but doesn’t remove the comparisons of the elements of pack 2 together. If you see how to get rid of those too, I’ll be happy to read your ideas in the comments.
To reduce comparisons, we can count the number of features in each feature pack and place in the first position the larger one.
With this improvement smaller pack will be merged into the larger one so the number of needed iterations can be slightly reduced:
template<typename Derived,
template<typename> typename ... Features1,
template<typename> typename ... Features2>
struct JoinExtraFeatures<
ExtraFeatures<Derived,Features1...>,
ExtraFeatures<Derived,Features2...>
>
{
using type = typename
std::conditional<
sizeof...(Features1) >= sizeof...(Features2),
typename JoinTwoExtraFeatures<
ExtraFeatures<Derived,Features1...>,
ExtraFeatures<Derived,Features2...>
>::type,
typename JoinTwoExtraFeatures<
ExtraFeatures<Derived,Features2...>,
ExtraFeatures<Derived,Features1...>
>::type
>::type;
};
Finally we just need to update the declaration of the X class. As explained at the beginning, X can no longer inherit from the feature packs directly. Rather it now inherits from the merged one:
template<template<typename> typename... Skills>
class X : public JoinExtraFeatures<Skills<X<Skills...>>...>::type
{
public:
void basicMethod(){};
};
The code can be tested easily without modifying the original X class posted by Jonathan in the original pre-summer post:
int main()
{
using XAB = X<ExtraFeaturesA, ExtraFeaturesB, ExtraFeaturesC>;
XAB x;
x.extraMethod1();
x.extraMethod2();
x.extraMethod3();
}
Improvements
As I told before JoinTwoExtraFeatures structure can be improved if we can remove recursion to ease the load on the compiler. Also, the merge of two packs still makes some comparisons that could be avoided.
I’m thinking about those two possible improvements it but I couldn’tcannot find a nice solution. If you discover a way to avoid the recursion and the superfluous comparisons, please share it with us by leaving a comment below.
You may also like
- 7 Ways to Get Better at C++ During this Summer
- 7 More Ways to Get Better at C++ This Summer (2018 Edition)
- Variadic CRTP: An Opt-in for Class Features, at Compile Time
- What the Curiously Recurring Template Pattern can bring to your code
Share this post!
