30.3 Ranges algoritmusok, projection és sentinel

A hagyományos standard algoritmusok két iterátort várnak, a <algorithm> ranges változata viszont egyetlen range-et – és ami a mindennapi hasznot legtöbbször hozza – egy projectiont. Ez a két változás együtt rövidíti le a hívási helyeket, de új szerződéseket is behoz: a range-nek ki kell elégítenie az algoritmus által előírt concepteket, a projectionnek hívhatónak kell lennie a dereferált iterátoron, és a visszatérési típus már nem feltétlenül iterator. Ebben az alfejezetben a std::ranges algoritmusok hívási szerződését, a begin/end customization pontját, a range/iterator/sentinel megkötéseket, a képességtípusokat, a projection gyakorlatát és a dangling jelzést tárgyaljuk. Az iterator-kategóriákra és a fél-nyílt [first,last) tartományra építünk (Iterator-kategóriák és fél-nyílt tartomány), a constrained overload mechanizmusát ismertnek vesszük (Concepts, requires és constrained overload), a member pointer mint callable pedig a std::invoke szabályai szerint működik (invoke, function wrapper és type erasure).

Forrásmegjegyzés. Ehhez az egységhez nem kaptam ellenőrzött forrásjegyzéket, ezért a szöveg nem hivatkozik szabványparagrafusra, és nem állítom, hogy bármely állítás egy konkrét szabványpéldányban vagy implementációban ellenőrizve lenne. Ahol a viselkedés a standard library verziójától függ, ezt külön jelzem.

30.3.1 A hívás szerződése: range, comparator, projection

A ranges algoritmus első paramétere R&& forwardoló referencia, amelyre a sablon range-megkötést ír elő. A további paraméterek típussorrendje algoritmusonként rögzített; a rendező és kereső algoritmusoknál jellemzően (range, comp, proj), illetve (range, value, proj). A projection (vetítés) egy callable, amelyet az algoritmus a dereferált iterátor értékén alkalmaz, mielőtt az összehasonlítást vagy predikátumot kiértékelné:

$$\text{pred}( \text{proj}(*it) ), \qquad \text{comp}\big(\text{proj}(*a),\, \text{proj}(*b)\big).$$

Az alapértelmezett projection std::identity, tehát a std::ranges::sort(v) és a std::ranges::sort(v, std::less{}, std::identity{}) ugyanaz. A projection meghívása std::invoke szabályai szerint történik, ezért lehet tagfüggvény-pointer, member pointer vagy lambda is. A comparatornak a vetített értékeken strict weak orderinget kell megadnia; a projection szerződése, hogy az elemet nem módosítja (a szabvány ezt a nem-konstans hívás tilalmaként fogalmazza meg – a pontos megfogalmazást a használt szabványpéldányban érdemes ellenőrizni).

Az algoritmus saját megkötése például rendezésnél: a range random_access_range, az iteratorra pedig sortable a megadott comparatorral és projectionnel. Ha ezek nem teljesülnek, a hiba a koncepció nevével jelenik meg a diagnosztikában – ez a ranges egyik gyakorlati előnye a hagyományos overloadok hosszú hibaszövegeihez képest.

30.3.2 ranges::begin és ranges::end mint customization pont

A std::ranges::begin és std::ranges::end nem függvények a klasszikus értelemben, hanem customization point objectek (CPO). A ranges::begin(r) kiértékelése rögzített sorrendet követ: tömb esetén a tömb első elemére mutató pointer, egyébként ha van tagfüggvény r.begin(), akkor az, különben nem-tag begin(r) ADL-hívással; ha egyik sem értelmezhető, a kifejezés nem fordítódik le. A ranges::end ugyanezt teszi end-del, tömbnél pedig begin + extent-et ad.

Két következmény fontos. Egyrészt a saját konténer akkor is működik range-ként, ha csak nem-tag begin/end párja van (ez a klasszikus std::begin-nél is így volt, de a CPO ezt következetesen, a const-helyességet is figyelve egységesíti). Másrészt a CPO-nak van egy törölt rvalue overloadja: nem-borrowed konténer temporálisára a ranges::begin nem hívható, így a leggyakoribb „temporális konténer iteratorát elmentem” hiba már fordítási időben megbukik. Ez a védelem azonban csak a begin/end szintjén érvényes; a lazán kiértékelt nézetekre ez nem jelent automatikus élettartam-garanciát (a részleteket lásd Lazy view pipeline és mellékhatások és Borrowed range, dangling és iterator lifetime).

30.3.3 Range-, iterator- és sentinel-megkötések

