时间戳

首页 > 解决方案 > 用一对对排序 STL 容器

c++ - 用一对对排序 STL 容器

问题描述

这是我第一次使用 C++ STL priority_queue()，我对遇到的这段特定代码有点困惑（但我相信这与 pq 无关，它应该适用于所有容器（向量、集合等） ):

priority_queue<pair<int, pair<int, int> >,
            vector<pair<int, pair<int, int> > >,
            greater<pair<int, pair<int, int> > > > pq;

可以说我有pq.push_back(make_pair(a,make_pair(b,c)))。如果存在 的冲突a，那么比较规则是否会扩展到第二对，并且将在 和 的基础上进行b排序c？

标签： c++c++11stl

解决方案

这个问题基本上归结为：std::pairs 是如何排序的，即a > b两对的结果是什么（注意std::greater只是调用operator>）。

从cppreference开始std::pair::operator>：

按字典顺序比较 lhs 和 rhs，即比较第一个元素，只有当它们相等时，才比较第二个元素。

这自然会扩展到嵌套对。因此...

假设我有 pq.push_back(make_pair(a,make_pair(b,c)))。如果a发生冲突，那么比较规则是否会延伸到第二对，并且会根据b然后c进行排序？

是的。如果两个元素相等，a则将比较second最外面的一对（即(b,c)）。

推荐阅读