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

CKTIS / C++

std::upper_bound — o limite após os elementos equivalentes

`std::upper_bound` encontra o limite da partição para o valor procurado: devolve um iterador para o primeiro elemento em relação ao qual `value` é menor segundo a comparação usada, ou `last` se não existir tal elemento. Com a comparação predefinida e números ordenados por ordem crescente, trata-se do primeiro número maior do que `value`.

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

Sintaxe

#include <algorithm>
std::upper_bound(first, last, value)
std::upper_bound(first, last, value, comp)

std::upper_bound, declarado em <algorithm>, pesquisa o intervalo semiaberto [first, last). Com a comparação predefinida e num intervalo crescente, devolve o primeiro elemento maior do que value, ignorando todos os duplicados desse valor. O resultado é um iterador, não um índice nem uma indicação de presença. Se não existir nenhum elemento que satisfaça a condição, incluindo num intervalo vazio, o resultado é last. Antes de o desreferenciar, verifica se o resultado é diferente de last.

A sobrecarga que recebe comp procura o primeiro elemento e para o qual comp(value, e) é verdadeiro. A precondição exige que o intervalo esteja particionado: primeiro têm de estar todos os elementos para os quais !comp(value, e) é verdadeiro e, depois, os restantes. Uma ordenação completa segundo uma ordem compatível é suficiente, mas não é necessária para uma única pesquisa. Não pesquises dados arbitrariamente desordenados: a violação da precondição causa comportamento indefinido. O significado de «maior» depende do comparador e não necessariamente do operador numérico >.

Num intervalo crescente, std::lower_bound encontra o primeiro elemento que não é menor do que value, enquanto std::upper_bound encontra o primeiro elemento maior. Num intervalo ordenado, estes limites delimitam os elementos equivalentes segundo a comparação. Repara na ordem dos argumentos: std::upper_bound usa comp(value, element), não comp(element, value).

São necessários, no mínimo, iteradores forward. O número de comparações é O(log N), mas, sem acesso aleatório, o número de passos pode ser O(N); com iteradores de std::vector, é logarítmico. O exemplo usa sintaxe compatível com C++23. O projeto de trabalho ligado continua a evoluir e pode conter declarações mais recentes.

Exemplos

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

int main() {
    const std::vector<int> values{1, 2, 2, 2, 4, 7};
    const auto it = std::upper_bound(values.begin(), values.end(), 2);
    std::cout << "index=" << (it - values.begin()) << '\n';
    if (it != values.end()) {
        std::cout << "value=" << *it << '\n';
    }
    const auto end = std::upper_bound(values.begin(), values.end(), 7);
    std::cout << "at_end=" << std::boolalpha << (end == values.end()) << '\n';
}

Resultado

index=4
value=4
at_end=true

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