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

CKTIS / C++

std::lower_bound — primeira posição não inferior a uma chave

std::lower_bound procura o limite de um intervalo devidamente particionado: o primeiro elemento que não é inferior à chave ou o fim do intervalo. Devolve um iterador, não confirma que exista um valor igual.

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

Sintaxe

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

std::lower_bound, declarada em <algorithm>, pesquisa [first, last) e devolve o primeiro iterador para o qual comp(*it, value) é falso, ou last se não existir tal elemento. Se comp não for indicado, utiliza a comparação predefinida «menor que». Num intervalo numérico crescente, o resultado aponta para o primeiro elemento >= value, incluindo o primeiro duplicado.

A precondição é que o intervalo esteja particionado para a chave específica: todos os elementos que satisfazem comp(element, value) têm de preceder os restantes. Uma ordenação completa segundo a mesma comparação é suficiente, mas não necessária. A violação desta condição causa comportamento indefinido; a função não ordena os dados.

O resultado não confirma que a chave exista. Verifique it != last antes de utilizar *it. No exemplo com inteiros, o código verifica apenas it != values.end() antes de apresentar o valor candidato; não o compara com a chave. Depois de confirmar que o iterador não está no fim do intervalo, pode testar a igualdade separadamente com *it == key. Numa ordenação personalizada, equivalência significa !comp(a, b) && !comp(b, a), não necessariamente a == b.

São necessários, no mínimo, iteradores para a frente. Para N elementos, o número de comparações é O(log N), mas, sem iteradores de acesso aleatório, o número de passos do iterador pode ser linear. O exemplo destina-se a C++23; o documento associado é um rascunho de trabalho em evolução, não uma edição fixa de C++23.

Exemplos

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

int main() {
    const std::vector<int> values{1, 3, 3, 7};
    for (int key : {3, 4, 9}) {
        const auto it = std::lower_bound(values.begin(), values.end(), key);
        std::cout << key << ": index=" << (it - values.begin());
        if (it != values.end()) {
            std::cout << ", value=" << *it;
        } else {
            std::cout << ", end";
        }
        std::cout << '\n';
    }
}

Resultado

3: index=1, value=3
4: index=3, value=7
9: index=4, end

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