29.3 Rendezés, keresés és comparator szerződés

Ez az alfejezet arról szól, hogyan lehet egy algoritmust tárolótól függetlenül meghívni, és miért nem elég ehhez a szintaxis ismerete. Egy DevOps-környezetben a legtöbb „rendezés” és „keresés” valójában napló- vagy metrikarekordokon fut: időbélyeggel, kapcsolatazonosítóval, késleltetéssel. Ezeknél a rendezettség nem esztétikai kérdés, hanem előfeltétel, amelyet az algoritmus nem ellenőriz, és amelynek megsértése csendben hibás választ ad. A comparator itt nem kényelmi paraméter, hanem szerződés: az algoritmus pontosan annyit tud, amennyit a comparator kifejez. A rendezési kategóriák (<, <=>, egyenlőség) korábbi tárgyalását itt feltételezzük, ahogy a módosító algoritmusok range-alapú szemléletét is — lásd Egyenlőség, spaceship és rendezési kategóriák (23.4) és Transform, copy, remove és módosító algoritmusok (29.2).

29.3.1 A comparator mint szerződés: strict weak ordering

Az std::sort, std::lower_bound és társai Compare paramétere akkor érvényes, ha strict weak ordering (szigorú gyenge rendezés). Négy feltétel:

1. irreflexivitás: comp(x, x) hamis;
2. aszimmetria: ha comp(a, b) igaz, akkor comp(b, a) hamis;
3. tranzitivitás: comp(a, b) && comp(b, c) esetén comp(a, c);
4. az összehasonlíthatatlanság tranzitivitása: ha a és b, valamint b és c összehasonlíthatatlan, akkor a és c is az.

Az összehasonlíthatatlanság külön nevet kap: a és b ekvivalens (jelölés: $a \sim b$), ha $$\neg\,\mathrm{comp}(a,b) \;\wedge\; \neg\,\mathrm{comp}(b,a).$$ Ez nem egyenlőség. Két kapcsolatrekord ekvivalens egy időbélyeg-comparator szerint akkor is, ha a conn_id-juk eltér — egyszerűen csak ugyanabban a milliszekundumban zárultak. A standard könyvtár minden „egyenlőség” fogalma Comparator esetén ekvivalenciát jelent, nem operator==-t; ezért a keresési eredmények értelmezésénél mindig a comparator a mérvadó.

Egy rendezett tartomány definíciója is kizárólag a comparatorra épül: a [first, last) tartomány comp szerint rendezett, ha minden i < j indexre comp(*j, *i) hamis. Ebből az is következik, hogy a fél-nyílt tartomány last eleme nem dereferálható, és hogy a „rendezett” állapot önmagában nem mond semmit az ekvivalens elemek egymáshoz viszonyított sorrendjéről.

A szerződésszegés következménye nem definiált viselkedés: a könyvtár nem köteles észlelni, hogy a comparator nem strict weak ordering, és az eredmény (esetleg összeomlás, esetleg értelmesnek látszó, de hibás sorrend) implementációfüggő. A konkrét megfogalmazást a használt szabványverzió algoritmus-követelmény szakaszában érdemes ellenőrizni; a forrásjegyzet ehhez nem tartalmazott ellenőrzött hivatkozást, ezért itt a szerződést tartalomként, nem idézetként adjuk.

29.3.1.1 A NaN-csapda

A lebegőpontos comparator klasszikus hibája a double mező. A NaN értékre minden < hamis, tehát a return a.rtt_us < b.rtt_us; comparator mellett a NaN minden más értékkel ekvivalens lesz. Ez pontosan a 4. feltételt sérti: legyen a.rtt_us = 2.0, b.rtt_us = NaN, c.rtt_us = 5.0. Ekkor $a \sim b$ és $b \sim c$, de $a \sim c$ hamis, mert 2.0 < 5.0. Innen kezdve minden, ami a comparatorra épül, érvénytelen.

Két helyes javítás: a NaN-eket előre kiszűrni (a rekord feldolgozás előtt kap egy „nincs mérés” állapotot, és nem kerül a rendezett sorozatba), vagy totális rendezést adó comparatorral rendezni, amely a NaN-t a sor végére teszi:

