Search code examples
c++templatesmetaprogrammingtemplate-meta-programming

Meta-program to remove adjacent duplicates from compile time vector

I have been trying to write a meta-function to remove adjacent duplicates from a compile time vector defined as

template <int...>
struct Vector;

Eg. If the input is:

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

Output should be:

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

But if input is:

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

output should be:

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

If the vector is unsorted, duplicates are expected.

I tried the following code:

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

I'm trying to recursively remove duplicates. If the first two elements are equal, then discard the first element and call uniq on the remaining elements. Otherwise take the first element and append with uniq for remaining elements.

However this code isn't working. Produces following errors.

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

I have tried a lots of things. Eg. std::conditional but can't seem to figure out why nothing works. I'm new to template metaprogramming and couldn't really find many examples on the internet.

Any help would be greatly appreciated. Thanks a lot.

Solution

    1. You don't need the template template parameter template<int...> class Vector.

    2. When first two elements are equal, one of them should be retained:

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

    3. You should handle empty pack, too. The easiest way is just to add ...:

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

    After these changes, your code will compile and static asserts will pass. Demo.

    For completeness, here is the corrected code:

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