删除元组中相邻的重复项

Question

目标:删除元组中重复相邻项的函数。

例如: std::tuple(1,1,2,3,1,4,5)变成std::tuple(1,2,3,1,4,5)

我的失败尝试：

#include <iostream>
#include <cstdint>
#include <tuple>

template <uint32_t n, typename Tuple, std::size_t... Is>
constexpr auto pop_front_helper(const Tuple& input, std::index_sequence<Is...>) {
    return std::make_tuple(std::get<n + Is>(input)...);
}

template <uint32_t n, typename Tuple>
constexpr auto pop_front(const Tuple& input) {
    using is_t = std::make_index_sequence<std::tuple_size<Tuple>::value - n>;
    return pop_front_helper<n>(input, is_t());
}

template <typename Element, size_t... Is>
constexpr auto remove_duplicate_adjacent_helper(const std::tuple<Element>& input, const std::index_sequence<Is...>&) noexcept {
    return input;
}

template <typename Tuple>
constexpr auto remove_duplicate_adjacent(const Tuple& input) noexcept;

template <typename Tuple, size_t... Is>
constexpr auto remove_duplicate_adjacent_helper(const Tuple& input, const std::index_sequence<Is...>&) noexcept {
    if (std::get<0>(input) == std::get<1>(input)) {
        if constexpr (2 == std::tuple_size<Tuple>::value) {
            return std::tuple(std::get<0>(input));
        }
        return std::tuple_cat(std::tuple(std::get<0>(input)), pop_front<2>(input));
    }
    return std::tuple_cat(std::tuple(std::get<0>(input)), remove_duplicate_adjacent(std::make_tuple(std::get<1 + Is>(input)...)));
}

template <typename Tuple>
constexpr auto remove_duplicate_adjacent(const Tuple& input) noexcept {
    return remove_duplicate_adjacent_helper(input, std::make_index_sequence<std::tuple_size<Tuple>::value - 1>());
}

template <typename Tuple, std::size_t... Is>
void dump_helper(const Tuple& input, const std::index_sequence<Is...>&) {
    (..., (std::cout << (0 == Is ? "" : ", " ) << std::get<Is>(input)));
    std::cout << std::endl;
}

template <typename Tuple>
void dump(const Tuple& input) {
    dump_helper(input, std::make_index_sequence<std::tuple_size<Tuple>::value - 1>());
}

int main() {
    constexpr std::tuple t1(1,1,2,3,1,4,5);
    const auto& r1 = remove_duplicate_adjacent(t1);
    dump(r1);
}

它失败了，因为在编译时，在remove_duplicate_adjacent_helper()中，编译器看到超过1个可能的返回类型。我不能用if constexpr替换if，因为在函数的上下文中，input是一个不能为constexpr的变量：

