在 C++11 中实现 std::tuple 的词典比较

Question

我正在尝试为 std::tuple 执行词典比较。我知道标准提供了这个。我正在做 TMP 练习。我不明白为什么下面的代码不起作用。谁能指出我正确的方向？

我知道下面的代码采用相同类型的操作数。我很高兴将其作为一个简化假设。

我查看了 VC++ 2013 和 GCC 4.7 实现。他们都使用非标准助手类从元组中获取尾部（即除了最左边的元素之外的所有元素）。我想用尽可能少的脚手架解决问题。是否可以在没有 get_tail?

的情况下进行元组比较

#include <iostream>
#include <string>
#include <tuple>

// Pseudo-recursion.

template<class tupleT,std::size_t N>
struct tuple_ops {
    static bool less(const tupleT& x,const tupleT& y) {
        return std::get<N-1>(x) < std::get<N-1>(y) ||
            ( !(std::get<N-1>(y) < std::get<N-1>(x)) &&
              tuple_ops<tupleT,N-1>::less(x,y) );
    }
};

// Base Case.

template<class tupleT>
struct tuple_ops<tupleT,1> {
    static bool less(const tupleT& x,const tupleT& y) {
        return std::get<0>(x) < std::get<0>(y);
    }
};

// Convenience wrapper.

template<class... T>
bool operator<(const std::tuple<T...>& x,const std::tuple<T...>& y) {
    return tuple_ops<decltype(x),sizeof...(T)>::less(x,y);
}

int main() {
    using namespace std;

    auto tup0 = make_tuple(3.14,string("foo"),2.71);
    auto tup1 = make_tuple(4.01,string("foo"),2.01);
    auto tup2 = make_tuple(1,string("bar"),5);
    auto tup3 = make_tuple(1,string("foo"),5);

    cout <<  (::operator<(tup0,tup1))  << ' '
         <<  (::operator<(tup2,tup3))  << ' '
         << !(::operator<(tup1,tup0)) << ' '
         << !(::operator<(tup3,tup2)) << ' ';

    return 0;
}

输出：0 1 0 1

正确的输出是：1 1 1 1

提前致谢。

Answer 1

您的代码不起作用的原因是您的比较是倒退的。您的第一个电话是：

return tuple_ops<decltype(x),sizeof...(T)>::less(x,y);

将调用 tuple_ops<Type, 3>::less()，其第一个操作比较 std::get<2>(x) 和 std::get<2>(y)。所以你首先比较 last 元素。

您必须从 0 开始，一直到 N，因此您必须将第一级调用重写为：

return tuple_ops<decltype(x),0,sizeof...(T)>::less(x,y);

终止案例现在是：

template <typename Tuple, size_t N>
struct tuple_ops<Tuple, N, N> {
    static bool less(const Tuple&, const Tuple&) { return false; }
};

避免特化的更简单方法是使用索引序列（并借用 Yakk 的 now-deleted answer 以添加更多功能）：

template <class X, class Y>
bool operator<(const X& x, const Y& y) {
    return is_less(x, y,
        std::make_index_sequence<std::min(std::tuple_size<X>{},
                                          std::tuple_size<Y>{})>{});
}

为空箱重载：

template <typename X, typename Y>
bool is_less(X const&, Y const&, std::index_sequence<> ) {
    return std::tuple_size<X>{} < std::tuple_size<Y>{};
}

和递归情况的重载：

template <typename X, typenmae Y, size_t I, size_t... Is>
bool is_less(X const& x, Y const& y, std::index_sequence<I, Is...> ) {
    if (std::get<I>(x) < std::get<I>(y)) {
        return true;
    }
    else if (std::get<I>(y) < std::get<I>(x)) {
        return false;
    }
    else {
        return is_less(x, y, std::index_sequence<Is...>{});
    }
}

Answer 2

像魅力一样工作。这是测试程序的一个版本，结合了 Barry 的技巧。

#include <iostream>
#include <string>
#include <tuple>

// Pseudo-recursion.

template<class tupleT,std::size_t J,std::size_t N>
struct tuple_ops {
    static bool less(const tupleT& x,const tupleT& y) {
        return std::get<J>(x) < std::get<J>(y) ||
            ( !(std::get<J>(y) < std::get<J>(x)) &&
                tuple_ops<tupleT,J+1,N>::less(x,y) );
    }
};

// Base Case.

template <typename Tuple, size_t N>
struct tuple_ops<Tuple,N,N> {
    static bool less(const Tuple&, const Tuple&) {return false;}
};

// Convenience wrapper.

template<class... T>
bool operator<(const std::tuple<T...>& x,const std::tuple<T...>& y) {
    return tuple_ops<decltype(x),0,sizeof...(T)>::less(x,y);
}

int main() {
    using namespace std;

    auto tup0 = make_tuple(3.14,string("foo"),2.71);
    auto tup1 = make_tuple(4.01,string("foo"),2.01);
    auto tup2 = make_tuple(1,string("bar"),5);
    auto tup3 = make_tuple(1,string("foo"),5);

    cout <<  (::operator<(tup0,tup1)) << ' '
         <<  (::operator<(tup2,tup3)) << ' '
         << !(::operator<(tup1,tup0)) << ' '
         << !(::operator<(tup3,tup2)) << ' ';

    return 0;
}

再次感谢。

在 C++11 中实现 std::tuple 的词典比较

Implementing lexicographic comparison for std::tuple in C++11

c++

templates

variadic-templates

c++11