Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

CKTIS / C++

std::equal_range: hranice prvkov ekvivalentných kľúču

std::equal_range vráti dvojicu iterátorov ohraničujúcu všetky prvky ekvivalentné hľadanej hodnote v usporiadanom rozsahu.

Verzia: C++23

Syntax

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) z <algorithm> vracia {lower_bound(...), upper_bound(...)}. Prvý iterátor označuje začiatok triedy ekvivalencie a druhý pozíciu za ňou; ak zhoda nie je, oba ukazujú na pozíciu vloženia.

Rozsah musí byť rozdelený podľa comp(element, value) aj !comp(value, element) a pre každý prvok musí comp(element, value) implikovať !comp(value, element). Porušenie ktoréhokoľvek rozdelenia alebo tejto implikácie vedie k nedefinovanému správaniu. Úplné zoradenie rovnakým striktným slabým usporiadaním je bezpečná postačujúca podmienka, nie samostatná požiadavka.

Algoritmus vyžaduje dopredný iterátor a vykoná najviac 2 * log2(N) + O(1) porovnaní. S random access sú kroky logaritmické, s inými iterátormi môžu byť lineárne. Komparátor musí zodpovedať usporiadaniu použitému na prípravu rozsahu.

Príklady

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

Výsledok

1 3

std::equal_range → 1 3

Zdroje