CKTIS / C++
std::ranges::equal_range — rozsah ekvivalentných prvkov
std::ranges::equal_range nájde polootvorený rozsah prvkov ekvivalentných hľadanej hodnote podľa komparátora. Podporuje rozsahy, dvojice iterátor–sentinel a projekcie; údaje musia byť vhodne rozdelené, čo zabezpečí ich usporiadanie.
Verzia: C++23; repository compiler flag, production runtime not attested
Syntax
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 zmeny údajov. Ekvivalencia znamená, že obe porovnania comp(proj(element), value) a comp(value, proj(element)) sú nepravdivé; nemusia sa zhodovať s operator==. Ak sa nenájde zhoda, výsledkom je prázdny rozsah na pozícii vloženia hodnoty.
Volanie prijíma dvojicu iterátor–sentinel alebo celý rozsah. Vyžadujú sa aspoň forward iterátory a comp musí spĺňať požiadavky na striktné slabé usporiadanie. Predvolené hodnoty sú std::ranges::less a std::identity. Projekcia transformuje prvky, nie hľadanú hodnotu. Údaje musia byť rozdelené tak, aby booleovské výsledky každého z výrazov comp(proj(element), value) a !comp(value, proj(element)) tvorili najprv pravdivý prefix a potom nepravdivý suffix. Usporiadanie pomocou toho istého komparátora a projekcie stačí; porušenie predpokladov spôsobí nedefinované správanie.
Verzia s iterátormi vracia std::ranges::subrange<I>, kým verzia s rozsahom vracia std::ranges::borrowed_subrange_t<R>. Pri dočasnom rozsahu, ktorý nespĺňa borrowed_range, je druhý typ std::ranges::dangling, nie použiteľný podrozsah. Výsledok neukladá kópie prvkov: údaje musia naďalej existovať a ich iterátory musia zostať platné.
Pre N prvkov je najviac 2 * log2(N) + O(1) porovnaní a projekcií; bez iterátorov s náhodným prístupom môže byť počet posunov iterátorov lineárny. Príklad vyhľadáva kľúče cez &Item::key: tri zhody majú indexy [1, 4), zatiaľ čo kľúč 3 vráti prázdny výsledok. Príklad je určený pre konfiguráciu zostavenia C++23; kompatibilita behu v produkčnom prostredí nie je potvrdená.
Prí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ýsledok
count=3 begin=1 end=4 missing=1
Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.