Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C++

std::equal_range: granice elementów równoważnych kluczowi

std::equal_range zwraca parę iteratorów ograniczającą wszystkie elementy równoważne szukanej wartości w uporządkowanym zakresie.

Wersja: C++23

Składnia

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> zwraca {lower_bound(...), upper_bound(...)}. Pierwszy iterator wskazuje początek klasy równoważności, a drugi pozycję za nią; gdy brak dopasowania, oba są równe pozycji wstawienia.

Zakres musi być partycjonowany względem comp(element, value) oraz !comp(value, element), a dla każdego elementu comp(element, value) musi implikować !comp(value, element). Naruszenie któregokolwiek z tych warunków wstępnych daje niezdefiniowane zachowanie. Pełne sortowanie tym samym ścisłym słabym porządkiem jest bezpiecznym warunkiem wystarczającym, lecz nie jest samo wymagane.

Algorytm wymaga iteratora forward i wykonuje najwyżej 2 * log2(N) + O(1) porównań. Dla iteratorów random access liczba kroków jest logarytmiczna, ale dla pozostałych może być liniowa. Komparator musi być zgodny z porządkiem użytym do przygotowania zakresu.

Przykłady

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

Wynik

1 3

std::equal_range → 1 3

Źródła