bool by_rtt(const Conn& a, const Conn& b) {           // NaN a végére
    const bool na = std::isnan(a.rtt_us), nb = std::isnan(b.rtt_us);
    if (na != nb) return nb;                          // NaN nélküli elem előre
    if (na) return false;                             // két NaN: ekvivalens
    return a.rtt_us < b.rtt_us;
}

Ez strict weak ordering: az irreflexivitás és aszimmetria látszik, a tranzitivitás pedig abból, hogy az értékeket három osztályba sorolja (számok, majd NaN), és az osztályokon belül a valós < tranzitív.

29.3.2 Rendezési algoritmusok és költségeik

A táblázat negyedik oszlopa azért fontos, mert a sort nem garantálja az ekvivalens elemek sorrendjét. Ha a kimenet reprodukálható kell legyen (teszt, diff, audit), akkor vagy stable_sort-ot használunk, vagy a comparatort teljes rendezéssé egészítjük ki egy másodlagos kulccsal (ts_ms, majd conn_id) — ez a gyakorlatban a jobb választás, mert a teljes rendezés minden algoritmuson determinisztikus marad.

Az iterator-kategória nem dekoráció: a std::sort random access iterátort követel, ezért std::list-en fordítási hibát ad — ez a szerződés fordítás idejű kikényszerítése. Listán a tagfüggvény l.sort() a helyes eszköz (stabil merge sort, random access nélkül). A partial_sort és nth_element akkor nyer, ha $k \ll N$: „a 10 leglassabb kapcsolat” esetén $O(N \log 10)$ nagyságrendű munka, szemben a teljes $O(N \log N)$-nel. A nth_element mediánhoz, percentilishez jó: nem rendez, csak szétválaszt.

29.3.3 Keresés rendezett tartományon

A bináris keresés családja a particionáltságot használja ki, nem a teljes rendezettséget. Egy tartomány egy p predikátum szerint particionált, ha minden olyan elem, amelyre p igaz, megelőzi azokat, amelyekre hamis. Az előfeltétel algoritmusonként más predikátumra vonatkozik ([C++20] [alg.binary.search]):

• lower_bound: particionált az e < value (comp(e, value)) szerint;
• upper_bound: particionált a !(value < e) (!comp(value, e)) szerint;
• equal_range és binary_search: mindkét feltétel szerint particionált, és minden e-re e < value-ból következik !(value < e).

Egy comp szerint teljesen rendezett tartomány mindegyik feltételt teljesíti, ezért a gyakorlatban rendezett tartományon keresünk. Az egyoldali particionáltság viszont csak az adott algoritmushoz elég, és a bináris keresés egyiket sem ellenőrzi:

// partition_bounds.cpp — C++20: melyik keresésnek elég az egyoldali particionálás?
#include <algorithm>
#include <cassert>
#include <vector>

int main() {
    const int v = 3;
    std::vector<int> a{1, 2, 5, 3};
    // e < 3:      igaz, igaz, hamis, hamis  -> particionált: lower_bound alkalmazható
    // !(3 < e):   igaz, igaz, hamis, igaz   -> NEM particionált: upper_bound,
    //             equal_range és binary_search előfeltétele sérül
    assert(std::is_partitioned(a.begin(), a.end(), [](int e) { return e < v; }));
    assert(!std::is_partitioned(a.begin(), a.end(), [](int e) { return !(v < e); }));
    auto lb = std::lower_bound(a.begin(), a.end(), v);
    assert(lb == a.begin() + 2);              // az első nem-kisebb elem: az 5
    // std::upper_bound(a.begin(), a.end(), v);  // előfeltétel-sértés, nem teszt
}

Buildjegyzőkönyv (lab-gcc profil). g++ -std=c++20 -Wall -Wextra -Wpedantic -D_GLIBCXX_DEBUG partition_bounds.cpp figyelmeztetés nélkül fordul, és mindhárom assert teljesül. Ugyanerre a tömbre az upper_bound(a.begin(), a.end(), 3) hívást a libstdc++ debug módja elements in iterator range [first, last) are not partitioned by the value hibával elutasítja: ez előfeltétel-sértés, nem érvényes tesztbemenet.

