Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

CKTIS / C++

std::equal_range: meje elementov, enakovrednih ključu

std::equal_range vrne par iteratorjev okoli vseh elementov, enakovrednih iskani vrednosti v urejenem obsegu.

Različica: C++23

Sintaksa

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) iz <algorithm> vrne {lower_bound(...), upper_bound(...)}. Prvi iterator označi začetek razreda enakovrednosti, drugi položaj za njim; če ujemanja ni, sta oba enaka mestu vstavljanja.

Obseg mora biti razdeljen glede na comp(element, value) in !comp(value, element), za vsak element pa mora comp(element, value) implicirati !comp(value, element). Kršitev katere koli razdelitve ali te implikacije povzroči nedoločeno vedenje. Popolno razvrščanje z isto strogo šibko ureditvijo je varen zadosten pogoj, ne ločena zahteva.

Algoritem zahteva forward iterator in izvede največ 2 * log2(N) + O(1) primerjav. Z random access je število korakov logaritemsko, z drugimi iteratorji pa je lahko linearno. Primerjalnik se mora ujemati z ureditvijo, uporabljeno za pripravo obsega.

Primeri

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

Rezultat

1 3

std::equal_range → 1 3

Viri