CKTIS / C++
std::ranges::equal_range — диапазон от еквивалентни елементи
std::ranges::equal_range намира полуотворения диапазон от елементи, еквивалентни на търсена стойност според компаратор. Поддържа диапазони, двойки итератор–сентинел и проекции; данните трябва да са подходящо разделени, което се гарантира чрез сортиране.
Версия: C++23; repository compiler flag, production runtime not attested
Синтаксис
std::ranges::equal_range(first, last, value)
std::ranges::equal_range(first, last, value, comp)
std::ranges::equal_range(first, last, value, comp, proj)
std::ranges::equal_range(range, value)
std::ranges::equal_range(range, value, comp)
std::ranges::equal_range(range, value, comp, proj)std::ranges::equal_range, декларирана в <algorithm>, определя диапазона [lower_bound, upper_bound) без да променя данните. Еквивалентност означава, че и двете сравнения comp(proj(element), value) и comp(value, proj(element)) са неверни; не е необходимо да съвпада с operator==. Ако няма съвпадение, резултатът е празен диапазон на позицията за вмъкване на стойността.
Извикването приема двойка итератор–сентинел или цял диапазон. Необходими са поне forward итератори, а comp трябва да изпълнява изискванията за строго слабо подреждане. Стойностите по подразбиране са std::ranges::less и std::identity. Проекцията преобразува елементите, а не търсената стойност. Данните трябва да са разделени така, че булевите резултати на всеки от изразите comp(proj(element), value) и !comp(value, proj(element)) първо да образуват истинен префикс, а след това неистинен суфикс. Сортирането със същия компаратор и проекция е достатъчно; нарушаването на предварителните условия води до неопределено поведение.
Вариантът с итератори връща std::ranges::subrange<I>, а вариантът с диапазон връща std::ranges::borrowed_subrange_t<R>. За временен диапазон, който не удовлетворява borrowed_range, последният тип е std::ranges::dangling, а не използваем поддиапазон. Резултатът не съхранява копия на елементите: данните трябва да продължат да съществуват, а итераторите им да останат валидни.
За N елемента има най-много 2 * log2(N) + O(1) сравнения и проекции; без итератори с произволен достъп преместванията на итераторите може да са линейни. Примерът търси ключове чрез &Item::key: три съвпадения заемат индексите [1, 4), а ключ 3 дава празен резултат. Примерът е предназначен за конфигурация за компилация C++23; съвместимостта при изпълнение в продукционна среда не е потвърдена.
Примери
#include <algorithm>
#include <array>
#include <iostream>
struct Item {
int key;
};
int main() {
const std::array<Item, 5> items{{{1}, {2}, {2}, {2}, {4}}};
const auto matches = std::ranges::equal_range(items, 2, {}, &Item::key);
std::cout << "count=" << matches.size() << '\n';
std::cout << "begin=" << (matches.begin() - items.begin()) << '\n';
std::cout << "end=" << (matches.end() - items.begin()) << '\n';
const auto missing = std::ranges::equal_range(items, 3, {}, &Item::key);
std::cout << "missing=" << missing.empty() << '\n';
}
Резултат
count=3 begin=1 end=4 missing=1
Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.