Az equal_range adja vissza az egész ekvivalencia-osztályt [first, second) alakban; a binary_search csak a létezést mondja meg, pozíció nélkül — ha a rekordra is szükség van, nem ez a megfelelő eszköz. A komplexitásáról pontosítani kell: az összehasonlítások száma logaritmikus, de forward iterator esetén a léptetések száma lineáris, mert a bináris keresés nem tud ugrani. Ezért std::list-en a lower_bound megengedett, de lassú; rendezett vektoron viszont valóban $O(\log N)$.

29.3.4 Kidolgozott példa: időablak lekérdezése

Adott egy lezárt kapcsolatokból álló vektor, amelyet időbélyeg szerint rendezünk, majd egy $[t_0, t_1)$ ablakra kérdezünk. A példa C++20-at használ, és önállóan fordítható; a várt kimenet illusztráció, nem mért eredmény.

// conn_query.cpp — g++ -std=c++20 -O2 -Wall -Wextra -o conn_query conn_query.cpp
#include <algorithm>
#include <cstdint>
#include <cstdio>
#include <vector>

struct Conn {
    std::uint64_t ts_ms;    // a kapcsolat lezárásának időpontja
    std::uint32_t conn_id;  // egyedi azonosító
    std::uint32_t rtt_us;   // mért körülfordulási idő
};

// Teljes rendezés: ts_ms, majd conn_id — determinisztikus sorrend.
bool by_time_then_id(const Conn& a, const Conn& b) {
    if (a.ts_ms != b.ts_ms) return a.ts_ms < b.ts_ms;
    return a.conn_id < b.conn_id;
}

// Durvább, csak időbélyegre néző comparator a kereséshez.
// Heterogén hívás: comp(elem, kulcs) és comp(kulcs, elem) is kell.
struct ByTime {
    bool operator()(const Conn& a, const Conn& b) const { return a.ts_ms < b.ts_ms; }
    bool operator()(const Conn& a, std::uint64_t t) const { return a.ts_ms < t; }
    bool operator()(std::uint64_t t, const Conn& b) const { return t < b.ts_ms; }
};

int main() {
    std::vector<Conn> conns = {
        {1000, 7, 220}, {1000, 3, 180}, {1200, 9, 310},
        {900,  1, 140}, {1200, 4, 275}, {1000, 5, 205},
    };
    std::sort(conns.begin(), conns.end(), by_time_then_id);

    const std::uint64_t t0 = 1000, t1 = 1200;   // fél-nyílt ablak
    auto lo = std::lower_bound(conns.begin(), conns.end(), t0, ByTime{});
    auto hi = std::lower_bound(conns.begin(), conns.end(), t1, ByTime{});

    std::uint64_t sum = 0; std::size_t n = 0;
    for (auto it = lo; it != hi; ++it) { sum += it->rtt_us; ++n; }
    std::printf("találat=%zu átlag=%.1f\n", n,
                n ? static_cast<double>(sum) / static_cast<double>(n) : 0.0);
}

A várt (nem mért) kimenet találat=3 átlag=201.7. Két dolgot érdemes kiemelni. Egyrészt a rendezés finomabb comparatort használ, mint a keresés: ez megengedett, mert a finom rendezés finomítása a durvának — ha by_time_then_id szerint a megelőzi b-t, akkor ByTime szerint is, így a particionáltság megmarad. Fordítva viszont nem működik: ha conn_id szerint rendeznénk és ts_ms szerint keresnénk, a particionáltság elvész. Másrészt a felső határhoz lower_bound-ot használunk t1-gyel, mert fél-nyílt ablakot akarunk; upper_bound-dal t0-ra ugyanezt kapnánk. Az equal_range akkor lenne a helyes eszköz, ha egyetlen időbélyeg összes rekordjára kíváncsiak vagyunk.

29.3.5 Lineáris keresés vagy indexépítés?

A std::find előfeltétel nélküli, $O(N)$ összehasonlítás, és input iterátoron is működik. A bináris kereséshez előbb rendezni kell: $O(N \log N)$ egyszeri költség. Ha $k$ lekérdezést futtatunk, a rendezés akkor térül meg, ha $$c_2 \cdot k \cdot N \;>\; c_1 \cdot N \log N \quad\Longrightarrow\quad k \;>\; \frac{c_1}{c_2}\log N,$$ ahol $c_1$ a rendezés, $c_2$ a lineáris keresés egy elempárra jutó költsége. A képlet csak nagyságrendi becslés: a valóságban a find folytonos vektoron kiválóan cache-el, ezért $c_2$ kicsi, és kis $N$-nél vagy néhány lekérdezésnél a lineáris keresés gyorsabb lehet a rendezésnél. Sok lekérdezésnél viszont a rendezett vektor a nyerő, mert a memóriája tömb, a bejárása előre jelezhető.

