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

Question

I would like a function bool dominates(const std::tuple<T...>& t1, const std::tuple<T...>& t2) which returns true iff tuple t1 dominates tuple t2, i.e. for all i, t1[i] <= t2[i], in contrast with the default <= operator which uses a lexicographic comparison.

I've tried to adapt the answer from this question, but without success. It fails at compilation.

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

Compilation errors:

./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

score 2 · Accepted Answer · answered May 16 '21 at 17:30

The problem in you code is in dominates_impl()

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

you can't have two variadic argument list of argument in a function; you can have only one in last position.

But you don't need dominates_impl() at all: you can emulate C++17 template folding writing dominates() (the three argument version) as follows

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

Remember to recover integer_sequence and gen_indices() from the original question.

Sam Varshavchik · Answer 2 · 2021-05-16T17:22:15.340

I was able to make it work in C++11, but only by manually reinventing C++14's std::integer_sequence, and losing 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;
}

A good chunk of the above is a half-baked std::integer_sequence. With that, and C++17's fold expressions this becomes a no-brainer:

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

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

2 Answers2