从编译时向量中删除相邻重复项的元程序

Question

我一直在尝试编写一个元函数来从定义为

的编译时向量中删除相邻的重复项

template <int...>
struct Vector;

例如。如果输入是：

Vector<1, 2, 2, 3, 3, 4, 5, 5>

输出应该是：

Vector<1, 2, 3, 4, 5>

但是如果输入是：

Vector<1, 2, 2, 3, 4, 4, 1, 5>

输出应该是：

Vector<1, 2, 3, 4, 1, 5>

如果矢量未排序，则应为重复项。

我尝试了以下代码：

#include <iostream>
#include <type_traits>

template <int...>
struct Vector;

template <int I, int... L>
struct Vector<I, L...> {
    int First = I;
};

template <int Elem, typename Vector>
struct Append {
    using type = Vector;
};

template <template<int...> class Vector, int Elem, int... VecArgs>
struct Append<Elem, Vector<VecArgs...>> {
    using type = Vector<Elem, VecArgs...>;
};

template <typename Vector>
struct uniq;

template <template<int...> class Vector, int First, int... Last>
struct uniq<Vector<First, First, Last...>> {
    using type = typename uniq<Vector<Last...>>::type;
};

template <template<int...> class Vector, int First, int... Last>
struct uniq<Vector<First, Last...>> {
    using type = typename Append<First, uniq<Vector<Last...>>::type>::type;
};

template <template<int> typename Vector, int I>
struct uniq<Vector<I>> {
    using type = Vector<I>;
};


int solution(int X) {
    static_assert(std::is_same<uniq<Vector<1, 2, 2, 3, 4, 4>>::type, Vector<1, 2, 3, 4>>::value);
    static_assert(std::is_same<uniq<Vector<1>>::type, uniq<Vector<1>>::type>::value);
    //static_assert(std::is_same<Vector<1, 2, 3>, Append<1, Vector<2, 3>>::type>::value);
    return X;
}

int main() {
    solution(1);
}

我正在尝试递归删除重复项。如果前两个元素相等，则丢弃第一个元素并对其余元素调用 uniq。否则取第一个元素并为剩余元素附加 uniq。

但是此代码无效。产生以下错误。

meta.cpp:32:65: error: type/value mismatch at argument 2 in template parameter list for ‘template<int Elem, class Vector> struct Append’
  using type = typename Append<First, uniq<Vector<Last...>>::type>::type;
                                                                 ^
meta.cpp:32:65: note:   expected a type, got ‘uniq<Vector<Last ...> >::type’
meta.cpp: In function ‘int solution(int)’:
meta.cpp:42:61: error: ‘type’ is not a member of ‘uniq<Vector<1, 2, 2, 3, 4, 4> >’
  static_assert(std::is_same<uniq<Vector<1, 2, 2, 3, 4, 4>>::type, Vector<1, 2, 3, 4>>::value);
                                                             ^~~~
meta.cpp:42:61: error: ‘type’ is not a member of ‘uniq<Vector<1, 2, 2, 3, 4, 4> >’
meta.cpp:42:84: error: template argument 1 is invalid
  static_assert(std::is_same<uniq<Vector<1, 2, 2, 3, 4, 4>>::type, Vector<1, 2, 3, 4>>::value);
                                                                                    ^~
meta.cpp:43:46: error: ‘type’ is not a member of ‘uniq<Vector<1> >’
  static_assert(std::is_same<uniq<Vector<1>>::type, uniq<Vector<1>>::type>::value);
                                              ^~~~
meta.cpp:43:46: error: ‘type’ is not a member of ‘uniq<Vector<1> >’
meta.cpp:43:69: error: ‘type’ is not a member of ‘uniq<Vector<1> >’
  static_assert(std::is_same<uniq<Vector<1>>::type, uniq<Vector<1>>::type>::value);
                                                                     ^~~~
meta.cpp:43:69: error: ‘type’ is not a member of ‘uniq<Vector<1> >’
meta.cpp:43:73: error: template argument 1 is invalid
  static_assert(std::is_same<uniq<Vector<1>>::type, uniq<Vector<1>>::type>::value);
                                                                         ^
meta.cpp:43:73: error: template argument 2 is invalid

我尝试了很多东西。例如。 std::conditional 但似乎无法弄清楚为什么没有任何效果。我是模板元编程的新手，在互联网上找不到很多示例。

