对一组成对的向量进行排序

Question

我有一个关于对一个pair类型的vector进行排序的问题：

std::vector<std::pair<double,Processor*>> baryProc;

这个向量已经被填充满了键值对。

现在我想要根据键值对中的double值对向量中的键值对进行排序。

例如：假设向量中有3个键值对，pair1在最前面，pair3在最后面，pair2在中间：

pair1(1, proc1) 
pair2(3, proc2)
pair3(2.5, proc3)

现在我想根据双精度值对这些配对进行排序，以便向量内部的顺序如下：

pair1(1, proc1) 
pair3(2.5, proc3)
pair2(3, proc2)

我该怎么做呢？我很困惑。

- user2633791

Answer 1

#include <algorithm>

int main(){

    std::vector<std::pair<double,Processor*>> baryProc;

    std::sort(baryProc.begin(),baryProc.end());
}

请注意，您不需要自定义比较器，因为pair的默认比较器可以实现您想要的功能。 它首先通过第一个元素进行比较，如果它们相同，则比较对中的第二个元素。

- Hossein Nasr

---

如果可以保证 double 值唯一（实际上是“集合”），那么这个方法 将 起作用。但如果没有这样的保证（必要时强制执行），则需要编写比较器。对于 pair，默认比较器通常执行 return (a.first < b.first || (a.first == b.first && a.second < b.second); 后者是指针比较，将在 first 的非唯一值处导致问题。 - WhozCraig

我们没有条件告诉我们当第一个元素相同时该怎么做。那么如果我们使用默认比较器会发生什么？ - Hossein Nasr

只要你明白，对于相同的“double”值，小于状态现在基于比较两个指针，这绝对不是你想要发生的事情（实际上很少发生）。 - WhozCraig

那么，我的理解是，这可能会导致排序不一致？或者你只是担心两个指针之间的简单比较会导致最多5个CPU时钟周期？ - Hossein Nasr

为什么标准比较器在这里取双值对的双倍？ - user2633791

Answer 2

在C++中，您可以编写自定义比较函数来指定排序时如何决定一个元素是否排在另一个元素之前。在您的情况下，给定2个pair，您希望具有较低第一个元素值的pair排在另一个pair之前。您可以编写以下比较函数：

// This function returns true if the first pair is "less"
// than the second one according to some metric
// In this case, we say the first pair is "less" if the first element of the first pair
// is less than the first element of the second pair
bool pairCompare(const std::pair<double, Processor*>& firstElem, const std::pair<double, Processor*>& secondElem) {
  return firstElem.first < secondElem.first;

}

现在，将这个函数传递给你的排序方法：

//The sort function will use your custom comparator function 
std::sort(baryProc.begin(), baryProc.end(), pairCompare);

- maditya

---

这是一个很好的例子，可以消除对std::pair的.second比较。我更喜欢使用函数对象来实现（更容易内联化），但是函数式解决方案同样可行。 - WhozCraig

谢谢您的好解释。我想标准比较器会很好地工作。如果双精度值经常相同，那么标准运算符排序是否正确？例如：(1,proc1)，(1,proc2)，(2,proc3)，(3,proc4)，(3,proc5)...... - user2633791

@user2633791，您所询问的是排序是否稳定。如果两个具有相同值的元素在排序结束时与排序开始时相对顺序保持不变，则排序算法是稳定的。默认的排序算法不稳定，但STL提供了一个稳定排序，适合您的需求。 - maditya

谢谢。现在使用标准比较器可以正常工作了。如果您使用我的比较器，我的编译器会报错： 此函数调用缺少参数列表。这些指针会让我崩溃 :) - user2633791

@maditya 你有什么想法，为什么我的编译器会这样说？函数调用缺少参数。使用“&pairCompare”而不是“pairCompare”来获取此成员的指针。但这样做并没有帮助。 - user2633791