使整数序列在编译时唯一

Question

假设我有：

template<int... N>
class seq
{
};

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

我需要以某种方式使序列唯一，以便

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

结果是真的。换句话说，使序列唯一然后创建一个序列。
有没有办法在编译时实现这个？

Answer 1

您可以为此使用 boost::mp11::mp_unique。

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

如果别名不适合 seq，您可以使用 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...>>{}));
};

Answer 2

要删除相邻的重复项（对于 std::unique），您可以这样做：

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

使用 C++20，一些算法变得偶数 constexpr 并允许：

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

注意：constexpr std::vector 通常甚至允许删除 lambda 中的重复代码。

Answer 3

使用`std`

使用标准库中的 <type_traits>，您可以像这样实现自己的：

#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 的工作方式是从一个空 seq<> 和一个参数包 auto... Ns 开始，然后使用模板特化 [= 一次一个地获取参数包的前面33=]

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

它使用 fold expression and decides whether to push N onto Ms or discard it using std::conditional_t 检查 N 是否在 auto... Ms 的集合中。一旦 auto... Ns 为空，它就会使用特化

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

标记唯一值的结果容器。在 godbolt.org 上试用：Demo.

使用`boost::mp11`

As , you can delegate the algorithm to boost::mp11::mp_unique, but because , you'll need to wrap and unwrap the values to and from std::integral_constant 为了使用这个方法：

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

在 godbolt.org 上试用：Demo。

Answer 4

使用 C++20，仅限 STL

我在 gcl 库中使用了类似的东西。
（请注意，您可以用 IIFE lambda 替换 deduplicate_values，如果您的编译器允许 lambda 在未评估的上下文中 )

现场示例：https://godbolt.org/z/KzjWrM

template <auto ... values>
struct sequence{};

template <auto ... values>
constexpr auto deduplicate_values()
{
    constexpr auto arguments = std::tuple{values...};
    constexpr auto element_if_predicate = [arguments]<auto argument, std::size_t argument_index>() consteval {
        constexpr auto has_previous_position = [&arguments]<std::size_t ... indexes>(std::index_sequence<indexes...>) consteval {
            return (((std::get<indexes>(arguments) == argument) || ...));
        }(std::make_index_sequence<argument_index>{});
        if constexpr (has_previous_position)
            return std::tuple{};
        else return std::tuple{argument};
    };

    constexpr auto deduplicated_values_as_tuple = [&arguments, element_if_predicate]<std::size_t ... indexes>(std::index_sequence<indexes...>) consteval {
        return std::tuple_cat(element_if_predicate.template operator()<std::get<indexes>(arguments), indexes>()...);
    }(std::make_index_sequence<std::tuple_size_v<decltype(arguments)>>{});

    return [&deduplicated_values_as_tuple]<std::size_t ... indexes>(std::index_sequence<indexes...>) consteval {
        return sequence<std::get<indexes>(deduplicated_values_as_tuple)...>{};
    }(std::make_index_sequence<std::tuple_size_v<decltype(deduplicated_values_as_tuple)>>{});
}

template <auto ... values>
using deduplicated_sequence = decltype(deduplicate_values<values...>());

static_assert(std::is_same_v<sequence<1,2,3>, deduplicated_sequence<1,2,3,1,2,3>>);

解释：

将值包装成元组
创建一个谓词来检查某个值以前是否存在于 values...
- returns 空 std::tuple 失败
- returns std::tuple{value} 成功
将 values... 展开为 std::tuple_cat(predicate(...))
将 std::tuple 元素重新打包成您想要的类型，sequence

gcl 图书馆代码：

template <auto ... values>
constexpr auto tuple_erase_duplicate_values()
{
    constexpr auto arguments = std::tuple{values...};

    constexpr auto element_if_predicate = [arguments]<auto argument, std::size_t argument_index>() consteval {
        constexpr auto has_previous_position = [&arguments]<std::size_t ... indexes>(std::index_sequence<indexes...>) consteval {
            return (((std::get<indexes>(arguments) == argument) || ...));
        }(std::make_index_sequence<argument_index>{});

        if constexpr (has_previous_position)
            return std::tuple{};
        else return std::tuple{argument};
    };

    return [&arguments, element_if_predicate]<std::size_t ... indexes>(std::index_sequence<indexes...>) consteval {
        return std::tuple_cat(element_if_predicate.template operator()<std::get<indexes>(arguments), indexes>()...);
    }(std::make_index_sequence<std::tuple_size_v<decltype(arguments)>>{});
}
static_assert(tuple_erase_duplicate_values<'a', 'b', 'a', 1, 2, 1>() == std::tuple{'a', 'b', 1, 2});

在我看来，这不那么神秘，更容易理解 read/maintain；同时保留编译时间。
此外，它避免了递归。

使整数序列在编译时唯一

Make integer sequence unique at compile time

c++

templates

template-meta-programming

c++17

使用`std`

使用`boost::mp11`

使用 C++20，仅限 STL

使整数序列在编译时唯一

Make integer sequence unique at compile time

c++

templates

template-meta-programming

c++17

使用std

使用boost::mp11

使用 C++20，仅限 STL

使用`std`

使用`boost::mp11`