A range<R> concept lényegében azt követeli, hogy ranges::begin(r) és ranges::end(r) érvényes legyen, és az első egy input_or_output_iterator, a második pedig egy hozzá tartozó sentinel, azaz teljesüljön rá a sentinel_for<sentinel_t<R>, iterator_t<R>>. A sentinel nem kötelezően ugyanolyan típusú, mint az iterator: elég, hogy összehasonlítható legyen vele (it != sent), és hogy az iterálás a sentinel eléréséig definiált legyen. Ez teszi lehetővé a nullterminátoros C sztring vagy egy stream végének természetes modellezését.

A gyakorlatban ezért a ranges algoritmusok belső típusai iterator_t<R> és sentinel_t<R>; a kettő csak ott esik egybe, ahol a range common. A sized_sentinel_for<S, I> további megkötés: a s - i kifejezés konstans időben kiértékelhető távolságot ad. A range-en felül az algoritmusok további concepteket kérnek: input_range, forward_range, random_access_range, contiguous_range, valamint az iterator oldalán indirectly_readable, indirectly_copyable, sortable, permutable stb.

30.3.4 Képességtípusok: sized, common, contiguous, borrowed

A négy képesség egymástól független, és nem következtethetünk egyikből a másikra. A pontos definíciók:

A common_range hiánya nem hiba, csak meghatározza, mely algoritmusok és mely visszatérési típusok használhatók. A sized_range hiánya azt jelenti, hogy a hossz csak bejárással állapítható meg (ranges::distance lineáris). A borrowed_range pedig arról szól, hogy a range-ből nyert iterator érvényes marad-e a range objektum megszűnése után – ez nem azonos azzal, hogy a mögötte lévő elemek is életben maradnak (ezt a Borrowed range, dangling és iterator lifetime (30.5) fejti ki részletesen).

30.3.5 Projection a gyakorlatban

Rekordmező szerinti rendezés hagyományos alakja kézi comparator:

std::sort(hosts.begin(), hosts.end(),
          [](const Host& a, const Host& b) { return a.latency_ms < b.latency_ms; });

Ranges alakban a comparator általános marad, a mezőkiválasztás pedig projection:

std::ranges::sort(hosts, std::less{}, &Host::latency_ms);

A member pointer itt azért használható, mert a projection hívása std::invoke-on keresztül történik; a &Host::latency_ms pointerre (Host*, const Host*) is alkalmazható, ami pointertároló rendezésénél hasznos. Keresésnél ugyanez a szerkezet: std::ranges::find(hosts, value, &Host::name) a proj(*it) == value összehasonlítást végzi.

Két gyakorlati megjegyzés. Egyrészt a projection nem „cache-elt kulcs”: a comparator minden összehasonlításnál újra kiértékeli, így egy drága lambda $O(n\log n)$-szer futhat le; ilyenkor a decorate–sort–undecorate (előre kiszámított kulcsú segédtömb rendezése) a megfelelő minta. Másrészt az azonos kulcsú elemek sorrendje nem garantált: sort nem stabil, ezért kell stable_sort, vagy a projectionnek olyan összetett kulcsot kell adnia (például std::pair/std::tuple, amelyek lexikografikusan rendeződnek), amely a holtversenyt is eldönti.

30.3.6 Kidolgozott példa: hostlista rendezése és keresése

Az alábbi program a C++20 alapra épül, és a fenti elemeket együtt mutatja: range argumentum, comparator, projection, borrowed_iterator_t és dangling.

// hosts.cpp — C++20
#include <algorithm>
#include <iostream>
#include <ranges>
#include <string>
#include <string_view>
#include <type_traits>
#include <vector>

struct Host {
    std::string name;
    int port;
    int latency_ms;
};

int main() {
    std::vector<Host> hosts{
        {"api-1",    443, 41},
        {"db-1",    5432,  7},
        {"cache-1", 6379, 12},
        {"api-2",    443, 95},
    };

    // range + comparator + projection: növekvő latencia
    std::ranges::sort(hosts, std::less{}, &Host::latency_ms);

    auto worst = std::ranges::max_element(hosts, std::less{}, &Host::latency_ms);
    if (worst != hosts.end()) {
        std::cout << "leglassabb: " << worst->name << ' ' << worst->latency_ms << " ms\n";
    }

    // value + projection: a név mezőn keresztül keresünk
    auto hit = std::ranges::find(hosts, std::string_view{"cache-1"}, &Host::name);
    if (hit != hosts.end()) {
        std::cout << "talalat: " << hit->port << '\n';
    }

    // Lvalue vector: az eredmény valódi iterator (borrowed_iterator_t).
    static_assert(std::is_same_v<decltype(worst), std::vector<Host>::iterator>);

    // Nem-borrowed temporális: az eredmény típusa std::ranges::dangling.
    static_assert(std::is_same_v<
        decltype(std::ranges::find(std::vector<int>{1, 2, 3}, 2)),
        std::ranges::dangling>);
}

