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

CKTIS / C++

Intervalo de pesquisa particionado

`std::lower_bound` não exige uma ordenação completa: para a chave dada, todos os elementos que satisfazem o teste têm de preceder os que não o satisfazem.

Versão: ISO C++23; implementation support may vary

Sintaxe

#include <algorithm>

std::lower_bound(first, last, key);
std::lower_bound(first, last, key, comp);
std::ranges::lower_bound(first, last, key, comp, proj);
std::ranges::lower_bound(range, key, comp, proj);

// For this key, the predicate must be true for a prefix and false for the rest.
// Classic: bool(comp(element, key))
// Ranges:  bool(std::invoke(comp, std::invoke(proj, element), key))

Um intervalo [first, last) está particionado em relação à chave quando bool(comp(element, key)) dá primeiro apenas true e depois apenas false. Qualquer das partes pode estar vazia e nenhuma tem de estar ordenada internamente. A versão clássica de std::lower_bound, em <algorithm>, devolve o primeiro iterador para o qual o teste é falso, ou last se não houver nenhum. O resultado não tem de ser igual à chave. Se a pré-condição de particionamento for violada, o comportamento é indefinido.

A sobrecarga clássica com comparador só compara no sentido elemento–chave. Pode por isso usar uma expressão lambda [](const Sale& row, int key) que testa row.sales > key; [] não captura nada. std::ranges::lower_bound (desde C++20) aceita um par iterador–sentinela ou um intervalo. O comparador tem de satisfazer indirect_strict_weak_order para os elementos projetados e a chave; &Sale::sales permite comparar inteiros. Ambas as versões exigem, no mínimo, iteradores de avanço e fazem um número logarítmico de comparações, mas o número de avanços pode ser linear sem acesso aleatório. A sobrecarga que recebe um intervalo devolve std::ranges::dangling para um intervalo temporário que não seja um borrowed_range. Não desreferencies iteradores de fim ou invalidados.

std::nth_element e std::partial_sort exigem iteradores de acesso aleatório e uma ordem fraca estrita: comp(x, x) tem de ser falso, e tanto a comparação como a equivalência definida por duas comparações falsas têm de ser transitivas. Para valores inteiros de vendas, a.sales > b.sales cumpre estas regras; >= não. nth_element coloca o elemento da posição escolhida onde ficaria se o intervalo fosse ordenado e separa as duas partes sem garantir a sua ordenação. partial_sort ordena o prefixo pedido e deixa o resto numa ordem não especificada. Nenhum garante o particionamento de todo o intervalo para uma chave arbitrária. Para pesquisas repetidas com chaves diferentes, ordena todo o intervalo segundo o mesmo critério.

Exemplos

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

struct Sale {
    int sales;
};

int main() {
    const std::vector<Sale> rows{{95}, {120}, {70}, {85}, {60}};
    const int key = 90;
    const auto before_key = [](const Sale& row, int key) {
        return row.sales > key;
    };

    const auto classic = std::lower_bound(rows.begin(), rows.end(), key, before_key);
    const auto ranged = std::ranges::lower_bound(rows, key, std::ranges::greater{}, &Sale::sales);

    if (classic != rows.end() && ranged != rows.end()) {
        std::cout << classic->sales << '\n' << ranged->sales << '\n';
    }
}

Resultado

70
70

Para `90`, ambas as chamadas escrevem `70`, o primeiro valor que não ultrapassa o limiar, embora o intervalo não esteja ordenado por ordem decrescente. Para `100`, `95` dá `false` antes de `120` dar `true`: nenhuma das chamadas é válida com `100` neste intervalo.

Lições relacionadas

  • C++ · Lição 23 · Avançado · Versão: 3

Fontes