Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C++

std::equal_range: granice elemenata ekvivalentnih ključu

std::equal_range vraća par iteratora koji obuhvaća sve elemente ekvivalentne traženoj vrijednosti u uređenom rasponu.

Verzija: 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> vraća {lower_bound(...), upper_bound(...)}. Prvi iterator označava početak klase ekvivalencije, a drugi položaj iza nje; bez podudaranja oba su jednaka položaju umetanja.

Raspon mora biti particioniran prema comp(element, value) i !comp(value, element), a za svaki element comp(element, value) mora implicirati !comp(value, element). Kršenje bilo kojeg zahtjeva za particioniranje ili te implikacije uzrokuje nedefinirano ponašanje. Potpuno sortiranje istim strogim slabim poretkom siguran je dovoljan uvjet, a ne zaseban zahtjev.

Algoritam zahtijeva forward iterator i izvodi najviše 2 * log2(N) + O(1) usporedbi. Uz random access koraci su logaritamski, ali uz druge iteratore mogu biti linearni. Komparator mora odgovarati poretku kojim je raspon pripremljen.

Primjeri

#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

Izvori