42.2 Kombináló view-k: zip, adjacent, enumerate, cartesian_product

A naplóelemző pipeline eddig egyetlen forráson dolgozott: szűrtünk, transzformáltunk, majd anyaggá alakítottuk az eredményt. A valós diagnosztikában viszont ritkán van csak egy sorozatunk: egyszerre kell egy időbélyeg-listát és egy késleltetés-listát összepárosítani, egy sorozat szomszédos elemeit összevetni, a rekordokhoz sorszámot rendelni, vagy éppen minden rekordot minden rekorddal összemérni. A C++23 kombináló view-jai (views::zip, views::zip_transform, views::adjacent, views::enumerate, views::cartesian_product) pontosan ezt teszik lehetővé allokáció nélkül. A nehézség azonban nem az algoritmusban van, hanem abban, hogy mi a dereferálás típusa, és hogy meddig él az, amire a nézet mutat. Ez a rész ezt a két kérdést járja körül; a C++20-as ranges-alapokat (fél-nyílt tartomány, sentinel, projection, lazy pipeline) ismertnek tekinti, és csak a kombinálás új szerződéseit bontja ki.

Az élettartam-kérdéshez felidézzük a korábbi borrowolt range-szabályt: egy R range akkor borrowed range, ha R lvalue-referencia típusú, vagy enable_borrowed_range<remove_cvref_t<R>> igaz. Ennek jelentősége itt konkrét: a kombinált view majdnem soha nem borrowed, ezért ideiglenesből előállított kombinált nézetből kimentett iterátor tipikusan dangling. A tuple-protokollt (miért működik a strukturált kötés, mit ad a std::get) a tuple-részből vesszük adottnak, az anyaggá alakítást pedig a ranges::to-ről szóló részre hagyjuk.

42.2.1 A kombináló view-k közös szerződése: mit ad a dereferálás?

Pontos definícióval kezdünk. Legyenek $R_1,\dots,R_n$ range-ek. A views::zip egy olyan zip_view-ot ad, amelyre

$$\text{reference} = \texttt{tuple<range\_reference\_t<}R_1\texttt{>}, \dots, \texttt{range\_reference\_t<}R_n\texttt{>}>,$$ $$\text{value\_type} = \texttt{tuple<range\_value\_t<}R_1\texttt{>}, \dots, \texttt{range\_value\_t<}R_n\texttt{>}>.$$

Feltétel: minden $R_i$ teljesítse az input_range követelményt. A zip_view csak akkor common_range, ha minden forrás az, csak akkor sized_range, ha minden forrás az, és csak akkor random_access_range, ha minden forrás az és sized. A bejárás a legrövidebb forrás végénél megáll; a hossz nem összeg, hanem minimum.

A lényegi megállapítás: a dereferálás eredménye nem tuple&, hanem egy prvalue tuple, amely referencia-tagokat tartalmaz. Ez az úgynevezett proxy referencia. Ha a forrás int&-et ad, a zip dereferálása std::tuple<int&, double&>, és ezen a tuple-ön keresztül írva az eredeti elemek módosulnak, mert a tuple nem az értékeket, hanem a hivatkozásokat tárolja.

Két következményt érdemes azonnal rögzíteni. Egyrészt auto& x = *it; nem fordul le, mert a *it prvalue; auto&& vagy érték szerinti kötés kell. Másrészt ha a forrás olyan range, amelynek a range_reference_t-je érték (például egy transform, amely std::string-et ad vissza), akkor a tuple valódi értéket tárol: a módosítás elveszik, és a másolás költsége csendben megjelenik. Ez a leggyakoribb szemantikai hiba a kombinált pipeline-okban.

42.2.2 zip és zip_transform

A views::zip elemenként egy tuple-t állít elő, és a rövidebb tartománynál megáll. Két párhuzamos vektor összefűzése így nem igényel indexelést:

#include <ranges>
#include <string>
#include <vector>
#include <iostream>

int main() {
    std::vector<std::string> keys{"alma", "korte", "szilva"};
    std::vector<int> vals{3, 5, 7};

    for (auto&& [k, v] : std::views::zip(keys, vals))
        v *= 10;                       // a vals elemeit módosítja

    for (auto&& [k, v] : std::views::zip(keys, vals))
        std::cout << k << '=' << v << '\n';
}

Itt v típusa int& (pontosabban a tuple int& tagjára kötött név), ezért a v *= 10 a vals-ba ír. Ha a ciklusfejet auto [k, v]-re írnánk, a viselkedés referenciatagok esetén változatlan maradna, de értéktagok esetén csendben másolnánk – ezért a auto&& a biztonságos alapminta.