如有任何帮助，我们将不胜感激。非常感谢。

Answer 1

您不需要模板模板参数template<int...> class Vector。

当前两个元素相等时，保留其中一个：

template <template<int...> class Vector, int First, int... Last>
struct uniq<Vector<First, First, Last...>> {
    using type = typename uniq<Vector<First, Last...>>::type;
    //                                ^^^^^
};

你也应该处理空包。最简单的方法就是添加 ...:

template<int... I>
struct uniq<Vector<I...>> {
    using type = Vector<I...>;
};

进行这些更改后，您的代码将编译并且静态断言将通过。 Demo.

为了完整起见，这里是更正后的代码：

template<int Elem, typename Vector>
struct Append;

template<int Elem, int... VecArgs>
struct Append<Elem, Vector<VecArgs...>> {
    using type = Vector<Elem, VecArgs...>;
};

template<typename Vector>
struct uniq;

template<int First, int... Last>
struct uniq<Vector<First, First, Last...>> {
    using type = typename uniq<Vector<First, Last...>>::type;
};

template<int First, int... Last>
struct uniq<Vector<First, Last...>> {
    using type = typename Append<First, 
        typename uniq<Vector<Last...>>::type>::type;
};

template<int... I>
struct uniq<Vector<I...>> {
    using type = Vector<I...>;
};

Answer 2

template <typename T> concept Integral = std::is_integral<T>::value

// concat, append rhs to lhs
template <Integral INT, INT... lhs, INT... rhs>
constexpr std::integer_sequence<INT, lhs..., rhs...>
concat(std::integer_sequence<INT, lhs...>, std::integer_sequence<INT, rhs...>) {
  return {};
}

template <Integral INT, INT... lhs, INT... rhs, class... Others>
constexpr auto concat(std::integer_sequence<INT, lhs...>,
                      std::integer_sequence<INT, rhs...>, Others...) {
  return concat(std::integer_sequence<INT, lhs..., rhs...>{}, Others{}...);
}


// CAUTION: only works for sorted parameters
// for example, 3,3,4,5,5,4 will get 3,4,5,4
template <Integral INT, INT I0, INT I1, INT... Is>
constexpr auto unique_sorted(std::integer_sequence<INT, I0, I1, Is...>) {
  if constexpr (I0 == I1)
    return std::integer_sequence<INT, I0, I1, Is...>{};
  else
    return concat(std::integer_sequence<INT, I0>{},
                  std::integer_sequence<INT, I1, Is...>{});
}

template <Integral INT, INT I0>
constexpr auto unique_sorted(std::integer_sequence<INT, I0>) {
  return std::integer_sequence<INT, I0>{};
}

template <Integral INT>
constexpr auto unique_sorted(std::integer_sequence<INT>) {
  return std::integer_sequence<INT>{};
}

我用 gcc 10 和 c++2a 编译了它。您可以使用 boost::mp11 将 std::integer_sequence 转换为您想要的类型。

Answer 3

这是一个基于 constexpr 的解决方案：

template <int...> struct Vector{};

template<int HEAD, int ... TAIL> struct Vector<HEAD,TAIL...>{
    static constexpr auto head(){ return HEAD; }
    using tail = Vector<TAIL...>;
};

template<int I, int... ints>
constexpr auto  cons(Vector<ints...>){ return Vector<I,ints...>{}; }

template<int... ints>
constexpr auto  remove_duplicates(Vector<ints...> vec){
    using Vec = Vector<ints...>;
    if constexpr(sizeof...(ints)<2)
        return vec;
    else if constexpr( Vec::head() == Vec::tail::head() )
        return remove_duplicates(typename Vec::tail{});
    else
        return cons<vec.head()>( remove_duplicates(typename Vec::tail{}) );
}

template <typename VECTOR>
using remove_duplicates_t = decltype(remove_duplicates(VECTOR{}));

#include <type_traits>
int main() {
    static_assert(std::is_same_v<Vector<1,2,3>,remove_duplicates_t<Vector<1,2,3>>> );
    static_assert(std::is_same_v<Vector<1,2,3,1>,remove_duplicates_t<Vector<1,2,2,3,3,3,1,1>>> );
    return 0;
}

从编译时向量中删除相邻重复项的元程序

Meta-program to remove adjacent duplicates from compile time vector

c++

templates

metaprogramming

template-meta-programming