База знанияИзпитен център
BGБългарски
Избери език13

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

Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.

Източници