Fordítás a laborban (a parancsot a tanuló futtatja; a fejezet nem tartalmaz futtatási eredményt):

g++ -std=c++20 -Wall -Wextra -pedantic -O1 hosts.cpp -o hosts
# vagy
clang++ -std=c++20 -Wall -Wextra -pedantic -O1 hosts.cpp -o hosts

A várt – nem mért – kimenet a rendezés és a vetítés alapján: leglassabb: api-2 95 ms, majd talalat: 6379. A static_assertek nem futnak, fordítási időben ellenőriznek; ha a könyvtár a std::ranges::dangling típust nem a várt módon definiálja, a diagnosztika ezt jelzi.

30.3.7 Visszatérési típus és a dangling jelzés

A ranges algoritmusok többsége nem iterator_t<R>-t ad vissza, hanem borrowed_iterator_t<R>-t, amelynek definíciója: iterator_t<R>, ha borrowed_range<R>, egyébként std::ranges::dangling. Ugyanez a minta a borrowed_subrange_t<R> a range-et visszaadó algoritmusoknál. A dangling szándékosan „használhatatlan” típus: nem dereferálható, nem léptethető, csak azt jelzi, hogy az eredmény élettartama nem biztonságos.

Ez a jelzés fordítási idejű, de nem teljes körű: ha a temporális range-ből nyert iterátort nem használjuk, a program lefordul. A valódi javítás mindig élettartam-kérdés: nevezzük el a konténert, tartsuk életben a range-et, vagy olyan range-et használjunk, amelyre az enable_borrowed_range igaz (például std::string_view, std::span, lvalue-ból készült subrange). A dangling tehát diagnosztikai fogódzó, nem automatikus biztonsági háló.

30.3.8 Lefedettségbeli eltérés a hagyományos algoritmusokhoz képest

A C++20-as <algorithm> ranges változata gyakorlatilag teljes: a kereső, módosító, rendező, halmaz- és permutációs algoritmusoknak is van std::ranges:: párjuk. A <numeric> nem ilyen: a klasszikus accumulate, reduce, partial_sum, iota hagyományos alakban maradt, ranges megfelelőjük a C++20 alapban nincs. A C++23 kiegészítések (például ranges::fold_left/fold_right, ranges::iota, ranges::contains, ranges::starts_with/ends_with, ranges::find_last, valamint a range-eket konténerré alakító ranges::to) külön jelölt, verziófüggő képességek: használatuk előtt ellenőrizni kell a fordítót és a standard libraryt, például a <version> header feature-test makróival (a konkrét makrónevek és értékek verziófüggők, ezért itt nem állítom őket). Ahol a ranges alak hiányzik, a hagyományos algoritmus továbbra is használható: std::ranges::begin(r) és std::ranges::end(r) átadásával a két világ keverhető, feltéve, hogy az iterator- és sentineltípusok az adott algoritmus követelményeinek megfelelnek.

30.3.9 Tipikus hibák

• Hiányzó projection. std::ranges::find(hosts, "db-1") a Host és a const char* összehasonlítását kéri, ami nem fordul le; a javítás a harmadik argumentum: &Host::name.
• Rossz comparator-szerződés. A <= vagy a !comp(a,b) && !comp(b,a) mint „egyenlőség” a comparatorban megsérti a strict weak orderinget; a sort viselkedése ilyenkor nem definiált.
• Stabilitás feltételezése. A sort nem stabil; holtversenynél a sorrend nem garantált.
• common_range feltételezése. A r.begin() == r.end() alak nem fordul le, ha az iterator és a sentinel típusa eltér; ilyenkor std::ranges::begin(r) == std::ranges::end(r) vagy explicit subrange/iteratorpár szükséges.
• sized_range feltételezése. ranges::size(r) nem létezik nem-sized range-re; a hossz ranges::distance-szel lineáris.
• Temporális range iteratorának megtartása. A dangling jelzés figyelmen kívül hagyása vagy típusának auto-val való elrejtése élettartam-hibához vezet.

30.3.10 Feladatok

1. feladat (magyarázó). Adott:

auto it = std::ranges::max_element(std::vector<int>{3, 1, 2}, std::less{}, std::negate{});

Mi az it típusa, miért nem használható, és mit jelent szemantikailag a std::negate{} projection?