A views::zip_transform(f, rs...) ugyanazt a párosítást végzi, de nem tuple-t ad, hanem f(elemek...) eredményét, tehát prvalue-t. Ez írásra nem alkalmas, viszont kifejezetten kellemes számított értékekhez:

for (int s : std::views::zip_transform(std::plus<>{},
                                       std::views::all(vals),
                                       std::views::all(vals)))
    std::cout << s << '\n';            // 60, 100, 140

Mivel a zip_transform eredménye érték, a lánc tovább nem írható, de nem is dangle: nincs mögötte három hivatkozás, aminek élnie kellene. Költsége elemenként egy függvényhívás, amit a fordító gyakran beinlinol; allokáció nincs.

42.2.3 adjacent, adjacent_transform és pairwise

A views::adjacent<N> egyetlen range-ből állít elő $N$-es csoportokat: a $i$-edik elem az $r[i], r[i+1], \dots, r[i+N-1]$ elemekre hivatkozó tuple, és a nézet hossza

$$\max\bigl(0,\; \text{size}(r) - (N-1)\bigr).$$

Az $N$ nem-típusparaméter, N >= 1; az alapértelmezés 2, és a views::pairwise pontosan az adjacent<2> rövidítése. A forrásnak legalább forward_range-nek kell lennie, hiszen a nézetnek $N-1$ elemmel előre kell tudnia mutatni. Üres vagy egyelemű bemenetnél a nézet üres lesz – ez nem hiba, hanem a fenti képlet nulla értéke.

std::vector<int> ms{12, 40, 7, 90};
for (auto&& [prev, cur] : ms | std::views::pairwise)
    std::cout << (cur - prev) << ' ';   // 28 -33 83

A adjacent_transform<N>(f, r) ugyanezt teszi, de $f$-et alkalmazza a csoportra, tehát értéket ad vissza. Itt érdemes tudatosítani: a pairwise tuple-jének mindkét tagja ugyanannak a range-nek a hivatkozása, ezért a két név közül bármelyiken át írva ugyanazt a tárolót módosítjuk – ez néha meglepő, ha az ember két független másolatot feltételez.

42.2.4 enumerate és az index típusa

A views::enumerate(r) eleme tuple<range_difference_t<R>, range_reference_t<R>>, azaz az index a range difference típusa, jellemzően előjeles egész (std::ptrdiff_t), nem std::size_t. Ez tudatos döntés: a ranges könyvtárban a távolságok előjelesek. A gyakorlati következmény, hogy a -Wsign-compare figyelmeztetés megjelenhet, ha az indexet size()-hez hasonlítjuk; ilyenkor explicit konverzióval jelezzük a szándékot.

for (auto&& [i, rec] : std::views::enumerate(ms)) {
    if (rec > 50)
        std::cout << static_cast<long long>(i) << ": " << rec << '\n';
}

Az index nullától indul és növekszik. Mivel az első tag érték a tuple-ben, az i módosítása csak a lokális másolatot érinti, a bejárásra nincs hatás – ezért írásra soha ne használjuk. A második tag viszont referencia, így a rec-en át írva a forrás módosul.

42.2.5 cartesian_product: méret és költség

A views::cartesian_product(rs...) az összes kombinációt állítja elő; eleme tuple a résztvevő range-ek aktuális elemeire hivatkozó tagokkal. A méret a tényezők szorzata:

$$\text{size} = \prod_{i=1}^{n} \text{size}(R_i), \qquad \text{üres forrás esetén } 0.$$

A bejárási rend a beágyazott ciklusokhoz hasonló: a jobb szélső tartomány lép leggyorsabban – ezt érdemes egy rövid próbával ellenőrizni a saját implementációnkon, mert erre épülő kódot írunk. A lépésenkénti költség $O(1)$, allokáció nincs, viszont az iterátor minden forrásra tárol egy pozíciót, tehát a nézet objektummérete $n$-nel nő. A nagy szorzatra figyelmeztetni kell: $10^4 \times 10^4$ már $10^8$ elem, amit egy naiv szűrőfeltétellel való bejárás megfizet. A helyes minta: előbb szűrj, aztán kombinálj, és ha a szorzat nagyságrendileg nem indokolható, használj index- vagy hash-alapú megoldást.

42.2.6 Borrowed range, rvalue forrás és dangling

Négy esetet kell élesen megkülönböztetni.

Ha a views::all argumentuma lvalue konténer, ref_view keletkezik: borrowed, de a konténer élettartamához kötött. Ha rvalue konténer, owning_view keletkezik, amely elmozgatja a konténert, és ezzel biztonságossá teszi a nézetet – ezért helyes a views::zip(std::vector{1,2}, std::vector{3,4}) forma. Ha viszont az argumentum már view, akkor csak másolat készül: a nézet nem birtokolja a mögöttes adatot, és ha az megszűnik, dangle. Végül az ideiglenes zip_view-ból kimentett iterátor mindig veszélyes, mert a zip_view nem borrowed range.

