检查一个元组是否支配 C++11 中的另一个元组

Question

我想要一个函数 bool dominates(const std::tuple<T...>& t1, const std::tuple<T...>& t2)，其中 returns true 当且仅当元组 t1 支配元组 t2，即对于所有 i， t1[i] <= t2[i]，与使用字典序比较的默认 <= 运算符相反。

我尝试改编 this question 的答案，但没有成功。编译失败。

template<typename H>
bool& dominates_impl(bool& b, H&& h1, H&& h2)
{
    b &= std::forward<H>(h1) <= std::forward<H>(h2);
    return b;
}

template<typename H, typename... T>
bool& dominates_impl(bool& b, H&& h1, H&& h2, T&&... t1, T&&... t2)
{
    b &= (std::forward<H>(h1) <= std::forward<H>(h2));
    return dominates_impl(b, std::forward<T>(t1)..., std::forward<T>(t2)...);
}

template<typename... T, std::size_t... I>
bool dominates(
        const std::tuple<T...>& t1,
        const std::tuple<T...>& t2,
        integer_sequence<std::size_t, I...>)
{
    bool b = true;
    int ctx[] = { (dominates_impl(b, std::get<I>(t1)..., std::get<I>(t2)...), 0), 0};
    (void)ctx;
    return b;
}

template <typename ... T>
bool dominates(
        const std::tuple<T...>& t1,
        const std::tuple<T...>& t2)
{
    return dominates(t1, t2, gen_indices<sizeof...(T)>{});
}

编译错误：

./common.hpp: In instantiation of 'bool dominates(const std::tuple<_Tps ...>&, const std::tuple<_Tps ...>&, integer_sequence<long unsigned int, I ...>) [with T = {long int, long int, long int, long int, long int}; long unsigned int ...I = {0, 1, 2, 3, 4}]':
./common.hpp:107:21:   required from 'bool dominates(const std::tuple<_Tps ...>&, const std::tuple<_Tps ...>&) [with T = {long int, long int, long int, long int, long int}]'
examples.cpp:1624:65:   required from here
./common.hpp:97:34: error: no matching function for call to 'dominates_impl(bool&, std::__tuple_element_t<0, std::tuple<long int, long int, long int, long int, long int> >&, std::__tuple_element_t<1, std::tuple<long int, long int, long int, long int, long int> >&, std::__tuple_element_t<2, std::tuple<long int, long int, long int, long int, long int> >&, std::__tuple_element_t<3, std::tuple<long int, long int, long int, long int, long int> >&, std::__tuple_element_t<4, std::tuple<long int, long int, long int, long int, long int> >&, std::__tuple_element_t<0, std::tuple<long int, long int, long int, long int, long int> >&, std::__tuple_element_t<1, std::tuple<long int, long int, long int, long int, long int> >&, std::__tuple_element_t<2, std::tuple<long int, long int, long int, long int, long int> >&, std::__tuple_element_t<3, std::tuple<long int, long int, long int, long int, long int> >&, std::__tuple_element_t<4, std::tuple<long int, long int, long int, long int, long int> >&)'
   97 |     int ctx[] = { (dominates_impl(b, std::get<I>(t1)..., std::get<I>(t2)...), 0), 0};
      |                    ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
./common.hpp:77:7: note: candidate: 'template<class H> bool& dominates_impl(bool&, H&&, H&&)'
   77 | bool& dominates_impl(bool& b, H&& h1, H&& h2)
      |       ^~~~~~~~~~~~~~
./common.hpp:77:7: note:   template argument deduction/substitution failed:
./common.hpp:97:34: note:   candidate expects 3 arguments, 11 provided
   97 |     int ctx[] = { (dominates_impl(b, std::get<I>(t1)..., std::get<I>(t2)...), 0), 0};
      |                    ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
./common.hpp:84:7: note: candidate: 'bool& dominates_impl(bool&, H&&, H&&, T&& ..., T&& ...) [with H = const long int&; T = {const long int&, const long int&, const long int&, const long int&, const long int&, const long int&, const long int&, const long int&}]'
   84 | bool& dominates_impl(bool& b, H&& h1, H&& h2, T&&... t1, T&&... t2)
      |       ^~~~~~~~~~~~~~
