Início / coding / Perguntas / 79185202
Accepted
PiotrNycz
Asked: 2024-11-13 21:50:04 +0800 CST

std::ranges::sort não funciona com operador não padrão<=>?

  • 772

Tenho um caso em que o tipo struct não precisa ser padrão operator<=>- só que nem todos os campos são importantes ao definir a ordem dos objetos.

struct A
{
    int a;
    int b; // not important when ordering
    int c;

    constexpr std::strong_ordering operator<=>(const A& rhs) const
    {
        if (const auto res = a<=>rhs.a; res != 0) return res;
        return c<=>rhs.c;
    }
};

Para minha surpresa, não posso usar container com esse tipo como argumento para std::ranges::sort:

std::array<A, 100> aa{};
std::ranges::sort(aa);

Eu verifiquei no mais novo gcc (14) e clang (19) e ele basicamente afirma que o intervalo não é classificável porque std::invocable_v<std::ranges::less&, A&, A&>não é verdade. Veja o link godbold

Mais observações:

  1. Funciona com std::sort( std::sort(aa.begin(), aa.end());)
  2. Funciona ao adicionar não padrãooperator==
  3. E funciona com o padrão ( =default)operator<=>

Isso é um bug do compilador, um bug padrão do C++ ou alguma regra estranha do C++ está em jogo aqui e deveria ser assim? Se a última opção estiver correta - você pode fornecer uma justificativa para tal comportamento?

Atualizar:

Pelos comentários parece que std::ranges::less{}(A{}, A{})requer não apenas operator<(derivado de operator<=>), mas também operator==que não pode ser derivado de não padrão, operator<=>então o erro.

Mas uma questão permanece: por que std::ranges::lessas necessidades operator==?

E melhor exemplo dos comentários: link

c++

2 respostas

  1. Em geral, os std::rangesalgoritmos são muito mais restritos do que os std::outros. O objetivo não é fornecer o conjunto mínimo absoluto de operações que os algoritmos precisam, mas sim um modelo coeso de operações.

    Neste caso, todos os algoritmos baseados em ordenação exigem tanto ordenação quanto igualdade. Em várias outras linguagens, você não pode nem optar por ordenação sem também fornecer igualdade. É a funcionalidade mais fraca, então faz sentido ter ambas.

    Então std::ranges::sort(aa)falha porque enquanto Afornece uma ordenação ( <=>) não fornece igualdade ( ==). Então suas opções são:

    • ou fornecer um ==operador correspondente (que também não olha para b), ou
    • fornecer uma ordenação personalizada para sort(que não olharia para b).

    Observe que os algoritmos de intervalo oferecem suporte a projeções, então estas podem se parecer com:

    std::ranges::sort(aa, std::ranges::less(), [](A const& a){ return std::tie(a.a, a.c); });

    Que você pode embrulhar em um adaptador fofo como este:

    std::ranges::sort(aa, std::ranges::less(), by(&A::a, &A::c));
    • 4
  2. Best Answer

    Algoritmos de ordenação dependem do fato de que os itens que estão sendo ordenados são totalmente ordenados (no sentido matemático). Isso significa que há uma ordem que é reflexiva, transitiva, antisimétrica e, para ser uma ordem total , fortemente conectada, o que significa que para qualquer ae b,

    a <= b || b <= a

    ou:

    if (a != b) then a <= b or b <= a

    e por causa do requisito de antisimetria, é OU a <= bOU b <= a. Isso novamente implica que para qualquer coleção a, b, c, ...existe uma permutação x, y, z, ...tal que x <= y <= z <= ..., ou em outras palavras: A coleção pode ser classificada.

    Então a restrição para ranges::lessque seus operandos devam ser totalmente ordenados existe não apenas para o propósito de requerer que certos operadores estejam disponíveis, mas também para indicar que os operadores devem ter certa semântica. Algoritmos podem então ser escritos sob a suposição de que os operadores disponíveis têm essa semântica.

    É por isso que conceitos em C++20 frequentemente têm requisitos semânticos além de requisitos de tipo. Requisitos semânticos não são impostos pelo compilador, mas os desenvolvedores devem honrá-los ao definir um tipo que modela um conceito e, como resultado, quando um tipo modela um conceito, os desenvolvedores podem assumir que o tipo também preenche todos os requisitos semânticos do conceito.

    Se um tipo é totalmente ordenado, então todos os operadores de comparação são bem definidos para ele e podem ser (matematicamente) inferidos somente do <operador. Portanto, o totally_orderedconceito requer que todos os operadores estejam disponíveis, simplesmente porque é significativo para um tipo totalmente ordenado, e porque é fácil definir todos os operadores usando o <=>operador.

    No entanto, por razões de desempenho, o compilador não gera automaticamente o ==operador quando um tipo tem um <=>operador personalizado, porque <=>potencialmente não pode ser implementado tão eficientemente quanto ==, e não é garantido que o ==operador fornecido implicitamente teria a mesma semântica como se fosse implementado em termos do <=>operador (personalizado). Por exemplo, ao comparar strings, ==pode ter complexidade de tempo O(1) para strings que têm comprimento diferente, enquanto <=>não pode.

    Portanto, se <=>não for o padrão, você precisa definir explicitamente ==para que todos os operadores de comparação sejam definidos, o que é necessário para modelar o conceito totally_ordered, que é exigido por ranges_less, que é usado por ranges::sort, porque os algoritmos de classificação exigem ordem total para funcionarem conforme o planejado.

    Veja também esta resposta a uma pergunta diferente .

    • 1

relate perguntas