C++：用于排序元素的结构与函数

Question

我有一个包含两个字段的 struct :

struct road {
    int from, len ;
};

出于某种原因，我需要能够订购我的 roads :

通过在数组中升序 from
通过在优先级队列中升序 len

我因此包括了:

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

我遇到过建议重载 operator< 的网站，但由于两种可能的排序感觉不对，它只能解决两者之一。

通过摆弄教科书，我得到了这个工作:

bool cmpFrom (const road & a, const road & b) {
    return (a.from < b.from) ;
}

struct cmpLen {
    bool operator () (const road & a, const road & b){
        return (a.len < b.len) ;
    }
};

用于：

std::sort(trips, trips + nbRoads, &cmpFrom) ;
std::priority_queue<road, std::vector<road>, cmpLen> pickRoad ;

其中trips当然是一个road [].

它编译完美（没试过运行，但应该没问题），但是用两种完全不同的方式定义两个非常相似的比较器似乎很奇怪，所以没有办法以相同的方式定义两种比较方法？

正在将 cmpFrom 的定义更改为

struct cmpFrom {
    bool operator () (const road & a, const road & b){
        return (a.from < b.from) ;
    }
};

给予

chantier.cpp: In function ‘int main()’:
chantier.cpp:38:48: error: expected primary-expression before ‘)’ token
     std::sort(trips, trips + nbRoads, &cmpFrom) ;

我认为这意味着 "You gave me a type when I was expecting a reference"。

正在写作

bool cmpLen (const road & a, const road & b) {
    return (a.len <= b.len) ;
}

给予

chantier.cpp: In function ‘int main()’:
chantier.cpp:52:56: error: type/value mismatch at argument 3 in template parameter list for ‘template<class _Tp, class _Sequence, class _Compare> class std::priority_queue’
     std::priority_queue<road, std::vector<road>, cmpLen> pickRoad ;
                                                        ^
chantier.cpp:52:56: note:   expected a type, got ‘cmpLen’
chantier.cpp:56:30: error: request for member ‘top’ in ‘pickRoad’, which is of non-class type ‘int’
...

有没有办法让这些比较方法中的一种对两个容器都适用？或者是否有第三种方法可以同时使用这两种方法？

如果我需要对两个容器使用相同的顺序怎么办？这是否需要定义两次相同的比较方法，但其中一个在 struct 中？

Answer 1

std::sort函数和std::priority_queueclass模板需要两个不同的东西：sort需要一个可调用对象，而priority_queue 模板需要一个允许创建对象的类型。

因此，sort 比 priority_queue 更杂食 - 您可以将它与函数或仿函数一起使用。您唯一需要做的就是为它提供一个真实的对象（而目前在您的代码中您正试图获取一个类型的地址，这是没有意义的）。

要在您的示例中修复它，只需将代码更改为

std::sort(trips, trips + nbRoads, cmpFrom{});

Answer 2

将两者都定义为结构更容易，因为您始终可以从类型创建对象并且它会按预期运行，但是从函数获取类型并将其充当函数的调用者要复杂得多难。

事实上，您和 struct cmpFrom 差不多了。但是，您已经正确地注意到 std::sort 需要比较器 object （例如函数），而不是类型。当然，在 cmpFrom 是类型的地方执行 &cmpFrom 是无效的 C++。相反，您需要创建该类型的对象；由于 operator() 定义，该对象将可调用并执行您想要的操作。所以只需像这样调用 std::sort：

std::sort(trips, trips + nbRoads, cmpFrom{});

Answer 3

你快搞定了。在 std::sort 中，您需要一个可以调用 operator() 的对象。使用

bool cmpFrom (const road & a, const road & b) {
    return (a.from < b.from) ;
}
std::sort(trips, trips + nbRoads, &cmpFrom);

之所以可行，是因为函数指针可以像函数一样使用。当您将 cmpFrom 更改为

struct cmpFrom {
    bool operator () (const road & a, const road & b){
        return (a.from < b.from) ;
    }
};

您不能再使用 std::sort(trips, trips + nbRoads, &cmpFrom);，因为您不能将 & 应用于类型名称。相反，您需要做的是获取 cmpFrom 的对象，然后像

std::sort(trips, trips + nbRoads, cmpFrom{});

现在 priority_queue 和 sort 都可以使用 cmpFrom。

C++：用于排序元素的结构与函数

C++ : struct vs function for ordering elements

c++

sorting

struct

priority-queue