42.4 C++23 range-algoritmusok és ranges-labor

A C++20 ranges alapjai után a C++23 több olyan algoritmust tett a std::ranges névtérbe, amelyeket addig csak kézzel, ciklussal vagy a régi <numeric>/<algorithm> függvényekkel lehetett megoldani. Ez a rész ezeket a szerződés oldaláról tárgyalja: mi a pontos visszatérési típus, milyen range-kategória kell, mi történik üres bemenetnél, és hol tér el a viselkedés a megszokott std::accumulate-től. A záró labor egy naplóelemző pipeline-t épít fel kétszer, C++20-ban és C++23-ban, hogy a különbség ne csak stílusbeli legyen, hanem mérhető és ellenőrizhető.

A rész alapprofilja ISO C++23, -std=c++23. A konkrét fordító- és könyvtárverzió támogatását itt nem tekintjük ellenőrzöttnek: minden új képességhez feature-test makrót és compile probe-ot adunk, és ahol szükséges, fallbacket jelzünk. A C++20-ban már bevezetett ranges-alapokat (projection, sentinel, view pipeline, borrowed range) nem tanítjuk újra; ezekre a Ranges algoritmusok, projection és sentinel (30.3) és Szeletelő és átalakító view-k: chunk, slide, chunk_by, stride, join_with (42.3) részekre hivatkozunk.

42.4.1 A fold család: bal- és jobbasszociatív összegzés

A std::ranges::fold_left, fold_right, fold_left_first és fold_right_first a P2322 javaslat nyomán került a szabványba. Közös jellemzőjük, hogy determinisztikus sorrendben dolgozzák fel a range elemeit, ellentétben a C++17-es std::reduce-dzsel, amelynek a sorrendje nem meghatározott, és amely ezért nem is használható nem asszociatív művelettel. A foldok mindig balról jobbra, illetve jobbról balra haladnak, így a művelet asszociativitása nem követelmény.

A fold_left lényegében a ranges-esített accumulate. A deklarációja leegyszerűsítve:

template <std::input_range R, class T, class F>
  constexpr auto fold_left(R&& r, T init, F f) -> std::decay_t<T>;

A visszatérési típus az init típusa (decay_t<T>), nem a range értéktípusa. Ez a legfontosabb szerződésbeli pont: ha init int, akkor az akkumulátor végig int marad, akkor is, ha a range elemei long long-ok, és minden részeredmény int-té konvertálódik. A f hívása f(acc, *it) alakú, és a követelmény, hogy a visszatérési értéke konvertálható legyen T-vé. A fold_right ugyanezt jobbról teszi, de bidirectional_range-et igényel, mert hátulról kell indulnia, és a művelet argumentumsorrendje megfordul: f(*it, acc).

A fold_left_first kezdőérték nélkül dolgozik: az első elemet használja kezdőértékként, ezért üres range esetén std::nullopt-ot ad vissza, nem hibát. A visszatérési típus std::optional<U>, ahol U = std::decay_t<std::ranges::range_value_t<R>>. Itt van a gyakori csapda: a visszatérési típus az első elem típusából származik, nem abból, amit a művelet visszaad. Ha az elemek int-ek, de a művelet double-t adna, az eredmény mégis optional<int> lesz, és a törtrész elveszik. A fold_right_last ugyanez jobbról, szintén bidirectional_range-en.

A std::accumulate és a fold_left viszonya: az accumulate C++98 óta létezik, nincs projectionje, nincs sentinel-támogatása, és nem constexpr-követelményű a régi szignatúrában (C++20 óta constexpr). A fold_left ugyanazt a balról jobbra haladó szemantikát adja, de ranges-interfésszel, projectionnel és constexpr-rel. A fold_right viszont olyan műveletet tesz lehetővé, amelynek az argumentumsorrendje számít, például nem kommutatív összefűzést.

Nézzünk egy kidolgozott példát, amely bemutatja az init típusának szerepét:

#include <algorithm>
#include <cassert>
#include <functional>
#include <vector>