remove_duplicate_adjacent.cpp: In instantiation of ‘constexpr auto remove_duplicate_adjacent_helper(const Tuple&, std::index_sequence<Is ...>&) [with Tuple = std::tuple<int, int>; long unsigned int ...Is = {0}; std::index_sequence<Is ...> = std::integer_sequence<long unsigned int, 0>]’:
remove_duplicate_adjacent.cpp:37:41:   required from ‘constexpr auto remove_duplicate_adjacent(const Tuple&) [with Tuple = std::tuple<int, int>]’
remove_duplicate_adjacent.cpp:32:81:   required from ‘constexpr auto remove_duplicate_adjacent_helper(const Tuple&, std::index_sequence<Is ...>&) [with Tuple = std::tuple<int, int, int>; long unsigned int ...Is = {0, 1}; std::index_sequence<Is ...> = std::integer_sequence<long unsigned int, 0, 1>]’
remove_duplicate_adjacent.cpp:37:41:   required from ‘constexpr auto remove_duplicate_adjacent(const Tuple&) [with Tuple = std::tuple<int, int, int>]’
remove_duplicate_adjacent.cpp:32:81:   required from ‘constexpr auto remove_duplicate_adjacent_helper(const Tuple&, std::index_sequence<Is ...>&) [with Tuple = std::tuple<int, int, int, int>; long unsigned int ...Is = {0, 1, 2}; std::index_sequence<Is ...> = std::integer_sequence<long unsigned int, 0, 1, 2>]’
remove_duplicate_adjacent.cpp:37:41:   [ skipping 2 instantiation contexts, use -ftemplate-backtrace-limit=0 to disable ]
remove_duplicate_adjacent.cpp:37:41:   required from ‘constexpr auto remove_duplicate_adjacent(const Tuple&) [with Tuple = std::tuple<int, int, int, int, int>]’
remove_duplicate_adjacent.cpp:32:81:   required from ‘constexpr auto remove_duplicate_adjacent_helper(const Tuple&, std::index_sequence<Is ...>&) [with Tuple = std::tuple<int, int, int, int, int, int>; long unsigned int ...Is = {0, 1, 2, 3, 4}; std::index_sequence<Is ...> = std::integer_sequence<long unsigned int, 0, 1, 2, 3, 4>]’
remove_duplicate_adjacent.cpp:37:41:   required from ‘constexpr auto remove_duplicate_adjacent(const Tuple&) [with Tuple = std::tuple<int, int, int, int, int, int>]’
remove_duplicate_adjacent.cpp:32:81:   required from ‘constexpr auto remove_duplicate_adjacent_helper(const Tuple&, std::index_sequence<Is ...>&) [with Tuple = std::tuple<int, int, int, int, int, int, int>; long unsigned int ...Is = {0, 1, 2, 3, 4, 5}; std::index_sequence<Is ...> = std::integer_sequence<long unsigned int, 0, 1, 2, 3, 4, 5>]’
remove_duplicate_adjacent.cpp:37:41:   required from ‘constexpr auto remove_duplicate_adjacent(const Tuple&) [with Tuple = std::tuple<int, int, int, int, int, int, int>]’
remove_duplicate_adjacent.cpp:53:47:   required from here
remove_duplicate_adjacent.cpp:32:23: error: inconsistent deduction for auto return type: ‘std::tuple<int>’ and then ‘std::tuple<int, int>’
   32 |  return std::tuple_cat(std::tuple(std::get<0>(input)), remove_duplicate_adjacent(std::make_tuple(std::get<1 + Is>(input)...)));
      |         ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

在template <int64_t... Vs> struct Foo;中删除重复相邻是可能的，因为模板参数的所有值在编译时都是已知的(一种constexpr)。我不确定如何删除tuple中的重复相邻项。

谢谢。

===

更新#1

根据@康桓瑋在评论中的建议，我将remove_duplicate_adjacent_helper()更改为

template <typename Tuple, size_t... Is>
constexpr auto remove_duplicate_adjacent_helper(const Tuple& input, const std::index_sequence<Is...>&) noexcept -> std::variant<decltype(pop_front<Is>(input))...> {
    if (std::get<0>(input) == std::get<1>(input)) {
        if constexpr (2 == std::tuple_size<Tuple>::value) {
            return std::tuple(std::get<0>(input));
        }
        return std::tuple_cat(std::tuple(std::get<0>(input)), pop_front<2>(input));
    }
    return std::tuple_cat(std::tuple(std::get<0>(input)), std::visit([](const auto& t){ return t;}, remove_duplicate_adjacent(std::make_tuple(std::get<1 + Is>(input)...))));
}

编译器给出了一个错误：

