Nota: Mientras escribía esta pregunta, creo que ya encontré la respuesta. Siéntase libre de enmendarlo o agregarlo con una versión mejor. Pensé que sería bueno documentar mi problema.editar Estaba equivocado, mi respuesta no era correcta.

Considerando una lista de pares de enteros: me gustaría ordenarlos topológicamente en función de un orden parcial. Esto es similar a¿Es el orden parcial, en contraste con el orden total, suficiente para construir un montón? , pero me gustaría usar std :: sort en lugar de std :: priority_queue.

Para hacerlo, escribí este fragmento de código:

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

Fuente:http://ideone.com/CxOVO0

Resultando en:

(1, 1) (1, 2) (2, 1) (3, 1) (1, 3) (2, 2) (4, 0) (5, 5) 

Que está ordenado por topología (prueba por ejemplo;).

Sin embargo, el orden parcial crea que! ((1,2) <(2,1)) y! ((1,2)> (2,1)) de acuerdo con el tpc, y por lo tanto, uno puede concluir (1,2 ) == (2,1). Sin embargo, el párrafo 25.4.3 del estándar c ++ (borrador de trabajo de enero de 2012) establece:

Para todos los algoritmos que toman Comparar, hay una versión que usa el operador <en su lugar. Es decir, comp (* i, * j)! = Falso por defecto es * i <* j! = Falso. Para que otros algoritmos distintos a los descritos en 25.4.3 funcionen correctamente, comp debe inducir un orden débil estricto en los valores.

Editado: Según la respuesta válida de ecatmur: un pedido parcial no es necesariamente un pedido débil estricto; se rompe eltransitividad de la incomparibilidad. Por lo tanto, me gustaría abandonar mi razonamiento de que un pedido parcial siempre es un pedido débil estricto y las preguntas asociadas, y agregar la pregunta: ¿estoy condenado a escribir mi propio algoritmo de clasificación topológica o usar la implementación de impulso que me obliga a construir el ¿grafico?

Solución: Una sugerencia inteligente de ecatmur:

struct topological_pair_comparator {
    bool operator()(const pair &p, const pair &q) const { return (p.a + p.b) < (q.a + q.b); }
} tpc;

Fuente:http://ideone.com/uoOXNC

Tenga en cuenta que el SO sobre montones no menciona explícitamente que std :: sort se clasifica topológicamente; a excepción de un comentario, que no está respaldado por argumentos.