Harmadik út az index építése: std::unordered_map vagy std::map kulcs alapján. Ez kiküszöböli a rendezést, de csomópontonkénti allokációval és nagyobb memóriával jár, és nem ad sorrendet — időablakra nem alkalmas, egyedi kulcsra viszont igen. A döntés tehát nem „melyik a gyorsabb”, hanem „milyen lekérdezési mintát kell kiszolgálni”: pontkeresés, sorrendi bejárás vagy intervallum.

29.3.6 Tipikus hibák

• return a.ts_ms <= b.ts_ms; — nem irreflexív, ezért nem strict weak ordering. Az std::sort ettől nem definiáltan viselkedik; a helyes <.
• Rendezni by_time_then_id-vel, majd conn_id szerint lower_bound-olni — a particionáltság elvész, az eredmény csendben hibás.
• binary_search-ot hívni rendezetlen vektoron: nincs diagnosztika, csak rossz bool.
• NaN-t tartalmazó double mezőn <-t használni (lásd fent).
• std::sort-ot std::list-en hívni — jó hír, hogy ez fordítási hiba, nem futásidejű hiba.
• Feltételezni, hogy sort után az ekvivalens elemek sorrendje megmarad; arra csak a stable_sort ad garanciát.
• std::lower_bound-ot std::set-en hívni: a tagfüggvény s.lower_bound(v) a megfelelő, mert az kihasználja a fa szerkezetét.

29.3.7 Feladatok

1. (magyarázó) Egy kolléga comparatora return a.rtt_us <= b.rtt_us;. Mutass egy konkrét, háromelemű bemenetet, amelyen a négytagú definíció valamelyik feltétele megsérül, és mondd meg, melyik.

2. (kódolási) Írj Conn-ra olyan comparatort, amely rtt_us szerint csökkenő sorrendbe rendez, a NaN értékeket a sor végére teszi, az azonos rtt_us-ű elemeket pedig conn_id szerint növekvően rendezi. Indokold, miért strict weak ordering.

3. (diagnosztikai) Az alábbi kódrészlet lefordul és lefut, de a lekérdezés néha üres eredményt ad. Keresd meg az okot, és add meg a javítást, valamint egy olyan ellenőrzést, amely fejlesztés közben elkapja a hibát.

std::sort(conns.begin(), conns.end(), by_time_then_id);
auto lo = std::lower_bound(conns.begin(), conns.end(), t0,
                           [](const Conn& a, const Conn& b) { return a.conn_id < b.conn_id; });

4. (döntési) Egy szolgáltatás induláskor 200 000 kapcsolatrekordot tölt be, majd másodpercenként átlagosan 5 időablak-lekérdezést szolgál ki. Hasonlítsd össze a „lineáris szűrés minden lekérdezésnél”, a „rendezés + lower_bound/upper_bound” és az „unordered_map + lineáris szűrés” megoldást, és indokold a választást. Számolj a memóriával és azzal, hogy az ablakok intervallum-lekérdezések.

29.3.8 Megoldások

1. Legyen a.rtt_us = 5. Ekkor comp(a, a) = 5 <= 5 = igaz, tehát az irreflexivitás sérül. Már kételemű, azonos értékű bemeneten is előfordulhat, hogy a rendezés „megcseréli” az elemeket, vagy az implementáció futásidejű hibát jelez; a viselkedés nem garantált, ezért az eredményre hagyatkozni nem lehet. Javítás: <.

2. Egy lehetséges megoldás:

bool by_rtt_desc(const Conn& a, const Conn& b) {
    const bool na = std::isnan(a.rtt_us), nb = std::isnan(b.rtt_us);
    if (na != nb) return nb;            // a NaN mindig hátra
    if (na) return a.conn_id < b.conn_id;
    if (a.rtt_us != b.rtt_us) return a.rtt_us > b.rtt_us;
    return a.conn_id < b.conn_id;
}

