按照一对元素的差值对向量对进行排序

Question

有没有一种方法在C++中，能够根据一对值的差异来排序向量对。例如，假设我有4个向量对：

1 3, 
5 6, 
2 3,
12 5,

所以，这些数对的差分别为2、1、1、7，如果我按降序排列，则排序后的向量将是：

12 5,
1 3,
5 6,
2 3,

我希望您能理解我的问题。有没有办法按照这种方式对元素进行排序？

我已经尝试过根据第一个或第二个元素对元素进行排序。但这不是我的问题。我的问题是需要基于差异进行排序。

bool sortinrev(const pair<int,int> &a, const pair<int,int> &b){
    return(a.first > b.first) ;
}


int main()
{
    vector< pair <int,int> > pq;
    for(int i=1; i<=4; i++){
        int x,y;
        cin >> x >> y;

        pq.push_back(make_pair(x,y));
    }

    sort(pq.begin(), pq.end(), sortinrev);

    for(int i=0; i<4; i++){
        cout << pq[i].first << " " << pq[i].second << endl;
    }


    return 0;
}

- Yeasin Rahaman

---

C++中的sort函数可以接受一个函数指针作为参数。只需传递一个按照你想要的方式比较这些对的函数即可。 - scohe001

我只知道如何根据第一个元素或第二个元素进行排序。由于我不知道如何根据差异进行排序，所以我发帖询问方法。然后我会尝试解决我的实际问题。 - Yeasin Rahaman

你可以将一个 compare 变量传递给 sort() 方法。请参考 @scohe001 在评论中提供的链接。 - Error - Syntactical Remorse

实际上，由于这是计算问题，因此有许多方法可以解决，而C++足够强大，几乎可以实现任何东西（尽管有时需要时间）。在这种特定情况下，C++提供了内置支持，可以使用相当短小优雅的解决方案std::sort（并使用比较器变量，如CoryKramer的答案所示）。但是，除非您遇到一些非计算问题或某些非常低级别的操作系统/固件问题，否则通常会自动回答“是否有C++的方法”为“是”。 - Ped7g

@Ped7g 是的，这是一个计算问题。我需要最佳解决方案。 - Yeasin Rahaman

@YeasinRahaman “最好”是指什么？短源代码？短二进制文件？最佳性能？等等...在这种情况下，你不能拥有所有的东西，以下答案是合理的妥协（简单的源代码，以预期的方式重用C++ stdlib，合理的性能）。 - Ped7g

Answer 1

如果您的容器是：

std::vector<std::pair<int, int>> data;

您可以将其分类为：

std::sort(std::begin(data),
          std::end(data),
          [](std::pair<int, int> const& lhs, std::pair<int, int> const& rhs)
          {
              return std::abs(lhs.first - lhs.second) < std::abs(rhs.first - rhs.second);
          });

如果您想在升序和降序之间切换，只需相应地从< 切换到 >。

- Cory Kramer

---

你的代码非常适合这种情况，但如果OP不知道如何查找并找到这种排序函数，我怀疑他是否能理解lambda表达式。也许可以添加一些解释？或者将比较器变成它自己的函数？ - scohe001

Answer 2

标准库提供了数据结构std::pair和排序算法std::sort，您可以将自定义的比较函数传递给它们来定义排序顺序。以下代码定义了一个比较器，接受两个std::pair<int,int>并基于它们的“绝对差”进行比较，以及如何使用它调用std::sort。希望这能帮到您。

#include <iostream>
#include <vector>

int main()
{
    std::vector<std::pair<int,int> > v = {
        {1, 3},
        {5, 6},
        {2, 3},
        {12, 5}
    };

    // sort using a custom function object
    struct {
        bool operator()(const std::pair<int,int> &a, const std::pair<int,int> &b) const
        {
            return ( abs(a.first-a.second) > abs(b.first-b.second));
        }
    } differenceIsGreater;
    std::sort(v.begin(), v.end(), differenceIsGreater);
    for (auto a : v) {
        std::cout << "(" << a.first << "," << a.second << ")" << std::endl;
    }

    return 0;
}

输出：

(12,5)
(1,3)
(5,6)
(2,3)

- Stephan Lechner

Answer 3

std::sort有一个重载函数，可以使用可调用的比较器。

template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );

所以，你可以将lambda（或其他函数）作为第三个参数传递，以任何你想要的方式进行比较。

来自cppreference.com：

comp     -   comparison function object (i.e. an object that satisfies the     requirements of Compare) which returns ​true if the first argument is less than (i.e. is ordered before) the second. 
The signature of the comparison function should be equivalent to the following:

bool cmp(const Type1 &a, const Type2 &b);

The signature does not need to have const &, but the function object must not modify the objects passed to it.
The types Type1 and Type2 must be such that an object of type RandomIt can be dereferenced and then implicitly converted to both of them. ​

所以，例如。

sort(begin(myvect), end(myvect), [](auto p) { /* comparison code */ });

（需要C++14，根据您的编译器版本可能需要进行修改）

- Rex Kerr