CODEWITHSUNDEEP
c++templatesc++11variadic-templates
Jytug
Jytug

Reputation: 1116

Ensuring that a variadic template contains no duplicates

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.

Upvotes: 4

Views: 1276

Answers (4)

Rumburak
Rumburak

Reputation: 3571

Below is the simplest version I can think of (works with C++11 and beyond). It uses the fact the no two direct base classes shall be the same:

template<typename T>
struct unique_base{};

template<typename... T>
struct require_unique : public unique_base<T>... {
  static constexpr bool value = true;
};

You can use it like this:

template <typename... T>
struct sample
{
  static_assert(require_unique<T...>::value, "");
};

int main() {
  auto x = sample<int, float, double>{};
  // auto y = sample<int, float, double, float>{}; // fails to compile
}

I tested with gcc and clang. Both compilers report the offending duplicate (if any) in an error message.

Note that you cannot use this in SFINAE. But if you really just want to enforce uniqueness...

Upvotes: 0

Fabio A.
Fabio A.

Reputation: 2724

With c++17 this is pretty easy.

#include <type_traits>

template <typename T, typename... Ts>
struct are_distinct: std::conjunction<
    std::negation<std::is_same<T, Ts>>...,
    are_distinct<Ts...>
>{};

template <typename T>
struct are_distinct<T>: std::true_type{};

The algorithm is the same as the one illustrated by Jkor and TheOperator, but expressed much more concisely.

Then, coming to your specific question, you'd use it this way:

template<typename ...Types> 
struct MyVariadicTemplate {
    static_assert(are_distinct<Types...>::value, "Types must be distinct");

    /* rest of the code */
};

However, given this is O(n²), I wonder if there's a way to make it less algorithmically complex? Boost::mpl's unique<> is O(n), but I can't get my head around the algo it uses.

Upvotes: -1

JKor
JKor

Reputation: 3832

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.

Upvotes: 2

TheOperator
TheOperator

Reputation: 6466

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");
};

Upvotes: 6

Related Questions