Indoklás: az elemeket három régióba sorolja (nem-NaN, NaN), a nem-NaN régiót a > szerint csökkenően rendezi, az ekvivalens (rtt_us egyenlő, vagy mindkettő NaN) elemeket conn_id szerint, ami teljes rendezés. Így a comparator értékkészlete egy Totális rendezés leszűkítése, ami automatikusan strict weak ordering. Ellenőrzési feltétel: tetszőleges bemenetre std::is_sorted(v.begin(), v.end(), by_rtt_desc) igaz, és a NaN-ek a végén vannak.

3. A comparator conn_id szerint hasonlít, miközben a vektor ts_ms szerint rendezett. A lower_bound azt feltételezi, hogy a tartomány a keresett comparatorra nézve particionált; ez itt nem teljesül, ezért az eredmény értelmetlen (a standard szerint előfeltétel-sértés, nem definiált viselkedés, a gyakorlatban csendben rossz index). Javítás: ugyanazt a comparatort használni a kereséshez, amivel rendeztünk, azaz a ByTime struktúrát a fenti példa szerint. Fejlesztés közbeni ellenőrzés:

assert(std::is_sorted(conns.begin(), conns.end(), ByTime{}));

Ez nem bizonyítja a teljes helyességet (a finomabb rendezés is átmegy rajta), de a durva rendezetlenséget elkapja. Erősebb védelem: a keresést egy sorted_by(ByTime{}) invariánst fenntartó típusba zárni, vagy a keresést a rendezéssel azonos comparatort használó helper függvényen keresztül végezni.

4. 200 000 rekordnál egy lineáris szűrés rekordonként néhány tíz ns nagyságrendű, másodpercenként 5 lekérdezésnél ez elfogadható lehet, de a tartalék nő, ha a rekordszám vagy a lekérdezésszám emelkedik. A rendezés egyszeri $O(N \log N)$, utána lekérdezésenként $O(\log N)$ plusz a találati halmaz bejárása — ez a kedvező választás, mert intervallum-lekérdezésről van szó, amit a lower_bound/upper_bound pár természetesen kiszolgál, és a rendezett vektor memóriája folytonos. Az unordered_map pontkeresésre jó, intervallumra nem: egy időablakot nem tudunk vele közvetlenül megválaszolni, csak végigszűrni a teljes táblát, ami rosszabb, mint a rendezett vektor. Ha a rekordok gyakran érkeznek be futásidőben, akkor a beszúrás költsége miatt érdemes inkább rendezett vektort időszakonként újraépíteni, vagy std::multimap-ot használni — de ez már a tárolóválasztás kérdése. Ellenőrzési feltétel: a választott megoldásra írjunk olyan tesztet, amely ismert ablakhosszra ismert darabszámot vár, és határesetként üres ablakot, $[t,t)$-t is lefed.

29.3.9 Összefoglaló

A comparator szerződés: strict weak ordering, és az „egyenlőség” mindenhol ekvivalenciát jelent. A rendezettség a comparatorra van definiálva, ezért a rendezéshez és a kereséshez használt comparatoroknak kompatibilisnek kell lenniük — a finomabb rendezés durvább kereséssel párosítható, fordítva nem. A sort nem stabil, a stable_sort az; a partial_sort és az nth_element akkor nyer, ha nem kell a teljes sorrend. A bináris keresés előfeltétele a particionáltság, nem „valami rendezettség”; a binary_search csak létezést ad, pozícióhoz lower_bound/equal_range kell. Kis $N$-nél vagy kevés lekérdezésnél a lineáris find versenyképes, sok intervallum-lekérdezésnél a rendezett vektor a helyes alap.

Megjegyzés a verziókhoz: a példák ISO C++20-at és a megadott fordítópárt feltételezik; a std::isnan a <cmath>-ból, a std::is_sorted az <algorithm>-ból érkezik. A comparator-követelmények normatív megfogalmazása szabványverziónként változhat, ezért a konkrét szöveget a használt szabványban és a laborprofilban rögzített libstdc++/libc++ kiadás dokumentációjában kell ellenőrizni. A fenti kimenet illusztráció, nem mért eredmény.