CKTIS / C++
std::equal_range: граници на елементите, еквивалентни на ключ
std::equal_range връща двойка итератори около всички елементи, еквивалентни на търсената стойност в подреден диапазон.
Версия: C++23
Синтаксис
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) от <algorithm> връща {lower_bound(...), upper_bound(...)}. Първият итератор сочи началото на класа на еквивалентност, а вторият позицията след него; без съвпадение и двата са позицията за вмъкване.
Диапазонът трябва да е разделен спрямо comp(element, value) и !comp(value, element), а за всеки елемент comp(element, value) трябва да имплицира !comp(value, element). Нарушаването на което и да е разделяне или на тази импликация води до неопределено поведение. Пълното сортиране със същата строга слаба наредба е безопасно достатъчно условие, не отделно изискване.
Алгоритъмът изисква forward iterator и прави най-много 2 * log2(N) + O(1) сравнения. При random access стъпките са логаритмични, но при други итератори може да са линейни. Компараторът трябва да съответства на наредбата, използвана за подготовка на диапазона.
Примери
#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';
}
Резултат
1 3
std::equal_range → 1 3