Make integer sequence unique at compile time

Question

Suppose I have:

template<int... N> class seq { };  template<int... N> struct uniq{     using type = seq<N...>; }; 

I need to make the sequence unique somehow, so that

std::is_same_v<uniq<1,2,2,2,3,3,3>::type, seq<1, 2, 3>>;  

ends up being true. In other words make the sequence unique then create a seq.
Is there a way to achieve this at compile time?

Answer 1

Using std

Using <type_traits> from the standard library, you can implement your own like this:

#include <type_traits>  namespace detail { template<class, auto... Ns> struct uniq_impl; template<template<auto...> class T, auto... Ms, auto N, auto... Ns> struct uniq_impl<T<Ms...>, N, Ns...> : std::conditional_t<     (... || (N == Ms)),     uniq_impl<T<Ms...>, Ns...>,     uniq_impl<T<Ms..., N>, Ns...>> { }; template<template<auto...> class T, auto... Ms> struct uniq_impl<T<Ms...>> {     using type = T<Ms...>; }; } // namespace detail  template<int... Ns> class seq { };  template<int... Ns> using uniq = detail::uniq_impl<seq<>, Ns...>;  static_assert(std::is_same_v<typename uniq<1,2,2,2,3,3,3>::type, seq<1, 2, 3>>); 

uniq_impl works by starting with an empty seq<> and a parameter pack of auto... Ns, then taking the front of the parameter pack one at a time using the template specialization

template<template<auto...> class T, auto... Ms, auto N, auto... Ns> struct uniq_impl<T<Ms...>, N, Ns...> : std::conditional_t<     (... || (N == Ms)),     uniq_impl<T<Ms...>, Ns...>,     uniq_impl<T<Ms..., N>, Ns...>> { }; 

it checks whether N is in the set of auto... Ms using a fold expression and decides whether to push N onto Ms or discard it using std::conditional_t. Once auto... Ns is empty, it then uses the specialization

template<template<auto...> class T, auto... Ms> struct uniq_impl<T<Ms...>> {     using type = T<Ms...>; }; 

to tag the resulting container of unique values. Try it on godbolt.org: Demo.

Using boost::mp11

As others have pointed out, you can delegate the algorithm to boost::mp11::mp_unique, but because it works for types and not values, you'll need to wrap and unwrap the values to and from std::integral_constant in order to use this approach:

#include <boost/mp11/algorithm.hpp>  namespace detail { template<template<auto...> class T, auto... Ns> class uniq_impl {     static boost::mp11::mp_list<std::integral_constant<decltype(Ns), Ns>...> types();      template <class L>     static boost::mp11::mp_unique<L> transform(L);      template<class... Ts, auto... Ms>     static T<Ms...> values(boost::mp11::mp_list<std::integral_constant<Ts, Ms>...>);  public:     using type = decltype(values(transform(types())));  }; } // namespace detail  template<int... Ns> class seq { };  template<int... Ns> using uniq = detail::uniq_impl<seq, Ns...>;  static_assert(std::is_same_v<typename uniq<1,2,2,2,3,3,3>::type, seq<1, 2, 3>>); 

Try it on godbolt.org: Demo.

Answer 2

You can use boost::mp11::mp_unique for this.

Example:

#include <boost/mp11.hpp>  namespace { template <int... N> using seq = boost::mp11::mp_list_c<int, N...>;  template <int... N> struct uniq {     using type = boost::mp11::mp_unique<seq<N...>>; }; }  int main() {     static_assert(std::is_same_v<uniq<1,2,2,2,3,3,3>::type, seq<1,2,3>>);     static_assert(std::is_same_v<uniq<4,1,9,9,2,2,3,1,5>::type, seq<4,1,9,2,3,5>>);     return 0; } 

If an alias isn't suitable for seq, you can do something like this:

template <int... N> struct seq {};  template <int... N> struct uniq { private:     template <int... Is>     static constexpr auto uniquer(boost::mp11::mp_list_c<int, Is...>) -> seq<Is...>;  public:     using type = decltype(uniquer(boost::mp11::mp_unique<boost::mp11::mp_list_c<int, N...>>{})); };