logo标签列表

std::sort() 的自定义元组比较器

c++templatesstdtuple
3

我有以下情况：我必须将多个指针和一个标识符打包到如下的元组中：

typedef tuple<unsigned*, unsigned*, unsigned*, unsigned> tuple_with_pointers_t;

这里我有三个指针和一个标识符。在其他情况下，我可能会有更多或更少的指针，但最后一个指针将是标识符。请注意，我仅使用 unsigned* 作为示例。实际上，它可能是更复杂的对象。

现在，我想比较两个这样的元组的值。也就是说，我需要解除引用除了最后一个以外的所有元素。我们可以使用以下方法（在 C++17 中）实现：

template <size_t I = 0, typename T, typename... Ts>
constexpr bool lesser(std::tuple<T, Ts...> a, std::tuple<T, Ts...> b)
{
    if constexpr (I < sizeof...(Ts))
        return (*std::get<I>(a) < *std::get<I>(b)) ||
               ((*std::get<I>(a) == *std::get<I>(b)) && lesser<I + 1>(a, b));
    else
        return std::get<I>(a) < std::get<I>(b);
}

这种构造方法在比较两个元组时非常有效。现在，我想将lesser()作为一个函数对象用于std::sort()中。但是，g++和clang++都报错“couldn't infer template argument '_Compare'”。换句话说，我们需要向lesser传递正确的模板参数。
我尝试了一些方法，但没有成功：我们有三个模板参数，我不确定如何在此处使用元组中的_Elements。什么策略最好呢？
以下是一些示例代码：
#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>

using namespace std;

// My weird tuple with pointers and one unsigned index.
typedef tuple<unsigned*, unsigned*, unsigned*, unsigned> tuple_with_pointers_t;

// This works fine for two tuples directly. Note that we cannot dereference
// the last tuple element, so we compare it directly.
template <size_t I = 0, typename T, typename... Ts>
constexpr bool lesser(std::tuple<T, Ts...> a, std::tuple<T, Ts...> b)
{
    if constexpr (I < sizeof...(Ts))
        return (*std::get<I>(a) < *std::get<I>(b)) ||
               ((*std::get<I>(a) == *std::get<I>(b)) && lesser<I + 1>(a, b));
    else
        return std::get<I>(a) < std::get<I>(b);
}

int main() {
    // Three sets of values.
    vector<unsigned> values1 {1, 2, 3};
    vector<unsigned> values2 {10, 20, 30};
    vector<unsigned> values3 {11, 22, 33};

    // Here, we pack it all together with the index.
    vector<tuple_with_pointers_t> all;

    for(unsigned i = 0; i < values1.size(); ++i)
        all.emplace_back(&values1[i], &values2[i], &values3[i], i);


    // So, it works if we want to compare two elements of our vector.
    cout << "\n- t0 < t1: " << std::boolalpha << lesser(all[0], all[1]);
    cout << "\n- t2 < t1: " << std::boolalpha << lesser(all[2], all[1]);


    // Now, I want to sort the tuples by their values. The compiler doesn't
    // like it: it cannot deduce the template parameters.
    sort(all.begin(), all.end(), lesser);

    return 0;
}

我很感激任何C++17或C++20方面的帮助，但我正在寻找最简洁优雅的方法来解决这个问题。如果可能的话，可以直接在sort()调用中使用lambda函数。

谢谢!

更新:

好的，我找到了一个小技巧，它能够实现：

sort(all.begin(), all.end(),
     [](const auto &a, const auto &b) {
        return lesser(a, b);
     }
);

基本上，我们将其包装成 lambda 表达式，因此编译器可以推断类型。但是，我们能做得更好吗？

谢谢

在调用点，您需要指定要使用哪个lesser的实例化，而不仅仅是将模板名称插入其中。例如，sort(all.begin(), all.end(), lesser<0, unsigned*, unsigned*, unsigned*, unsigned>())。您可以通过使用typedef（或等效的using）来简化此过程。 - Peter
谢谢@Peter，但这不够通用。想象一下我有不同的元组类型，就像这样，有数十个指针（我有一个有12个指针！）。因此，编写一些可以使编译器自动推断参数的代码将是很好的选择。 - an_drade
将“unsigned”（标识符）放在元组的第一个元素中会更容易些。 - 康桓瑋
我认为这并不重要，因为我无论如何都需要解引用其他元素。但是，这样会更清晰明了。在这段代码的第一个版本中，我有一个包含几个元素的元组，所以我可以使用标准的operator<运算符。但是，事情发展成另一条路线，所以我必须使用指针。 - an_drade
2
将您的比较器打包到一个带有模板化的operator()的函数对象中。 - n. m.
如果仅用于排序，常规的 operator< 就可以胜任（您还可以比较等效元素的 id）。 （对于 std::map，这确实会有问题，因为在地图中您也会有“重复”的元素）。 - Jarod42
3个回答
1

我认为我们可以使用这个。当然，我不知道你的元组可能会更加复杂。

template<typename T, size_t I = 0>
using type_tuple = typename std::tuple_element<I,T>::type;