std::vector<long long> v{1'000'000'000LL, 2'000'000'000LL, 3'000'000'000LL};

// Helyes: az init long long, az akkumulátor nem csordul túl.
long long ok = std::ranges::fold_left(v, 0LL, std::plus<>{});

// Hibás szándék: az init int, az akkumulátor int marad.
// A részeredmények konvertálódnak, és a viselkedés túlcsordulásnál
// nem definiált (a long long -> int konverzió implementációfüggő,
// illetve a signed túlcsordulás UB).
long long bad = std::ranges::fold_left(v, 0, std::plus<>{});

A fold_left_first helyes használata:

#include <optional>
#include <ranges>

std::optional<long long> first_sum(const std::vector<long long>& v) {
    return std::ranges::fold_left_first(v, std::plus<>{});
}

void use(const std::vector<long long>& v) {
    if (auto s = first_sum(v)) {
        // *s csak akkor érvényes, ha a range nem volt üres.
    }
}

A fold_left_first az első elem típusát használja, ezért a v elemeinek long long-nak kell lenniük; ha int vektorral hívjuk, az eredmény optional<int> lesz, és a nagy összeg túlcsordulhat. Ez nem a fold hibája, hanem a típusválasztásé.

42.4.2 Kereső és összehasonlító algoritmusok

A C++23 három, egymáshoz szorosan kapcsolódó csoportot adott a <algorithm>-hoz: a contains/contains_subrange és a starts_with/ends_with predikátumokat, a find_last családot, valamint a <numeric>-ba tartozó ranges::iota-t és a shift_left/shift_right-ot.

A std::ranges::contains(r, value, proj) bool-t ad, és rövidzárral működik: az első egyezésnél megáll. Ez a legfontosabb különbség a find(...) != end() mintához képest, ahol a fordító gyakran nem tudja kihasználni a korai kilépést, ha az iterátort tovább használjuk. A contains_subrange(r, sub, pred, proj1, proj2) azt vizsgálja, hogy a sub részhalmazként előfordul-e az r-ben; a starts_with és az ends_with pedig a range elejét, illetve végét hasonlítja össze a megadott prefixszel, illetve szufixszel. Utóbbiaknál a két range elemeinek összehasonlíthatónak kell lenniük, de nem kell azonos típusúnak lenniük — például std::string és std::string_view karakterei összehasonlíthatók.

A find_last(r, value, proj) az utolsó előfordulást keresi, és std::ranges::subrange-et ad vissza, amelynek begin()-je a találatra mutat, end()-je pedig a range végére. Ha nincs találat, a subrange üres (begin() == end()), de a subrange-nek nincs operator bool-ja, ezért a helyes ellenőrzés if (!result.empty()), nem if (result). A find_last_if és a find_last_if_not predikátumos változatok; a teljes lista és a pontos követelmények a szabványban ellenőrizendők.

A std::ranges::iota(r, value) a <numeric> std::iota ranges-esített változata: a range-et növekvő értékekkel tölti fel. A std::ranges::shift_left(r, n) és a shift_right(r, n) a [first, last) tartományon belül eltolja az elemeket, és visszatér az új last iterátorral. A visszatérési értéket kötelező felhasználni: a shift_left után az [new_last, last) tartomány elemei nem érvényesek, és ha a hívó a régi last-ot használja, szemét adatokhoz jut. A shift_left az n >= size esetben üres tartományt ad vissza.

#include <algorithm>
#include <array>
#include <cassert>
#include <string>
#include <vector>

void search_examples(const std::vector<std::string>& lines) {
    // Az első FATAL előfordulásig nem megy tovább.
    bool has_fatal = std::ranges::contains(lines, std::string{"FATAL"});

    // Prefix- és szufixvizsgálat; a string_view elemei char-ok,
    // ezért a string és a string_view összehasonlítható.
    bool any_error = std::ranges::any_of(lines, [](const std::string& s) {
        return std::ranges::starts_with(s, std::string_view{"ERROR"});
    });
    bool any_trunc = std::ranges::any_of(lines, [](const std::string& s) {
        return std::ranges::ends_with(s, std::string_view{"..."});
    });
}

void shift_example(std::vector<int>& v, std::size_t n) {
    auto new_last = std::ranges::shift_left(v.begin(), v.end(), n);
    v.erase(new_last, v.end());   // a farok érvénytelen, törölni kell
}

A contains_subrange használatakor érdemes figyelni arra, hogy a részhalmazt ne allokáljuk minden hívásnál; egy std::array vagy egy std::string_view alkalmasabb lehet, ha az elemek összehasonlíthatók.

42.4.3 Labor: naplóelemző pipeline C++20 és C++23 változatban

A labor bemenete egy std::vector<std::string>, amelynek elemei "LEVEL ts bytes" formátumúak, ahol a LEVEL az ERROR, WARN vagy INFO valamelyike. A feladat: számoljuk ki az ERROR szintű sorok byte-összegét, döntsük el, hogy van-e adott szint, és keressük meg az utolsó ERROR bejegyzést. A C++20-as változat std::accumulate-et, std::find_if-et és reverse iterátort használ; a C++23-as változat views::filter/views::transform pipeline-t, ranges::fold_left-et, ranges::contains-t és ranges::find_last-ot.

A labor három fájlból áll. A közös loglab.hpp tartalmazza a bemeneti modellt (Entry, parse) és a helyességi kaput, amelyet mindkét változat main függvénye lefuttat: üres bemenet, nincs ERROR, csupa ERROR, egyetlen sor és vegyes bemenet. A kapu biztosítja, hogy a két implementáció ugyanazt az eredményt adja.

// loglab.hpp — közös bemeneti modell és helyességi kapu mindkét változathoz
#pragma once
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <sstream>
#include <string>
#include <vector>

struct Entry {
    std::string level;
    std::int64_t ts;
    std::int64_t bytes;
};

// "LEVEL ts bytes" sorok; a hibás sort kihagyja.
inline std::vector<Entry> parse(const std::vector<std::string>& lines) {
    std::vector<Entry> out;
    for (const std::string& line : lines) {
        std::istringstream in(line);
        Entry e;
        if (in >> e.level >> e.ts >> e.bytes) out.push_back(e);
    }
    return out;
}

#define CHECK(condition) do {                                      \
    if (!(condition)) {                                            \
        std::fprintf(stderr, "CHECK failed at line %d\n", __LINE__); \
        std::exit(EXIT_FAILURE);                                   \
    }                                                              \
} while (0)

