c++ - 如何对向量或双端队列 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并提供自己的比较器：

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特别尝试过这个，但这通常是这样做的。不过，该链接有一个更详尽的示例：-)

Answer 2

您只需要定义一个比较运算符即可使用对中的第二项：

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; });