// HIBA (tanítási példa): a helyi string megszűnik, a nézet dangling
auto make_bad() {
    std::string s = "alma";
    return std::views::zip(s, std::views::single(1)); // ref_view<string>
}

// HELYES: az adatot adjuk vissza, a nézetet a hívó építse
std::vector<std::string> make_ok() { return {"alma"}; }

A második élettartam-szabály az invalidáció: a kombinált nézet semmit nem cache-el, ezért minden olyan művelet, amely a forrás iterátorát érvényteleníti (push_back, erase, std::string módosítása), a kombinált iterátort is érvényteleníti. Egy zip iterátor „ereje” mindig a leggyengébb forrásáé.

42.2.7 kidolgozott példa: naplórekordok négy nézettel

A példa egy koherens pipeline: a rekordok level + ms mezőt tartalmaznak, a level egy string_view, amely a hívó lines vektorára mutat – ezt a tulajdonviszonyt kommentben rögzítjük.

// logzip.cpp — C++23; a tamogatast feature-test makroval ellenorizd
#include <ranges>
#include <string>
#include <string_view>
#include <vector>
#include <iostream>
#include <charconv>

struct rec { std::string_view level; int ms; };  // nem tulajdonol: lines elemeire mutat

std::vector<rec> parse(const std::vector<std::string>& lines) {
    std::vector<rec> out;
    for (auto&& line : lines) {
        auto sp = line.find(' ');
        if (sp == std::string::npos) continue;
        int ms = 0;
        auto [p, ec] = std::from_chars(line.data() + sp + 1,
                                       line.data() + line.size(), ms);
        if (ec != std::errc{}) continue;
        out.push_back({std::string_view{line}.substr(0, sp), ms});
    }
    return out;
}

int main() {
    std::vector<std::string> lines{"INFO 12", "WARN 40", "WARN 7", "ERROR 90"};
    auto recs = parse(lines);                      // recs elemei lines-ra mutatnak

    for (auto&& [i, r] : std::views::enumerate(recs))
        std::cout << i << ' ' << r.level << ' ' << r.ms << '\n';

    for (auto&& [a, b] : recs | std::views::pairwise)
        std::cout << "delta " << (b.ms - a.ms) << '\n';

    std::size_t worse = 0;
    for (auto&& [a, b] : std::views::cartesian_product(recs, recs))
        if (a.level == b.level && a.ms < b.ms) ++worse;
    std::cout << "worse pairs: " << worse << '\n';

    for (int s : std::views::zip_transform(std::plus<>{},
             recs | std::views::transform(&rec::ms),
             recs | std::views::transform(&rec::ms)))
        std::cout << "2x " << s << '\n';
}

Build (a fordítás eredményét nem állítom mértnek; a tanuló laborjában ellenőrizendő):

g++ -std=c++23 -O2 -Wall -Wextra -o logzip logzip.cpp
# vagy: clang++ -std=c++23 -O2 -Wall -Wextra -o logzip logzip.cpp

Támogatás-ellenőrzés: a zip/adjacent családhoz __cpp_lib_ranges_zip, az enumerate-hez __cpp_lib_ranges_enumerate, a cartesian_product-hoz __cpp_lib_ranges_cartesian_product makrót keress a <version> headerben; ha bármelyik hiányzik, a nézet nem használható, és a C++20-as fallback (indexszel való bejárás, std::forward_as_tuple-tel) jön szóba.

42.2.8 Tipikus hibák és javításuk

A auto& x = *it; nem köt prvalue-ra; auto&& kell. Az enumerate indexe előjeles, ezért size()-hez hasonlítva figyelmeztet, és a static_cast hiánya -Werror mellett fordítási hibát ad. A függvényből visszaadott, lokális konténerre épülő zip dangling; ilyenkor az adatot kell visszaadni, nem a nézetet. A transform által értékkel visszaadott elemeket a zip csendben lemásolja; ha írni akarunk, a transformnak referenciát kell adnia. Végül a cartesian_product mérete szorzódik: nagy forrásoknál előbb szűrjünk.

42.2.9 Összefoglaló

A zip/zip_transform/adjacent/enumerate/cartesian_product mind ugyanarra a szerződésre épül: a dereferálás tuple, amelynek tagjai referenciák vagy értékek aszerint, hogy a forrás mit ad. A proxy referencián keresztül írni csak akkor lehet, ha a forrás valódi referenciát ad; az élettartam pedig soha nem hosszabb, mint a legrövidebb forrásé, és a nézet nem borrowed, ha ideiglenesből készült. Az enumerate indexe difference típus, a cartesian_product mérete szorzat.