In file included from remove_duplicate_adjacent.cpp:4:
/opt/rh/devtoolset-10/root/usr/include/c++/10/variant: In instantiation of ‘static constexpr auto std::__detail::__variant::__gen_vtable_impl<std::__detail::__variant::_Multi_array<_Result_type (*)(_Visitor, _Variants ...)>, std::integer_sequence<long unsigned int, __indices ...> >::_S_apply() [with _Result_type = std::__detail::__variant::__deduce_visit_result<std::tuple<int, int, int, int, int, int> >; _Visitor = remove_duplicate_adjacent_helper<std::tuple<int, int, int, int, int, int, int>, {0, 1, 2, 3, 4, 5}>::<lambda(const auto:34&)>&&; _Variants = {std::variant<std::tuple<int, int, int, int, int, int>, std::tuple<int, int, int, int, int>, std::tuple<int, int, int, int>, std::tuple<int, int, int>, std::tuple<int, int> >&&}; long unsigned int ...__indices = {1}]’:
/opt/rh/devtoolset-10/root/usr/include/c++/10/variant:976:56:   required from ‘static constexpr void std::__detail::__variant::__gen_vtable_impl<std::__detail::__variant::_Multi_array<_Result_type (*)(_Visitor, _Variants ...), __dimensions ...>, std::integer_sequence<long unsigned int, _Idxs ...> >::_S_apply_single_alt(_Tp&, _Tp*) [with bool __do_cookie = false; long unsigned int __index = 1; _Tp = std::__detail::__variant::_Multi_array<std::__detail::__variant::__deduce_visit_result<std::tuple<int, int, int, int, int, int> > (*)(remove_duplicate_adjacent_helper<std::tuple<int, int, int, int, int, int, int>, {0, 1, 2, 3, 4, 5}>::<lambda(const auto:34&)>&&, std::variant<std::tuple<int, int, int, int, int, int>, std::tuple<int, int, int, int, int>, std::tuple<int, int, int, int>, std::tuple<int, int, int>, std::tuple<int, int> >&&)>; _Result_type = std::__detail::__variant::__deduce_visit_result<std::tuple<int, int, int, int, int, int> >; _Visitor = remove_duplicate_adjacent_helper<std::tuple<int, int, int, int, int, int, int>, {0, 1, 2, 3, 4, 5}>::<lambda(const auto:34&)>&&; long unsigned int ...__dimensions = {5}; _Variants = {std::variant<std::tuple<int, int, int, int, int, int>, std::tuple<int, int, int, int, int>, std::tuple<int, int, int, int>, std::tuple<int, int, int>, std::tuple<int, int> >&&}; long unsigned int ...__indices = {}]’
/opt/rh/devtoolset-10/root/usr/include/c++/10/variant:955:48:   required from ‘constexpr const _Array_type std::__detail::__variant::__gen_vtable<std::__detail::__variant::__deduce_visit_result<std::tuple<int, int, int, int, int, int> >, remove_duplicate_adjacent_helper<std::tuple<int, int, int, int, int, int, int>, {0, 1, 2, 3, 4, 5}>::<lambda(const auto:34&)>&&, std::variant<std::tuple<int, int, int, int, int, int>, std::tuple<int, int, int, int, int>, std::tuple<int, int, int, int>, std::tuple<int, int, int>, std::tuple<int, int> >&&>::_S_vtable’
/opt/rh/devtoolset-10/root/usr/include/c++/10/variant:1699:45:   required from ‘constexpr decltype(auto) std::__do_visit(_Visitor&&, _Variants&& ...) [with _Result_type = std::__detail::__variant::__deduce_visit_result<std::tuple<int, int, int, int, int, int> >; _Visitor = remove_duplicate_adjacent_helper<std::tuple<int, int, int, int, int, int, int>, {0, 1, 2, 3, 4, 5}>::<lambda(const auto:34&)>; _Variants = {std::variant<std::tuple<int, int, int, int, int, int>, std::tuple<int, int, int, int, int>, std::tuple<int, int, int, int>, std::tuple<int, int, int>, std::tuple<int, int> >}]’
/opt/rh/devtoolset-10/root/usr/include/c++/10/variant:1718:35:   required from ‘constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...) [with _Visitor = remove_duplicate_adjacent_helper<std::tuple<int, int, int, int, int, int, int>, {0, 1, 2, 3, 4, 5}>::<lambda(const auto:34&)>; _Variants = {std::variant<std::tuple<int, int, int, int, int, int>, std::tuple<int, int, int, int, int>, std::tuple<int, int, int, int>, std::tuple<int, int, int>, std::tuple<int, int> >}]’
remove_duplicate_adjacent.cpp:44:66:   required from ‘constexpr std::variant<decltype (pop_front<Is>(input))...> remove_duplicate_adjacent_helper(const Tuple&, std::index_sequence<__indices ...>&) [with Tuple = std::tuple<int, int, int, int, int, int, int>; long unsigned int ...Is = {0, 1, 2, 3, 4, 5}; std::index_sequence<__indices ...> = std::integer_sequence<long unsigned int, 0, 1, 2, 3, 4, 5>]’
remove_duplicate_adjacent.cpp:49:41:   required from here
remove_duplicate_adjacent.cpp:65:47:   in ‘constexpr’ expansion of ‘remove_duplicate_adjacent(const Tuple&) [with Tuple = std::tuple<int, int, int, int, int, int, int>]()’
/opt/rh/devtoolset-10/root/usr/include/c++/10/variant:1042:67:   in ‘constexpr’ expansion of ‘std::__detail::__variant::__gen_vtable_impl<std::__detail::__variant::_Multi_array<std::__detail::__variant::__deduce_visit_result<std::tuple<int, int, int, int, int, int> > (*)(remove_duplicate_adjacent_helper<std::tuple<int, int, int, int, int, int, int>, {0, 1, 2, 3, 4, 5}>::<lambda(const auto:34&)>&&, std::variant<std::tuple<int, int, int, int, int, int>, std::tuple<int, int, int, int, int>, std::tuple<int, int, int, int>, std::tuple<int, int, int>, std::tuple<int, int> >&&), 5>, std::integer_sequence<long unsigned int> >::_S_apply()’
/opt/rh/devtoolset-10/root/usr/include/c++/10/variant:940:19:   in ‘constexpr’ expansion of ‘std::__detail::__variant::__gen_vtable_impl<std::__detail::__variant::_Multi_array<std::__detail::__variant::__deduce_visit_result<std::tuple<int, int, int, int, int, int> > (*)(remove_duplicate_adjacent_helper<std::tuple<int, int, int, int, int, int, int>, {0, 1, 2, 3, 4, 5}>::<lambda(const auto:34&)>&&, std::variant<std::tuple<int, int, int, int, int, int>, std::tuple<int, int, int, int, int>, std::tuple<int, int, int, int>, std::tuple<int, int, int>, std::tuple<int, int> >&&), 5>, std::integer_sequence<long unsigned int> >::_S_apply_all_alts<0, 1, 2, 3, 4>(__vtable, (std::make_index_sequence<5>(), std::make_index_sequence<5>()))’
/opt/rh/devtoolset-10/root/usr/include/c++/10/variant:1031:43: error: invalid conversion from ‘std::__success_type<std::tuple<int, int, int, int, int> >::type (*)(remove_duplicate_adjacent_helper<std::tuple<int, int, int, int, int, int, int>, {0, 1, 2, 3, 4, 5}>::<lambda(const auto:34&)>&&, std::variant<std::tuple<int, int, int, int, int, int>, std::tuple<int, int, int, int, int>, std::tuple<int, int, int, int>, std::tuple<int, int, int>, std::tuple<int, int> >&&)’ {aka ‘std::tuple<int, int, int, int, int> (*)(remove_duplicate_adjacent_helper<std::tuple<int, int, int, int, int, int, int>, {0, 1, 2, 3, 4, 5}>::<lambda(const auto:34&)>&&, std::variant<std::tuple<int, int, int, int, int, int>, std::tuple<int, int, int, int, int>, std::tuple<int, int, int, int>, std::tuple<int, int, int>, std::tuple<int, int> >&&)’} to ‘std::__detail::__variant::_Multi_array<std::__detail::__variant::__deduce_visit_result<std::tuple<int, int, int, int, int, int> > (*)(remove_duplicate_adjacent_helper<std::tuple<int, int, int, int, int, int, int>, {0, 1, 2, 3, 4, 5}>::<lambda(const auto:34&)>&&, std::variant<std::tuple<int, int, int, int, int, int>, std::tuple<int, int, int, int, int>, std::tuple<int, int, int, int>, std::tuple<int, int, int>, std::tuple<int, int> >&&)>::__untag_result<std::__detail::__variant::__deduce_visit_result<std::tuple<int, int, int, int, int, int> > (*)(remove_duplicate_adjacent_helper<std::tuple<int, int, int, int, int, int, int>, {0, 1, 2, 3, 4, 5}>::<lambda(const auto:34&)>&&, std::variant<std::tuple<int, int, int, int, int, int>, std::tuple<int, int, int, int, int>, std::tuple<int, int, int, int>, std::tuple<int, int, int>, std::tuple<int, int> >&&)>::element_type’ {aka ‘std::tuple<int, int, int, int, int, int> (*)(remove_duplicate_adjacent_helper<std::tuple<int, int, int, int, int, int, int>, {0, 1, 2, 3, 4, 5}>::<lambda(const auto:34&)>&&, std::variant<std::tuple<int, int, int, int, int, int>, std::tuple<int, int, int, int, int>, std::tuple<int, int, int, int>, std::tuple<int, int, int>, std::tuple<int, int> >&&)’} [-fpermissive]
 1031 |       { return _Array_type{&__visit_invoke}; }
      |                                           ^
      |                                           |
      |                                           std::__success_type<std::tuple<int, int, int, int, int> >::type (*)(remove_duplicate_adjacent_helper<std::tuple<int, int, int, int, int, int, int>, {0, 1, 2, 3, 4, 5}>::<lambda(const auto:34&)>&&, std::variant<std::tuple<int, int, int, int, int, int>, std::tuple<int, int, int, int, int>, std::tuple<int, int, int, int>, std::tuple<int, int, int>, std::tuple<int, int> >&&) {aka std::tuple<int, int, int, int, int> (*)(remove_duplicate_adjacent_helper<std::tuple<int, int, int, int, int, int, int>, {0, 1, 2, 3, 4, 5}>::<lambda(const auto:34&)>&&, std::variant<std::tuple<int, int, int, int, int, int>, std::tuple<int, int, int, int, int>, std::tuple<int, int, int, int>, std::tuple<int, int, int>, std::tuple<int, int> >&&)}

