CKTIS / C++
std::ranges::equal_range — rozsah ekvivalentních prvků
std::ranges::equal_range najde polouzavřený rozsah prvků ekvivalentních hledané hodnotě podle komparátoru. Podporuje rozsahy, dvojice iterátor–sentinel a projekce; data musejí být vhodně rozdělena, což zajišťuje jejich seřazení.
Verze: C++23; repository compiler flag, production runtime not attested
Syntaxe
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 deklarované v <algorithm> určí rozsah [lower_bound, upper_bound) bez změny dat. Ekvivalence znamená, že obě porovnání comp(proj(element), value) a comp(value, proj(element)) jsou nepravdivá; nemusí odpovídat operator==. Pokud žádná shoda neexistuje, výsledkem je prázdný rozsah na pozici, kam by se hodnota vložila.
Volání přijímá dvojici iterátor–sentinel nebo celý rozsah. Jsou vyžadovány alespoň forward iterátory a comp musí splňovat požadavky na striktní slabé uspořádání. Výchozí hodnoty jsou std::ranges::less a std::identity. Projekce transformuje prvky, nikoli hledanou hodnotu. Data musejí být rozdělena tak, aby booleovské výsledky každého z výrazů comp(proj(element), value) a !comp(value, proj(element)) tvořily nejprve pravdivý prefix a poté nepravdivý suffix. Seřazení pomocí stejného komparátoru a projekce stačí; porušení předpokladů vede k nedefinovanému chování.
Varianta s iterátory vrací std::ranges::subrange<I>, zatímco varianta s rozsahem vrací std::ranges::borrowed_subrange_t<R>. U dočasného rozsahu, který nesplňuje borrowed_range, je druhý typ std::ranges::dangling, nikoli použitelný podrozsah. Výsledek neukládá kopie prvků: data musejí nadále existovat a jejich iterátory musejí zůstat platné.
Pro N prvků je nejvýše 2 * log2(N) + O(1) porovnání a projekcí; bez iterátorů s náhodným přístupem může být počet posunů iterátorů lineární. Příklad hledá klíče přes &Item::key: tři shody mají indexy [1, 4), zatímco klíč 3 vrátí prázdný výsledek. Příklad je určen pro konfiguraci sestavení C++23; kompatibilita běhu v produkčním prostředí není potvrzena.
Příklady
#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';
}
Výsledek
count=3 begin=1 end=4 missing=1
Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.