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

CKTIS / C++

std::ranges::equal_range — intervalo de elementos equivalentes

std::ranges::equal_range encontra o intervalo semiaberto dos elementos equivalentes a um valor procurado segundo um comparador. Suporta intervalos, pares iterador-sentinela e projeções; os dados têm de estar particionados adequadamente, o que a ordenação garante.

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

Sintaxe

std::ranges::equal_range(first, last, value)
std::ranges::equal_range(first, last, value, comp)
std::ranges::equal_range(first, last, value, comp, proj)
std::ranges::equal_range(range, value)
std::ranges::equal_range(range, value, comp)
std::ranges::equal_range(range, value, comp, proj)

std::ranges::equal_range, declarado em <algorithm>, determina o intervalo [lower_bound, upper_bound) sem alterar os dados. Equivalência significa que ambas as comparações comp(proj(element), value) e comp(value, proj(element)) são falsas; não tem de coincidir com operator==. Se não houver correspondências, o resultado é um intervalo vazio na posição de inserção do valor.

A chamada aceita um par iterador-sentinela ou um intervalo completo. São necessários, pelo menos, iteradores forward e comp tem de cumprir os requisitos de uma ordem estrita fraca. Os valores predefinidos são std::ranges::less e std::identity. A projeção transforma os elementos, não o valor procurado. Os dados têm de estar particionados de modo que os resultados booleanos de cada expressão comp(proj(element), value) e !comp(value, proj(element)) formem primeiro um prefixo verdadeiro e depois um sufixo falso. Ordenar com o mesmo comparador e a mesma projeção é suficiente; violar as pré-condições causa comportamento indefinido.

A sobrecarga com iteradores devolve std::ranges::subrange<I>, enquanto a sobrecarga com intervalo devolve std::ranges::borrowed_subrange_t<R>. Para um intervalo temporário que não modele borrowed_range, este último tipo é std::ranges::dangling, não um subintervalo utilizável. O resultado não guarda cópias dos elementos: os dados têm de continuar a existir e os respetivos iteradores têm de permanecer válidos.

Para N elementos, há no máximo 2 * log2(N) + O(1) comparações e projeções; sem iteradores de acesso aleatório, os movimentos dos iteradores podem ser lineares. O exemplo procura chaves através de &Item::key: três correspondências ocupam os índices [1, 4), enquanto a chave 3 produz um resultado vazio. O exemplo destina-se a uma configuração de compilação C++23; a compatibilidade de execução em produção não está atestada.

Exemplos

#include <algorithm>
#include <array>
#include <iostream>

struct Item {
    int key;
};

int main() {
    const std::array<Item, 5> items{{{1}, {2}, {2}, {2}, {4}}};
    const auto matches = std::ranges::equal_range(items, 2, {}, &Item::key);
    std::cout << "count=" << matches.size() << '\n';
    std::cout << "begin=" << (matches.begin() - items.begin()) << '\n';
    std::cout << "end=" << (matches.end() - items.begin()) << '\n';
    const auto missing = std::ranges::equal_range(items, 3, {}, &Item::key);
    std::cout << "missing=" << missing.empty() << '\n';
}

Resultado

count=3
begin=1
end=4
missing=1

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