How to Implement std::conjunction and std::disjunction in C++11

Published April 30, 2021

Among the many features that C++17 introduced, the standard library got std::conjunction and its brother (or is it a sister?) std::disjunction.

std::conjunction allows to perform a logical AND on a variadic pack of boolean values, and std::disjunction a logical OR:

std::conjunction<Bs...>::value // is true if all Bs... are true, false otherwise

std::disjunction<Bs...>::value // is true if at least one of Bs... is true, false otherwise

Those convenient helpers simplify template code. It would be nice to have this feature available even if you’re not in C++17 yet.

It turns out we can implement it fairly easily in C++11. But before seeing how to implement it, let start by seeing how not to implement it.

How not to implement `std::conjunction` in C++11

You may wonder what the point is in seeing a wrong way to implement std::conjunction in C++11. The reason why this is interesting is that it shows a variadic template anti-pattern that we all need to be aware of: recursion.

Indeed, using recursion is often seen as a bad practice when it comes to manipulating variadic templates. The reason is that if the pack is large enough, then this becomes cumbersome for the compiler and can slow down the compilation.

Like many things in C++, it doesn’t mean that we should never ever do recursion with variadic templates. It rather means that we should always try to write variadic template code without using recursion.

The thing is that recursion is sometimes the first solution that comes to mind. Were it not for my friend Sy Brand that showed me a better solution, I wouldn’t have known how to implement conjunction other than with the following code:

template<class...> struct conjunction : std::true_type { };

template<class B1> struct conjunction<B1> : B1 { };

template<class B1, class... Bn>
struct conjunction<B1, Bn...> 
    : std::conditional<bool(B1::value), conjunction<Bn...>, B1>::type {};

This is pretty much the implementation suggested on cppreference.com.

We can see the recursion here: the code defines the cases of 0 and 1 parameter, and then a head-tail pattern where we define conjunction of the head-tail by calling conjunction on the tail. In the above code, B1 is the head and Bn... is the tail.

This code is very natural and expressive, but it uses the anti-pattern of recursion for variadic templates.

Can you see how to implement conjunction without recursion?

…

Come on, give it a go!

…

If you find something, please leave your solution in a comment, I’d love to read it.

…

Done yet, ready to read about Sy’s not recursive way?

How to implement `std::conjunction` in C++11

Here is an astute way to implement conjunction in C++11 and without recursion. Let’s look at the code, and explain it afterwards:

template<bool...> struct bool_pack{};

template<bool... Bs>
using conjunction = std::is_same<bool_pack<true,Bs...>, bool_pack<Bs..., true>>;

This is a pretty compact piece of code. Let’s see how this works.

bool_pack is a template containing a variadic pack of booleans. The struct itself has no data members or functions. Its sole purpose is to hold its pack of booleans. Hence the name, bool_pack.

The pack contains all the bools we’d like to apply a logical AND on, plus one:

conjunction

std::is_same compares the types, which includes comparing the respective template parameters. So if bool_pack<true, Bs...> and bool_pack<Bs..., true> are the same type, it means that:

B1 == true,
B2 == B1, which means that B2 == true,
B3 == B2, which means that B3 == true,
…
Bn == B(n-1), which means that Bn == true.

The last true of the second pack is redundant, but it has to be here because otherwise the two bool_pack would not have the same number of template parameters, and std::is_same would return false.

No recursion

Note how this implementation of conjunction doesn’t use recursion. Instead, it relies on the ability of the compiler to compare each corresponding element of two variadic packs.

`std::disjunction`

To implement std::conjunction, we relied on the compiler comparing variadic packs, which ensure that ALL types are the same. We arranged the packs to make it ensure that ALL booleans are equal to true.

Can we apply the same technique to implement std::disjunction?

std::disjunction seems to have a different need. Contrary to conjunction where we want ALL booleans to be true, for disjunction we need AT LEAST ONE boolean to be true. It seems more difficult to rely on the compiler comparing variadic types for this.

How would you implement disjunction in C++11? Please leave a comment below.

One way to implement disjunction is to reuse conjunction. Indeed, another way to express that AT LEAST ONE boolean is true is that it is false that ALL of them are false.

Here is what that would look like in code:

template <bool B>
using bool_constant = std::integral_constant<bool, B>; // redefining C++17 bool_constant helper

template<bool... Bs>
struct disjunction : bool_constant<!conjunction<!Bs...>::value>{};

This allows to implement disjunction in C++11 without using recursion.

Moving towards the future

If you’re in C++11, or in C++14, or in any other version of C++ that is not the last one available, it is important that you upgrade your compiler and platform in order to get access to the latest version of C++ available. Each recent version has added countless features to write more expressive code.

But upgrading compiler can be a long process, especially on large legacy codebases, or if you have dependencies with clients, or for any other reasons.

In the meantime, before the upgrade is done, you don’t have to limit yourself with the features of an old standard. With conjunction and disjunction, we have one more example that we can write modern code and that there are things to learn whatever the version of C++ we’re using.