c++ - 如何对 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}

我有一个“蛮力”所有值都为 N² 的工作方法，但它非常糟糕。 也许存在这个 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; });