template<size_t I = 0, template<typename> class F = std::less_equal>
struct TupleCompare
{
    template<typename T>
    bool operator()(T const &t1, T const &t2){
        using _type = typename std::conditional<std::is_pointer<type_tuple<T>>::value, 
            typename std::remove_pointer<type_tuple<T,I>>::type, type_tuple<T>>::type;

        if constexpr (I == std::tuple_size_v<T> - 1) {            
            return F<_type>()(std::get<I>(t1), std::get<I>(t2));
        } else {            
            return F<_type>()(*std::get<I>(t1), *std::get<I>(t2)) && TupleCompare<I+1, F>()(t1, t2);
        }
        
    }
};
std::tuple_element_t 可以替换你的 type_tuple。 - Jarod42
谢谢@GAVD。我认为这个解决方案非常好，假设我可以使用不同（和标准的）比较函数来实例化TupleCompare。 - an_drade
1

通过编写非递归函数，你可以编写一个“一行代码”：

sort(all.begin(), all.end(),
     []<typename T>(const T& lhs, const T& rhs) {
         return [&]<std::size_t... Is>(std::index_sequence<Is...>){
             return std::tie(std::get<Is>(lhs)...)
                  < std::tie(std::get<Is>(rhs)...);
         }(std::make_index_sequence<std::tuple_size_v<T> - 1>{});
     });

模板lambda是C++20中的新特性。
如果没有这个特性，至少需要一个辅助函数，因此它就像其他解决方案一样，将函数封装在一个仿函数中。

感谢@Jarod42。我已经看到使用c++20的类似结构。好处是它只有一行，尽管代码更加密集。我还在考虑是否要使用它。 - an_drade
1

正如评论中所建议的，您可以将比较器添加到函数对象中，并将对象的实例传递给sort：

#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>

using namespace std;

// My weird tuple with pointers and one unsigned index.
typedef tuple<unsigned*, unsigned*, unsigned*, unsigned> tuple_with_pointers_t;

namespace details {

template <size_t I = 0, typename T, typename... Ts>
constexpr bool lesser(std::tuple<T, Ts...> const& a, std::tuple<T, Ts...> const& b)
{
    if constexpr (I < sizeof...(Ts))
        return (*std::get<I>(a) < *std::get<I>(b)) ||
               ((*std::get<I>(a) == *std::get<I>(b)) && lesser<I + 1>(a, b));
    else
        return std::get<I>(a) < std::get<I>(b);
}
}

struct Less
{
    template <typename... Ts>
    constexpr bool operator()(std::tuple<Ts...> const& a, std::tuple<Ts...> const& b)
    {
        return details::lesser<0, Ts...>(a, b);
    }
};

int main() {
    // Three sets of values.
    vector<unsigned> values1 {1, 2, 3};
    vector<unsigned> values2 {10, 20, 30};
    vector<unsigned> values3 {11, 22, 33};

    // Here, we pack it all together with the index.
    vector<tuple_with_pointers_t> all;

    for(unsigned i = 0; i < values1.size(); ++i)
        all.emplace_back(&values1[i], &values2[i], &values3[i], i);


    // So, it works if we want to compare two elements of our vector.
    cout << "\n- t0 < t1: " << std::boolalpha << Less()(all[0], all[1]);
    cout << "\n- t2 < t1: " << std::boolalpha << Less()(all[2], all[1]);


    // Now, I want to sort the tuples by their values. The compiler doesn't
    // like it: it cannot deduce the template parameters.
    sort(all.begin(), all.end(), Less());

    return 0;
}

作为一种替代方案，您可以将 unsigned* 包装在自定义指针类型中，并为其提供比较器。然后，您可以使用元组的默认比较器进行比较，该比较器按字典顺序比较元素。
个人而言，我更喜欢这种方法，因为代码更易读。我不知道这是否会破坏您现有的代码或需要进行大规模重构。
#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>

using namespace std;

class Ptr
{
public:
    Ptr(unsigned& v) : m_ptr(&v) {}
    unsigned operator*() const {
        return *m_ptr;
    }
private:
    unsigned* m_ptr;
};

bool operator<(Ptr const& l, Ptr const& r)
{
    return *l < *r;
}

// My weird tuple with pointers and one unsigned index.
typedef tuple<Ptr, Ptr, Ptr, unsigned> tuple_with_pointers_t;

int main() {
    // Three sets of values.
    vector<unsigned> values1 {1, 2, 3};
    vector<unsigned> values2 {10, 20, 30};
    vector<unsigned> values3 {11, 22, 33};

    // Here, we pack it all together with the index.
    vector<tuple_with_pointers_t> all;

    for(unsigned i = 0; i < values1.size(); ++i)
        all.emplace_back(values1[i], values2[i], values3[i], i);


    // So, it works if we want to compare two elements of our vector.
    cout << "\n- t0 < t1: " << std::boolalpha << (all[0] < all[1]);
    cout << "\n- t2 < t1: " << std::boolalpha << (all[2] < all[1]);

    sort(all.begin(), all.end());

    return 0;
}
如果您使用的是C++20，那么这将是使用太空船运算符的好方法。指针类型Ptr的排序由指针的值类型的排序定义。https://godbolt.org/z/9eenqsG7b - joergbrech
感谢@joergbrech。我认为struct Less给了我们一些灵活性，但在代码中添加了另一个辅助结构。在某种意义上，它类似于“接口和实现函数”习语，通常在操作元组时使用。指针包装器确实是更清晰的版本，特别是当使用复杂对象时。使用标准运算符通常比构建自己的运算符更好。然而，当仅使用简单基本类型时，我想知道它所需的计算开销。 - an_drade
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接