完整的代码here

Answer 1

由于C++20中几乎所有的算法都是constexpr，我们可以将std::tuple转换为std::array，并直接在其上使用std算法，然后将结果转换回std::tuple。

但是由于您的返回类型是由函数参数决定的，所以我们不能在编译时知道确切的返回类型。相反，我们应该使用std::vairiant来擦除所有可能的返回类型。

#include <tuple>
#include <variant>
#include <algorithm>
#include <array>

template<std::size_t N>
using Int = std::integral_constant<std::size_t, N>;

template<std::size_t N>
constexpr auto gen_tuple(const std::array<int, N>& arr, auto i) {
   return [&arr]<std::size_t... Is>(std::index_sequence<Is...>) {
    return std::tuple(arr[Is]...);
  }(std::make_index_sequence<i>{});
}

template<std::size_t... Is>
auto deduce_return_type(std::index_sequence<Is...>) -> 
std::variant<decltype(gen_tuple(std::array<int, sizeof...(Is)>{}, Int<Is>{}))...>;

template<std::size_t N>
using return_type = decltype(deduce_return_type(std::make_index_sequence<N>{}));

template<std::size_t N>
constexpr return_type<N + 1> gen_variant(const std::array<int, N>& arr, auto i) {
  return gen_tuple(arr, i);
}

template <typename Tuple, std::size_t N = std::tuple_size_v<Tuple>>
constexpr return_type<N + 1> remove_duplicate_adjacent(const Tuple& input) {
  constexpr auto indices = []<std::size_t... Is>(std::index_sequence<Is...>) {
    using var_t = std::variant<Int<Is>...>;
    return std::array<var_t, N + 1>{var_t{Int<Is>{}}...};
  }(std::make_index_sequence<N + 1>{});

  auto v = std::apply([](const auto&... args) {
    return std::array<int, N>{args...};
  }, input);

  auto unique_size = std::unique(v.begin(), v.end()) - v.begin();
  return std::visit([&v](auto i) { return gen_variant(v, i); }, indices[unique_size]);
}

Demo.