// A helyességi kapu: a határeseteken mindkét változatnak ugyanezt kell adnia.
template <class ErrorBytes, class HasLevel, class LastErrorTs>
void check_cases(ErrorBytes error_bytes, HasLevel has_level,
                 LastErrorTs last_error_ts) {
    const std::vector<Entry> empty;
    CHECK(error_bytes(empty) == 0 && !has_level(empty, "ERROR"));
    CHECK(last_error_ts(empty) == -1);

    const auto none = parse({"INFO 1 10", "WARN 2 20"});
    CHECK(error_bytes(none) == 0 && has_level(none, "WARN"));
    CHECK(last_error_ts(none) == -1);

    const auto all = parse({"ERROR 1 5", "ERROR 2 7"});
    CHECK(error_bytes(all) == 12 && last_error_ts(all) == 2);

    const auto one = parse({"ERROR 9 3"});
    CHECK(error_bytes(one) == 3 && last_error_ts(one) == 9);

    const auto mixed = parse({"ERROR 1 5", "INFO 2 1", "ERROR 3 4", "WARN 4 2"});
    CHECK(error_bytes(mixed) == 9 && last_error_ts(mixed) == 3);
    CHECK(!has_level(mixed, "DEBUG"));
}

A C++23-as változat:

// loglab23.cpp — C++23
#include "loglab.hpp"
#include <algorithm>
#include <functional>
#include <ranges>

std::int64_t error_bytes(const std::vector<Entry>& es) {
    auto errs = es
        | std::views::filter([](const Entry& e) { return e.level == "ERROR"; })
        | std::views::transform([](const Entry& e) { return e.bytes; });
    return std::ranges::fold_left(errs, std::int64_t{0}, std::plus<>{});
}

bool has_level(const std::vector<Entry>& es, const std::string& lv) {
    return std::ranges::contains(es, lv, &Entry::level);
}

std::ranges::subrange<std::vector<Entry>::const_iterator>
last_error(const std::vector<Entry>& es) {
    static const std::string kErr = "ERROR";
    return std::ranges::find_last(es, kErr, &Entry::level);
}

int main() {
    check_cases(error_bytes, has_level, [](const std::vector<Entry>& es) {
        auto r = last_error(es);
        return r.empty() ? std::int64_t{-1} : r.begin()->ts;
    });
    std::puts("loglab23: ok");
}

A C++20-as megfelelő:

// loglab20.cpp — C++20
#include "loglab.hpp"
#include <algorithm>
#include <numeric>

std::int64_t error_bytes(const std::vector<Entry>& es) {
    return std::accumulate(es.begin(), es.end(), std::int64_t{0},
        [](std::int64_t acc, const Entry& e) {
            return e.level == "ERROR" ? acc + e.bytes : acc;
        });
}

bool has_level(const std::vector<Entry>& es, const std::string& lv) {
    return std::find_if(es.begin(), es.end(),
        [&](const Entry& e) { return e.level == lv; }) != es.end();
}

auto last_error(const std::vector<Entry>& es) {
    return std::find_if(es.rbegin(), es.rend(),
        [](const Entry& e) { return e.level == "ERROR"; });
}