2. feladat (kódolás). Írj függvénysablont, amely egy const hostlistából visszaadja a legnagyobb latenciájú n hostra mutató pointert, a hostokat nem másolva, projectional paraméterezve. Készíts hozzá egy ellenőrzési feltételt is.

3. feladat (diagnosztika). Az alábbi két sor közül az első nem fordul le, a második lefordul, de az eredmény használhatatlan. Magyarázd meg mindkettőt, és javítsd ki.

auto a = std::ranges::find(hosts, "db-1");
auto b = std::ranges::find(std::vector<Host>{{"db-1", 5432, 7}}, "db-1", &Host::name);

30.3.11 Megoldások

1. megoldás. Az it típusa std::ranges::dangling, mert a range egy temporális std::vector<int>, amely nem borrowed_range, így a visszatérési típus borrowed_iterator_t<R> = dangling. A dangling nem dereferálható, tehát a *it nem fordul le – ez a szándékolt védelem. Szemantikailag a std::negate{} projection a -x értéket adja, a max_element pedig ezen a vetített értéken maximalizál, azaz a legkisebb x-et találja meg. Ez nem fordítási hiba, hanem logikai hiba: a projection megváltoztatta a keresés irányát. Ellenőrzési feltétel: a program csak akkor helyes, ha az it élettartama biztosított (nevesített konténer) és a projection szándéka egyezik a maximum/minimum irányával.

2. megoldás. A lényeg, hogy a range const marad, a kimenet pointereket tartalmaz, a projection pedig a hívótól jön:

#include <algorithm>
#include <functional>
#include <iterator>
#include <ranges>
#include <type_traits>
#include <vector>

template <class R, class Proj = std::identity>
    requires std::ranges::random_access_range<const R>
std::vector<const std::ranges::range_value_t<const R>*>
top_by(const R& r, std::size_t n, Proj proj = {}) {
    using T = std::ranges::range_value_t<const R>;
    std::vector<const T*> ptrs;
    ptrs.reserve(std::ranges::size(r));
    for (const T& x : r) {
        ptrs.push_back(&x);
    }
    n = std::min(n, ptrs.size());
    std::ranges::partial_sort(ptrs, ptrs.begin() + static_cast<std::ptrdiff_t>(n),
                              std::greater{}, proj);
    ptrs.resize(n);
    return ptrs;
}

A member pointer projection pointerre is alkalmazható (std::invoke(&Host::latency_ms, ptr)), ezért a top_by(hosts, 2, &Host::latency_ms) hívás a két legnagyobb latenciájú hostra mutató pointert adja. Indoklás: a partial_sort csak az első n elemet rendezi, így a költség $O(m\log n)$ a teljes rendezés $O(m\log m)$ helyett; a reserve elkerüli az újraallokációt, a pointerek pedig nem tulajdonolnak, ezért a bemenet élettartama a hívó felelőssége. A partial_sort nem stabil; ha a holtversenyes sorrend is számít, stable_sort vagy összetett kulcsú projection kell. Ellenőrzési feltétel: top_by(hosts, 2, &Host::latency_ms)[0]->latency_ms a legnagyobb latencia, a visszaadott vektor hossza min(n, hosts.size()), és semmilyen pointer nem mutat a bemeneti vektortól eltérő tárolóra.

3. megoldás. Az első sor azért nem fordul le, mert a find a Host értéket hasonlítja a const char*-hoz, amire nincs érvényes operator==; a projection hiányzik. A javítás: std::ranges::find(hosts, std::string_view{"db-1"}, &Host::name). A második sor lefordul, de a range egy temporális vektor, ezért a visszatérési típus std::ranges::dangling; az eredmény nem használható iterator. Javítás: nevezzük el a konténert (std::vector<Host> tmp{...}; auto b = std::ranges::find(tmp, ...);), vagy használjunk eleve borrowed range-et. Ellenőrzési feltétel: a javított kód forduljon -Wall -Wextra -pedantic mellett, és a keresés eredménye dereferálható legyen.

30.3.12 Összefoglaló

A ranges algoritmus range-et vár, a projectiont std::invoke szabályai szerint alkalmazza, és az eredmény borrowed_iterator_t, illetve borrowed_subrange_t – nem-borrowed temporális esetén dangling. A begin/end customization pont egységesen kezeli a tag- és nem-tag függvényeket, és törölt rvalue overloaddal fogja meg a legdurvább élettartam-hibát. Az iterator és a sentinel típusa eltérhet; ezt a common_range, a sized_range, a contiguous_range és a borrowed_range képességek egymástól függetlenül írják le. A <algorithm> ranges lefedettsége C++20-ban teljes, a <numeric>-é nem; a C++23-as kiegészítéseket mindig jelölni és implementáció szerint ellenőrizni kell.