Meta-program to remove adjacent duplicates from compile time vector

user_3286661 0
Viewed 752

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.

template-meta-programming templates metaprogramming c++
3 Answers

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

I compiled it with gcc 10 and c++2a. You can use boost::mp11 to convert std::integer_sequence to the type you want.

user_29513770

Here is a constexpr based solution:

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