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