Ensuring that a variadic template contains no duplicates

Question

I guess my whole problem is well described in the title. I am trying to create a variadic class template (in C++11, C++14 or C++1z).

template<typename ...Types> struct MyVariadicTemplate {};

and make sure that the list of types in any instantiation of MyVariadicTemplate is injective, so if I, for instance, call the following piece of code:

MyVariadicTemplate<int, double, int> x;

it won't compile (I'd be happy to do that somehow using static_assert).

I would appreciate a hint.

Answer 1

This can be written with the help of two metafunctions.

First, IsContained checks whether a type appears in a type list.

template <typename T, typename... List>
struct IsContained;

template <typename T, typename Head, typename... Tail>
struct IsContained<T, Head, Tail...>
{
    enum { value = std::is_same<T, Head>::value || IsContained<T, Tail...>::value };
};

template <typename T>
struct IsContained<T>
{
    enum { value = false };
};

Second, IsUnique checks whether a type list contains no duplicates. It uses IsContained to check all element combinations.

template <typename... List>
struct IsUnique;

template <typename Head, typename... Tail>
struct IsUnique<Head, Tail...>
{
    enum { value = !IsContained<Head, Tail...>::value && IsUnique<Tail...>::value };
};

template <>
struct IsUnique<>
{
    enum { value = true };
};

With these tools, the static assertion is then very simple:

template <typename... Ts>
struct NoDuplicates
{
    static_assert(IsUnique<Ts...>::value, "No duplicate types allowed");
};

Answer 2

If you have access to C++1z fold expressions, you can simplify @TheOperator's answer by doing the following for IsContained:

template <typename T, typename... List>
struct IsContained;

template <typename T, typename Head, typename... Tail>
struct IsContained<T, Head, Tail...>
{
    enum { value = std::is_same<T, Head>::value || (IsContained<T, Tail>::value && ... && true) };
};

template <typename T>
struct IsContained<T>
{
    enum { value = false };
};

The difference is that with the fold expression there is a larger chance of re-use of the class instantiations. If you are using a lot of parameters or have many repeat comparisons, this might have a faster compilation time. As always, test it out yourself.