42.2.10 Feladatok

1. feladat (elemzés). Add meg std::views::zip(v, w) reference és value_type típusát, ahol v std::vector<int>, w std::vector<double>. Írj static_assert-et, amely ezt ellenőrzi, és mondd meg, mi történik, ha a w egy transform nézet, amely std::string-et ad vissza értékként.

2. feladat (kódolás). Számítsd ki egy std::vector<int> szomszédos különbségeit views::adjacent<2>-vel, és írd ki azokat a helyeket, ahol a különbség negatív. Üres és egyelemű bemenetre is legyen helyes.

3. feladat (diagnosztika). Az alábbi függvény fordítódik, de a hívó oldalon dangle-t okoz. Találd meg az okot, és javítsd két különböző módon.

auto head(const std::vector<std::string>& v) {
    return std::views::zip(v, std::views::enumerate(v));
}

4. feladat (költség). Két n = 10000-es vektor minden párosításában keresed azokat a párokat, ahol az első érték kisebb a másodiknál. Becsüld meg a cartesian_product lépésszámát, és adj egy olyan megoldást, amely előszűréssel csökkenti a jelölteket.

42.2.11 Megoldások

1. megoldás. A zip referenciája std::tuple<int&, double&>, értéktípusa std::tuple<int, double>. Az ellenőrzés:

using Z = decltype(std::views::zip(std::declval<std::vector<int>&>(),
                                   std::declval<std::vector<double>&>()));
static_assert(std::is_same_v<std::ranges::range_reference_t<Z>,
                             std::tuple<int&, double&>>);
static_assert(std::is_same_v<std::ranges::range_value_t<Z>,
                             std::tuple<int, double>>);

Ha a második forrás transform, amely std::string-et ad vissza értékként, akkor range_reference_t std::tuple<int&, std::string>, tehát a tuple valódi std::string-et tárol: a zip elemenként másol, és a string-en át írni nincs hatás. Ellenőrzési feltétel: a static_assert a tuple<int&, std::string> típusra teljesül, és a fordító nem jelez hibát a zip létrehozásakor.

2. megoldás.

std::vector<int> v{5, 3, 9};
for (auto&& [i, d] : std::views::enumerate(v | std::views::adjacent<2>
        | std::views::transform([](auto t) { return std::get<1>(t) - std::get<0>(t); }))) {
    if (d < 0) std::cout << i << " csokkenes: " << d << '\n';
}

Egyszerűbb, ha rögtön a tuple-t kötjük ki:

for (auto&& [a, b] : v | std::views::adjacent<2>)
    if (b - a < 0) std::cout << (b - a) << '\n';

Üres vagy egyelemű v esetén az adjacent<2> üres, a ciklusmag nem fut le, és nincs UB. Ellenőrzési feltétel: {5,3,9}-re egy kiírás (-2), {}-re és {7}-re nulla kiírás.

3. megoldás. A v itt lvalue referencia, de a std::views::enumerate(v) ideiglenes nézet, és a zip referenciatagja erre az ideiglenesre mutat. A zip_view a bejárás során dereferálja az enumerate iterátorát, amely viszont egy olyan objektumra épül, amely a teljes kifejezés végén megszűnik: dangle. Első javítás: az adatot adjuk vissza, és a hívó építse a nézetet:

const std::vector<std::string>& head(const std::vector<std::string>& v) { return v; }

Második javítás: ha a sorszámozott nézetre tényleg szükség van, azt a hívó oldalon, lokálisan hozzuk létre, a v élettartamán belül:

for (auto&& [s, ip] : std::views::zip(v, std::views::enumerate(v))) { /* ... */ }

Ellenőrzési feltétel: a javított kód nem ad vissza nézetet lokálisra, és a -Wdangling típusú figyelmeztetés (ha az adott fordító ad ilyet) eltűnik; a viselkedés független attól, hogy a hívó milyen sorrendben használja a visszakapott objektumot.

4. megoldás. A cartesian_product lépésszáma $n^2 = 10^8$, ami már önmagában is érezhető költség, függetlenül attól, hogy a feltétel gyors. Előszűrés: rendezzük a második vektort, és minden $x$-re bináris kereséssel számoljuk meg a nála nagyobbakat – ez $O(n \log n)$; vagy ha cartesian_product-ot használunk, előbb szűrjük a második vektort egy küszöbre, és csak a jelöltekkel kombináljunk. A kisebb költségű megoldás indoklása: a szorzatméret multiplikatív, ezért a jelöltszám csökkentése négyzetesen megtérül. Ellenőrzési feltétel: a két megoldás ugyanazt a darabszámot adja kis ($n = 100$) bemeneten, és a lépésszám a másodikban nagyságrendekkel kisebb.