Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

CKTIS / C++

std::equal_range: limiti degli elementi equivalenti a una chiave

std::equal_range restituisce una coppia di iteratori che racchiude tutti gli elementi equivalenti al valore cercato in un intervallo ordinato.

Versione: C++23

Sintassi

template<class ForwardIterator, class T, class Compare>
constexpr std::pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last,
            const T& value, Compare comp);

std::equal_range(first, last, value, comp) di <algorithm> restituisce {lower_bound(...), upper_bound(...)}. Il primo iteratore segna l’inizio della classe di equivalenza, il secondo la posizione successiva; senza corrispondenze entrambi indicano la posizione d’inserimento.

L’intervallo deve essere partizionato rispetto a comp(element, value) e !comp(value, element), e comp(element, value) deve implicare !comp(value, element) per ogni elemento. Violare una delle partizioni o tale implicazione causa comportamento indefinito. L’ordinamento completo con lo stesso ordine debole stretto è una condizione sufficiente sicura, non un requisito distinto.

L’algoritmo richiede un forward iterator ed esegue al massimo 2 * log2(N) + O(1) confronti. I passi sono logaritmici con random access, ma possono essere lineari con altri iteratori. Il comparatore deve coincidere con l’ordine usato per preparare l’intervallo.

Esempi

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

int main() {
    const std::vector<int> values{1, 2, 2, 2, 4};
    const auto [first, last] = std::equal_range(values.begin(), values.end(), 2);
    std::cout << (first - values.begin()) << ' ' << (last - first) << '\n';
}

Risultato

1 3

std::equal_range → 1 3

Fonti