Understanding why compile-time boolean algebra doesn't work

Question

I am trying to implement a basic template metaprogramming struct which determines if a list of types are all the same using std::is_same. I tried to implement it as follows:

template <typename T, typename U, typename... Args>
struct check_same {
     static const bool value = std::is_same<T, U>::value && check_same<U, Args...>::value;
};

template <typename T, typename U>
struct check_same {
     static const bool value = std::is_same<T, U>::value;
};

However, if I try to instantiate check_same I get the following compiler error:

'check_same' : too few template arguments

Why is this not a valid way to perform compile-time boolean algebra? Surely as all of the expressions involved are constexpr (or const here as MSVC doesn't yet implement constexpr), it should compile?

The following will fail to compile:

int main() 
{
    static_assert( check_same<int, unsigned int, float>::value, "Types must be the same" );

    return 0;
}

You're missing a type for `value`. Not sure what that has to do with your error. — chris, Jul 23 '14 at 15:18
[See this answer for a great `are_same` implementation](http://stackoverflow.com/a/24687161/701092) — David G, Jul 23 '14 at 15:30
"too few template arguments" because Args are consumed down to 0 by this recursion, and no check_same<> has less than 2 mandatory parameters. — Solkar, Jul 23 '14 at 16:35

AnT stands with Russia · Accepted Answer · 2014-07-23T16:00:12.400

Class templates in C++ cannot be "overloaded" like functions. You cannot redeclare the same template again and again with a different set of parameters and expect it to compile. For example, this will not compile

template <typename A> struct S {};
template <typename A, typename B> struct S {};

It will not compile because it attempts to declare template class S twice. This is illegal.

Your code suffers from exactly the same error: you have declared template check_same twice. You can't do that.

The technique you are apparently attempting to use should be based on template specialization, not on a template redeclaration. You have to declare your primary template only once

template <typename T, typename U, typename... Args>
struct check_same {
     static const bool value = std::is_same<T, U>::value && check_same<U, Args...>::value;
};

and then provide a partial specialization of that primary template for a specific, more restricted set of arguments

template <typename T, typename U>
struct check_same<T, U> {
     static const bool value = std::is_same<T, U>::value;
};

score 2 · Answer 2 · answered Jul 23 '14 at 15:36

2

Try this:

template <typename T, typename... Args>
struct check_same: std::true_type {};

template <typename T, typename U, typename...Args>
struct check_same<T,U,Args...>: std::integral_constant<bool,
  std::is_same<T,U>::value && check_same<U, Args...>::value
> {};

the first one only evaluates when there is exactly one argument. The second specialization catches 2 or more.

It errors if you pass 0 arguments. I'd argue that you should handle that as well:

template <typename... Args>
struct check_same: std::true_type {};

template <typename T, typename U, typename...Args>
struct check_same<T,U,Args...>: std::integral_constant<bool,
  std::is_same<T,U>::value && check_same<U, Args...>::value
> {};

which actually takes no more specializations, as the first works for both 0 and 1 argument.

answered Jul 23 '14 at 15:36

Yakk - Adam Nevraumont

262,606
27
330
524

@dyp how does that reduce number of instantiations? You get 3 types instantiated per recursion, same as me? – Yakk - Adam Nevraumont Jul 23 '14 at 16:21
It's some kind of short-circuiting: the recursion ends when one check returns `false` and the remaining checks are not performed. However you get one more instantiation per step due to the `conditional`, so it's probably not worth it. – dyp Jul 23 '14 at 16:29
@dyp both branches of conditional are fully evaluated, so the checks are performed, just discarded. To pull off a short-circuit, you need to do more work than `conditional`. – Yakk - Adam Nevraumont Jul 23 '14 at 16:31
+1 for using `std::integral_constant` for this. loc are too precious to waste them, aren't they. – Solkar Jul 23 '14 at 16:39
Huh? Why should the branch which is not used require an instantiation? http://coliru.stacked-crooked.com/a/2c7146fd7e7c8dfe – dyp Jul 23 '14 at 16:42
@dyp The full type of the `std::conditional` instance must be instantiated, which is `std::conditional< false, LHS, RHS >`. Both `LHS` and `RHS` must be full types, which means any `template` expressions get fully instantiated on both branches. In order to avoid this, you need `typename my_lazy_conditional< false, LHS_template, RHS_template >::template apply< pack< LHS_args >, pack< RHS_args > >::type` or something like it. – Yakk - Adam Nevraumont Jul 23 '14 at 19:49
Why do `LHS` and `RHS` have to be full types? IIRC, implicit instantiations are required only if a completely-defined object type is *required*, I don't see why `conditional` should require that. You can even use incomplete types: http://coliru.stacked-crooked.com/a/62a5bbadd53779d3 – dyp Jul 23 '14 at 19:52

Understanding why compile-time boolean algebra doesn't work

2 Answers2