Make integer sequence unique at compile time
To remove adjacent duplicates (as for std::unique
), you might do:
template <typename Seq, typename Res = std::index_sequence<>>
struct reverse;
template <typename Res>
struct reverse<std::index_sequence<>, Res>
{
using type = Res;
};
template <std::size_t I, std::size_t ... Is, std::size_t ... Js>
struct reverse<std::index_sequence<I, Is...>, std::index_sequence<Js...>> : reverse<std::index_sequence<Is...>, std::index_sequence<I, Js...>>
{};
template <typename Seq, typename Res = std::index_sequence<>>
struct uniq;
template <typename Res>
struct uniq<std::index_sequence<>, Res>
{
using type = typename reverse<Res>::type;
};
template <std::size_t I, std::size_t ... Is, std::size_t ... Js>
struct uniq<std::index_sequence<I, Is...>, std::index_sequence<I, Js...>> : uniq<std::index_sequence<Is...>, std::index_sequence<I, Js...>> {};
template <std::size_t I, std::size_t ... Is, std::size_t ... Js>
struct uniq<std::index_sequence<I, Is...>, std::index_sequence<Js...>> : uniq<std::index_sequence<Is...>, std::index_sequence<I, Js...>> {};
static_assert(std::is_same_v<reverse<std::index_sequence<3, 2, 1>>::type, std::index_sequence<1, 2, 3>>);
static_assert(std::is_same_v<uniq<std::index_sequence<1,2,2,2,3,3,3>>::type, std::index_sequence<1, 2, 3>>);
Demo
With C++20, some algorithms become even constexpr
and allows:
template <std::size_t ... Is, std::size_t ... Js>
consteval auto unique_impl(std::index_sequence<Is...>, std::index_sequence<Js...>)
{
constexpr std::array<std::size_t, sizeof...(Is)> arr = [](){
std::array<std::size_t, sizeof...(Is)> arr{{Is...}};
//std::sort(arr.begin(), arr.end());
std::unique(arr.begin(), arr.end());
return arr;
}();
return std::index_sequence<arr[Js]...>{};
}
template <std::size_t ... Is>
consteval auto unique_impl(std::index_sequence<Is...> seq)
{
constexpr std::size_t size = [](){
std::array<std::size_t, sizeof...(Is)> arr{{Is...}};
//std::sort(arr.begin(), arr.end());
auto it = std::unique(arr.begin(), arr.end());
return std::distance(arr.begin(), it);
}();
return unique_impl(seq, std::make_index_sequence<size>());
}
template <std::size_t ... Is>
using unique = decltype(unique_impl(std::index_sequence<Is...>{}));
static_assert(std::is_same_v<unique<1,2,2,2,3,3,3>, std::index_sequence<1, 2, 3>>);
Demo
Note: constexpr std::vector
would normally even allow to remove duplicated code in lambda.
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.
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...>>{}));
};