int main() {
    check_cases(error_bytes, has_level, [](const std::vector<Entry>& es) {
        auto it = last_error(es);
        return it == es.rend() ? std::int64_t{-1} : it->ts;
    });
    std::puts("loglab20: ok");
}

A build mindkét esetben ugyanazzal a flag-készlettel történik, csak a nyelvi mód tér el:

g++ -std=c++20 -O2 -Wall -Wextra -Wpedantic -o loglab20 loglab20.cpp
g++ -std=c++23 -O2 -Wall -Wextra -Wpedantic -o loglab23 loglab23.cpp
./loglab20
./loglab23
# lab-clang profilban:
clang++ -std=c++23 -O2 -Wall -Wextra -Wpedantic -o loglab23 loglab23.cpp

Buildjegyzőkönyv (lab-gcc profil). Mindkét változat figyelmeztetés nélkül fordult (a C++23-as -std=c++23 módban, a GCC 13.3 libstdc++-ával), és a közös helyességi kapu után loglab20: ok, illetve loglab23: ok kimenettel futott. A Clang-sort nem ellenőriztük.

A feature-test probe:

#include <version>

#if defined(__cpp_lib_ranges_fold) && __cpp_lib_ranges_fold >= 202207L
constexpr bool have_fold = true;
#else
constexpr bool have_fold = false;
#endif

#if defined(__cpp_lib_ranges_contains) && __cpp_lib_ranges_contains >= 202207L
constexpr bool have_contains = true;
#else
constexpr bool have_contains = false;
#endif

A makrók jelenléte nem garantálja a teljes funkcionalitást (a könyvtár implementálhatja a makrót anélkül, hogy minden overload elkészült volna), ezért a labor elején egy compile probe fordítja le a tényleges hívásokat. A szabványtervezet szerinti értékek: __cpp_lib_ranges_fold 202207L, __cpp_lib_ranges_contains 202207L, __cpp_lib_ranges_starts_ends_with 202106L, __cpp_lib_ranges_find_last 202207L, __cpp_lib_ranges_iota 202202L, __cpp_lib_ranges_shift 202207L. Ezek a konkrét libstdc++/libc++ kiadásban ellenőrizendők; ahol hiányoznak, a C++20-as fallback marad.

A benchmark és a helyességi kapuk együtt futnak. A mérés metodikája: azonos bemenet, azonos optimalizálási szint, előmelegítés, legalább néhány ismétlés, és az eredmény mediánja. A helyességi kapu minden esetben az, hogy a két implementáció ugyanazt az értéket adja az összes határesetre: üres bemenet, nincs ERROR, csupa ERROR, egyetlen sor. A mérés eredménye nem része ennek a szövegnek; a tanuló laborjában keletkezik, és target-, fordító- és flagspecifikus.

#include <chrono>

template <class F>
double bench_ms(F&& f, int reps) {
    using clock = std::chrono::steady_clock;
    auto t0 = clock::now();
    for (int i = 0; i < reps; ++i) {
        volatile auto sink = f();   // holt kód kiesés ellen, nem univerzális barrier
        (void)sink;
    }
    auto t1 = clock::now();
    return std::chrono::duration<double, std::milli>(t1 - t0).count() / reps;
}

42.4.4 Gyakori hibák és javításuk

Az első és leggyakoribb hiba a fold_left init típusának elrontása: 0 helyett 0LL, 0.0 helyett 0.0L vagy fordítva. A második a fold_left_first eredményének kezeletlen optional-ja: a *opt üres optionalon nem definiált viselkedés, ezért előbb if (auto v = ...) kell. A harmadik a find_last eredményének bool-ként való használata: a subrange nem konvertálható bool-lá, helyette !r.empty(). A negyedik a shift_left visszatérési értékének eldobása, amitől a vektor vége szemét marad. Az ötödik a contains és a find összecserélése olyan helyen, ahol az iterátorra szükség van: a contains csak a létet adja vissza, pozíciót nem. Végül a benchmarknál a nem használt eredmény miatti holt kód kiesése, illetve a -O0-s mérés összehasonlíthatatlansága.

42.4.5 Összefoglaló

A C++23 ranges-algoritmusok a megszokott műveleteket adják vissza ranges-szerződéssel: a fold_left/fold_right determinisztikus sorrendű összegzés, az init típusa dönt az akkumulátor típusáról; a fold_left_first üres range-re nullopt-ot ad. A contains, contains_subrange, starts_with és ends_with rövidzáró predikátumok, a find_last subrange-et ad, a shift_left/shift_right pedig új last iterátort. A laborban a C++20-as és C++23-as pipeline eredményét kötelező egyeztetni, és csak ezután szabad mérni.

