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.