c++ - 使用 std::sort 进行拓扑排序

注意: 在写这个问题时，我想我已经找到了答案。随意修改或附加一个更好的版本。我认为记录我的问题可能会很好。 编辑 我错了，我的答案不正确。考虑整数对列表:我想根据偏序对它们进行拓扑排序。这类似于 Is partial-order, in contrast to total-order, enough to build a heap? ，但我想使用 std::sort 而不是 std::priority_queue。为此，我编写了这段代码:#include <iostream>#include <vector>#include <algorithm>struct pair { int a, b; pair(int a, int b) : a(a), b(b) {} std::ostream &print(std::ostream &out) const { return (out << "(" << a << ", " << b << ")"); }};std::ostream &operator<<(std::ostream &out, const pair &p) { return p.print(out); }struct topological_pair_comparator { bool operator()(const pair &p, const pair &q) const { return p.a<q.a && p.b<q.b; }} tpc;std::vector<pair> pairs = { pair(1,1), pair(1,2), pair(2,1), pair(3,1), pair(1,3), pair(5,5), pair(2,2), pair(4,0)};int main() { std::sort(pairs.begin(), pairs.end(), tpc); for(const pair &p : pairs) std::cout << p << " "; std::cout << std::endl; return 0;}资料来源:http://ideone.com/CxOVO0导致:(1, 1) (1, 2) (2, 1) (3, 1) (1, 3) (2, 2) (4, 0) (5, 5)这几乎是拓扑排序的(示例证明；)。然而，偏序根据 tpc 创建了 !((1,2) (2,1)) ，因此可以得出结论 (1,2 ) == (2,1)。但是，c++ 标准(2012 年 1 月工作草案)的第 25.4.3 段指出: For all algorithms that take Compare, there is a version that uses operator< instead. That is, comp(*i, *j) != false defaults to *i < *j != false. For algorithms other than those described in 25.4.3 to work correctly, comp has to induce a strict weak ordering on the values. 编辑: 根据 ecatmur 的有效答案:偏序不一定是严格的弱序；它打破了不可比性的传递性。所以我想放弃我的推理，即偏序总是严格的弱排序和相关问题，并添加一个问题:我是注定要编写自己的拓扑排序算法还是使用需要我构建图形？ 解决方案: ecatmur 的一个聪明建议: struct topological_pair_comparator { bool operator()(const pair &p, const pair &q) const { return (p.a + p.b) < (q.a + q.b); }} tpc;资料来源:http://ideone.com/uoOXNC请注意，关于堆的 SO 没有明确提到 std::sort 拓扑排序；除了一条评论，没有论证支持。 最佳答案 考虑值(value)pair x{0, 1}, y{2, 0}, z{1, 2};这里，!tpc(x, y) && !tpc(y, x);!tpc(y, z) && !tpc(z, y);然而，tpc(x, z);因此，您的比较器不会强加严格的弱排序，如果您将它与 std::sort 或任何其他需要严格弱排序的角色一起使用，则行为是未定义的。一个严格弱的比较器是你的比较器的改进:struct refined_comparator { bool operator()(const pair &p, const pair &q) const { return p.a + p.b < q.a + q.b; }} rc;关于c++ - 使用 std::sort 进行拓扑排序，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/24286209/