Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

CKTIS / C++

Ordenação, comparações e intervalos de pesquisa

Uma ordenação correta requer um comparador que defina uma ordem fraca estrita. A pesquisa binária requer um intervalo particionado de acordo com a condição relevante; ordenar todo o intervalo é suficiente, mas nem sempre necessário.

Versão: C++23; repository compiler flag, production runtime not attested

Sintaxe

std::sort(first, last, comp);
std::lower_bound(first, last, value, comp);

std::sort de <algorithm> ordena o intervalo semiaberto [first, last) segundo comp: nenhum elemento posterior precede um elemento anterior. Requer iteradores de acesso aleatório e elementos que cumpram os requisitos de movimentação e troca. Efetua O(N log N) comparações. Não garante a preservação da ordem dos elementos equivalentes; para isso, use std::stable_sort.

O comparador tem de definir uma ordem fraca estrita. comp(a, b) significa que a precede b, e comp(a, a) tem de ser falso. A relação tem de ser transitiva. A equivalência definida por !comp(a, b) && !comp(b, a) também tem de ser transitiva e não tem necessariamente de coincidir com operator==. Não use <=: viola o requisito para argumentos idênticos. Se os requisitos do comparador não forem cumpridos, as garantias do algoritmo deixam de se aplicar.

A ordem fraca estrita e a partição dos intervalos de pesquisa são requisitos relacionados, mas distintos. Num intervalo particionado segundo um predicado, todos os elementos cujo resultado é true surgem antes dos que dão false; qualquer uma das partes pode estar vazia. Para std::lower_bound(first, last, value, comp), o predicado é comp(e, value). A função devolve a fronteira: o primeiro elemento cujo resultado é false, ou last. Isto não confirma que o valor pesquisado está presente; não desreferencie last.

Ordenar segundo a mesma ordem garante esta partição para qualquer chave. Para uma única chave, basta a partição: [2, 1, 4, 3] cumpre a pré-condição de std::lower_bound para value = 3 e a comparação <, apesar de não estar ordenado. As outras funções de pesquisa binária têm requisitos de partição próprios. std::lower_bound efetua O(log N) comparações, mas, sem iteradores de acesso aleatório, pode exigir um número linear de passos do iterador.

O exemplo ordena números inteiros e, em seguida, usa o mesmo comp para obter o índice 3. O conteúdo tem como objetivo C++23; a referência fornecida aponta para um rascunho de trabalho em evolução, não para uma publicação C++23 definitiva. O suporte do compilador e do ambiente de execução de produção não está atestado.

Exemplos

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{4, 1, 3, 1, 2};
    const auto comp = [](int a, int b) { return a < b; };

    std::sort(values.begin(), values.end(), comp);
    for (std::size_t i = 0; i < values.size(); ++i) {
        if (i != 0) std::cout << ' ';
        std::cout << values[i];
    }
    std::cout << '\n';

    const auto it = std::lower_bound(values.begin(), values.end(), 3, comp);
    std::cout << "index=" << (it - values.begin()) << '\n';
}

Resultado

1 1 2 3 4
index=3

O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.

Fontes