42.4.6 Feladatok

1. Alapvető. Írj egy average_error_ratio függvényt, amely a naplóbejegyzésekből kiszámítja az ERROR byte-ok és az összes byte arányát. Használj ranges::fold_left-et std::int64_t{0} és 0.0 kezdőértékkel. Magyarázd meg, miért kell a két foldnak eltérő kezdőértéket adni.

2. Közepes. Írj egy last_error_before_ts függvényt, amely a find_last_if-fel megkeresi az utolsó olyan bejegyzést, amelynek a timestampje kisebb, mint egy adott limit, és az ERROR szintű. Mi a visszatérési típus, és hogyan kezeled az üres eredményt?

3. Nehéz. Írj egy dedup_in_place függvényt, amely egy rendezett std::vector<int>-ből shift_left-nel távolítja el az ismétlődőket, és add meg a komplexitást, valamint a helyességi kapukat.

4. Diagnosztikai. A laborban a C++23-as változat lassabbnak bizonyul a C++20-asnál. Sorolj fel három lehetséges okot, és mindegyikhez adj egy ellenőrzési lépést.

42.4.7 Megoldások

1. megoldás. Az error_bytes és a total_bytes külön fold; a másodiknak 0.0 az initje, mert az arányt lebegőpontosan akarjuk kiszámítani, és a fold_left visszatérési típusa az init típusa.

double average_error_ratio(const std::vector<Entry>& es) {
    auto bytes = es | std::views::transform([](const Entry& e) { return e.bytes; });
    double total = std::ranges::fold_left(bytes, 0.0, std::plus<>{});
    if (total == 0.0) return 0.0;
    auto errs = es
        | std::views::filter([](const Entry& e) { return e.level == "ERROR"; })
        | std::views::transform([](const Entry& e) { return e.bytes; });
    double err = std::ranges::fold_left(errs, 0.0, std::plus<>{});
    return err / total;
}

Ellenőrzés: üres vektorra 0.0, csupa ERROR-ra 1.0, és az int64_t összegek nem csordulnak túl. Ha a második fold initje 0 lenne, az egész osztás miatt az arány 0 vagy 1 lenne.

2. megoldás. A find_last_if subrange-et ad; a predikátumnak a limit-et is látnia kell, ezért lambdába zárjuk.

auto last_error_before_ts(const std::vector<Entry>& es, std::int64_t limit) {
    return std::ranges::find_last_if(es,
        [limit](const Entry& e) { return e.level == "ERROR" && e.ts < limit; });
}

void use(const std::vector<Entry>& es, std::int64_t limit) {
    auto r = last_error_before_ts(es, limit);
    if (!r.empty()) {
        const Entry& e = *r.begin();
        // e itt érvényes, amíg az es nem módosul.
    }
}

Ellenőrzés: üres bemenetre r.empty(), a limitnél nagyobb timestampű egyetlen ERROR esetén szintén r.empty(), és a visszaadott Entry& addig érvényes, amíg a vektor nem módosul.

3. megoldás. Rendezett vektoron az ismétlődések összefüggő blokkot alkotnak; a shift_left az egyedi prefixet előrehúzza.

void dedup_in_place(std::vector<int>& v) {
    if (v.empty()) return;
    auto last = std::ranges::unique(v).begin();   // C++20 ranges::unique
    auto new_last = std::ranges::shift_left(v.begin(), last, last - v.begin());
    v.erase(new_last, v.end());
}

A unique az egyedi elemeket előre mozgatja, és az új logikai végét adja vissza; a shift_left ezt a prefixet a vektor elejére tolja, majd a farkat töröljük. A komplexitás $O(n)$ lineáris, egyetlen extra tárterület nélkül. Helyességi kapuk: üres vektor, egyelemű vektor, csupa azonos elem, minden elem különböző, és a rendezettség megőrzése.

4. megoldás. (a) A views::filter/views::transform lánc nem feltétlenül olvad össze a fold_left-tel, és a lambda-hívás költsége megjelenhet; ellenőrzés: assembly vagy -fopt-info összehasonlítása. (b) A fold_left std::plus<>-t használ, amely nem feltétlenül vektorizálódik, míg a kézi ciklus igen; ellenőrzés: -O3 -march=native melletti újramérés. (c) A mérés maga hibás: a volatile sink nem elegendő, vagy a bemenet mérete miatt a C++20-as változat a cache-ben marad; ellenőrzés: azonos bemenet, azonos flags, előmelegítés és több ismétlés, valamint az eredmények egyezésének ellenőrzése a mérés előtt.