如何对vector或deque KeyPair进行排序

Question

我有一个deque <pair<int, int> > r;。我需要通过第二个参数对所有参数进行排序，并返回所有参数的deque<int>。例如：

deque<pair<int, int> > r;
r.push_back(make_pair(1, 5));
r.push_back(make_pair(0, 8));
r.push_back(make_pair(7, 3));
r.push_back(make_pair(2, 1));

我需要这个结果

{2, 7, 1, 0}

我有一种工作方法，“蛮力”所有值都是N2，但它非常糟糕。也许这个std::存在什么？我希望你帮助我。

Answer 1

您只需要定义一个比较运算符来处理对中的第二项：

std::sort(r.begin(), r.end(), 
    [](std::pair<int, int> const &a, std::pair<int, int> const &b) {
         return a.second < b.second;
    }
);

...或者，如果你不能使用lambda（例如，使用太旧的编译器），你可以明确地定义你的函子：

template <class T>
struct by_second { 
    bool operator()(T const &a, T const &b) { 
        return a.second < b.second;
    }
};

std::sort(r.begin(), r.end(), by_second());

从那里开始，这是获得每对中的第一项并将其放入结果中的问题：

std::transform(r.begin(), r.end(), std::back_inserter(result),
    [](std::pair<int, int> const &p) { return p.first; });

Answer 2

你可以使用std::sort并提供你自己的比较器：

struct myclass {
    bool operator() (std::pair<int, int> i, std::pair<int, int> j) {
        return (i.second < j.second);
   }
} myobject;

std::sort(r.begin(), r.end(), myobject);

我没有尝试使用deque，但这通常是如何做到的。该链接有一个更彻底的例子，但是:-)