./common.hpp:84:7: note:   candidate expects 19 arguments, 11 provided

Answer 1

我能够让它在 C++11 中工作，但只能通过手动重新发明 C++14 的 std::integer_sequence，并失去 constexpr-ability:

#include <tuple>
#include <type_traits>
#include <assert.h>

template<typename T, T ...i> struct integer_sequence {};

template<typename T, T v=0>
struct counter {

    static constexpr T n=v;
    typedef counter<T, v-1> prev;
};

template<typename T, typename V, T ...i> struct integer_sequence_impl;

template<typename T, T ...i>
struct integer_sequence_impl<T, counter<T>, i...> {

    typedef struct integer_sequence<T, 0, i...> t;
};

template<typename T, typename V, T ...i> struct integer_sequence_impl
    : integer_sequence_impl<T, typename V::prev, V::n, i...> {};

template<typename T, T n>
using create_integer_sequence=
    typename integer_sequence_impl<T, counter<T, n-1>>::t;

template<class T, T N>
using make_integer_sequence=create_integer_sequence<T, N>;

template<typename T1,
     typename T2,
     std::size_t ...i>
bool dominates_impl(const T1 &t1,
            const T2 &t2,
            const integer_sequence<std::size_t, i...> &)
{
    bool compare[]={
        (std::get<i>(t1) <= std::get<i>(t2))...
    };

    for (auto f:compare)
        if (!f)
            return false;
    return true;

}

template<typename ...T1,
     typename ...T2,
     typename=typename std::enable_if<sizeof...(T1) == sizeof...(T2)>::type>
bool dominates(const std::tuple<T1...> &t1,
             const std::tuple<T2...> &t2)
{
    return dominates_impl(t1, t2,
                  make_integer_sequence<std::size_t, sizeof...(T1)>
                  {});
}

int main()
{
    assert(!dominates(std::tuple<int, int>{4, 2},
              std::tuple<int, int>{3, 1}));

    assert(dominates(std::tuple<int, int>{2, 2},
             std::tuple<int, int>{3, 2}));

    return 0;
}

上面的一大块是半生不熟的 std::integer_sequence。有了它，再加上 C++17 的折叠表达式，这就变得很简单了：

#include <tuple>
#include <type_traits>

template<typename T1,
     typename T2,
     std::size_t ...i>
constexpr bool dominates_impl(const T1 &t1,
                  const T2 &t2,
                  const std::integer_sequence<std::size_t, i...> &)
{
    return ( (std::get<i>(t1) <= std::get<i>(t2)) && ...);
}

template<typename ...T1,
     typename ...T2,
     typename=std::enable_if_t<sizeof...(T1) == sizeof...(T2)>>
constexpr bool dominates(const std::tuple<T1...> &t1,
             const std::tuple<T2...> &t2)
{
    return dominates_impl(t1, t2,
                  std::make_index_sequence<sizeof...(T1)>{});
}

static_assert(!dominates(std::tuple{4, 2},
             std::tuple{3, 1}));

static_assert(dominates(std::tuple{2, 2},
            std::tuple{3, 2}));

Answer 2

你代码中的问题在dominates_impl()

template<typename H, typename... T>
bool& dominates_impl(bool& b, H&& h1, H&& h2, T&&... t1, T&&... t2)

你不能在一个函数中有两个参数的可变参数列表；你只能在最后一个位置。

但你根本不需要dominates_impl()：你可以模拟 C++17 模板折叠写作 dominates()（三参数版本）如下

template<typename... T, std::size_t... I>
bool dominates(
        const std::tuple<T...>& t1,
        const std::tuple<T...>& t2,
        integer_sequence<std::size_t, I...>)
{
   using unused = bool[];

   bool b { true };

   (void)unused { b, (b = b && std::get<I>(t1) <= std::get<I>(t2))... };

   return b;
}

记得从原始问题中恢复 integer_sequence 和 gen_indices()。

检查一个元组是否支配 C++11 中的另一个元组

Check if a tuple dominates another tuple in C++11

c++

tuples

template-meta-programming

variadic-templates

c++11