Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

CKTIS / C++

std::ranges::equal_range — intervallo di elementi equivalenti

std::ranges::equal_range trova l’intervallo semiaperto degli elementi equivalenti a un valore cercato secondo un comparatore. Supporta intervalli, coppie iteratore-sentinella e proiezioni; i dati devono essere partizionati correttamente, condizione garantita dall’ordinamento.

Versione: C++23; repository compiler flag, production runtime not attested

Sintassi

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, dichiarato in <algorithm>, determina l’intervallo [lower_bound, upper_bound) senza modificare i dati. Equivalenza significa che entrambi i confronti comp(proj(element), value) e comp(value, proj(element)) sono falsi; non è necessario che coincida con operator==. Se non ci sono corrispondenze, il risultato è un intervallo vuoto nella posizione di inserimento del valore.

La chiamata accetta una coppia iteratore-sentinella oppure un intervallo completo. Sono richiesti almeno iteratori forward e comp deve soddisfare i requisiti di un ordine stretto debole. I valori predefiniti sono std::ranges::less e std::identity. La proiezione trasforma gli elementi, non il valore cercato. I dati devono essere partizionati in modo che i risultati booleani di ciascuna espressione comp(proj(element), value) e !comp(value, proj(element)) formino prima un prefisso vero e poi un suffisso falso. Ordinare con lo stesso comparatore e la stessa proiezione è sufficiente; violare le precondizioni causa comportamento indefinito.

L’overload con iteratori restituisce std::ranges::subrange<I>, mentre quello con intervallo restituisce std::ranges::borrowed_subrange_t<R>. Per un intervallo temporaneo che non modella borrowed_range, quest’ultimo tipo è std::ranges::dangling, non un sottointervallo utilizzabile. Il risultato non conserva copie degli elementi: i dati devono continuare a esistere e i relativi iteratori devono restare validi.

Per N elementi, si effettuano al massimo 2 * log2(N) + O(1) confronti e proiezioni; senza iteratori ad accesso casuale, gli spostamenti degli iteratori possono essere lineari. L’esempio cerca le chiavi tramite &Item::key: tre corrispondenze occupano gli indici [1, 4), mentre la chiave 3 produce un risultato vuoto. L’esempio è destinato a una configurazione di compilazione C++23; la compatibilità di esecuzione in produzione non è attestata.

Esempi

#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';
}

Risultato

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

Il codice mostrato e il risultato dichiarato sono stati verificati in un ambiente isolato con il metodo registrato nella prova di verifica di questa versione esatta.

Fonti