使整型序列在编译时唯一

假设我有:

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

最终为真。换句话说，让序列唯一，然后创建一个seq。
是否有办法在编译时实现这一点?

使用`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的参数包开始，然后使用模板专门化

一次取一个参数包的前面。

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表达式检查N是否在auto... Ms集合中，并决定是将N压入Ms还是使用std::conditional_t丢弃它。一旦auto... Ns为空，它就会使用专门化

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

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

使用`boost::mp11`

正如其他人指出的那样，您可以将算法委托给boost::mp11::mp_unique，但由于它适用于类型而不是值，因此为了使用这种方法，您需要将值与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.

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

的例子:

#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，你可以这样做:

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

要删除相邻的重复项(如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>>);

演示在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>>);

演示注意:constexprstd::vector通常甚至允许删除lambda中的重复代码。

使用c++ 20，仅使用STL

我在gcl库中使用了类似的东西。
(请注意，您可以将deduplicate_values替换为IIFE如果编译器允许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...中是否存在一个值
- 在失败时返回空std::tuple
- 成功返回std::tuple{value}
将values...扩展为std::tuple_cat(predicate(...))
重新打包std::元组元素到你想要的类型，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});

，在我看来，它不那么隐晦，所以更容易阅读/维护;同时保持编译时。
也避免了递归。

使用`std`

使用`boost::mp11`

使用c++ 20，仅使用STL

相关内容

最新更新

热门标签：

使整型序列在编译时唯一

使用std

使用boost::mp11

使用c++ 20，仅使用STL

相关内容

最新更新

热门标签：

使用`std`

使用`boost::mp11`