确保可变参数模板不包含重复项

Question

我想标题中已经很好地描述了我的整个问题。我正在尝试创建一个可变参数类模板（在 C++11、C++14 或 C++1z 中）。

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

并确保

MyVariadicTemplate

的任何实例化中的类型列表都是单射的，因此，例如，如果我调用以下代码：

MyVariadicTemplate<int, double, int> x;

它不会编译（我很乐意使用

static_assert

以某种方式做到这一点）。

我希望得到提示。

Answer 1

这可以借助两个元函数来编写。

首先，

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

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

其次，

IsUnique

检查类型列表是否不包含重复项。它使用

IsContained

检查所有元素组合。

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

有了这些工具，静态断言就变得非常简单：

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

Answer 2

如果您有权访问 C++1z 折叠表达式，您可以通过对

IsContained

执行以下操作来简化 @TheOperator 的答案：

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

不同之处在于，使用折叠表达式，重用类实例化的机会更大。 如果您使用大量参数或进行多次重复比较，这可能会有更快的编译时间。一如既往，亲自测试一下。

Answer 3

下面是我能想到的最简单的版本（适用于 C++11 及更高版本）。它利用了没有两个直接基类应该相同的事实：

template<typename T>
struct unique_base{};

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

你可以这样使用它：

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
}

我用 gcc 和 clang 进行了测试。两个编译器都会在错误消息中报告有问题的重复项（如果有）。

请注意，您不能在 SFINAE 中使用它。但如果你真的只是想强制唯一性......

Answer 4

使用 c++17 这非常简单。

#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{};

该算法与Jkor和TheOperator所示的算法相同，但表达更简洁。

然后，针对您的具体问题，您可以这样使用它：

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

    /* rest of the code */
};

但是，考虑到这是 O(n²)，我想知道是否有办法降低算法复杂度？ Boost::mpl 的 unique<> 是 O(n)，但我无法理解它使用的算法。