28.5 unordered tárolók és container adapterek

A rendezett asszociatív tárolókat (map, set és rendezett asszociatív tárolók) az különböztette meg, hogy a kulcsok között teljes rendezés állt rendelkezésre, és a keresés a fa mélysége mentén $\mathcal{O}(\log n)$ lépésben haladt. Az std::unordered_* tárolók ezzel szemben nem rendezést, hanem ekvivalenciát és hash-függvényt kérnek a kulcstól, és cserébe átlagos $\mathcal{O}(1)$ keresést ígérnek. Ez az ígéret azonban feltételes: a szerződés be nem tartása esetén a tároló továbbra is fordít és fut, csak éppen a költséggörbe és a helyesség csendben elromlik. Ez az alfejezet ezt a szerződést bontja ki, majd megmutatja, hogyan öröklődnek a tároló tulajdonságai a stack/queue/priority_queue adapterekbe.

A C-s hash table (Hash table, comparator és ownership (13.3)) után itt már nem a nyílt láncolás vagy a próbasorozat implementációját kell megérteni, hanem azt, hogy a standard library implementációja ezt hogyan rejti el, és mely garantált viselkedésre lehet építeni. Az unordered_map és unordered_set tipikusan csomópont-alapú (node-based): minden elem külön allokált csomópontban él, a bucket-tömb csak mutatókat/láncfejeket tartalmaz. Ebből következik a legfontosabb tervezési tulajdonság: a referenciák és pointerek az elemekre akkor is érvényesek maradnak, amikor az iterátorok érvénytelenné válnak.

28.5.1 A hash/equality szerződés

Az std::unordered_map<Key, T, Hash, KeyEqual> négy template-paramétere közül az utolsó kettő adja a szerződést. Pontos feltételek:

• KeyEqual (equality predicate) egy ekvivalenciareláció a kulcsokon: reflexív, szimmetrikus, tranzitív. Ez a rendezett tárolók Compare-jének strict weak ordering követelményével analóg, de gyengébb: itt nem kell sorrend, csak megkülönböztethetőség.
• Hash egy konzisztens leképezés: ha eq(a, b) igaz, akkor h(a) == h(b) is igaz kell legyen. A megfordítás nem követelmény: két különböző kulcs hash-elhet ugyanarra az értékre (ez az ütközés, collision), és ezt a tároló KeyEqual-lel oldja fel.
• Mindkettőnek ugyanarra a futásra nézve determinisztikusnak kell lennie; a hash értéke nem változhat meg a kulcs „élete” alatt, különben az elem elvész a saját bucketjéből.

A leggyakoribb hiba pontosan itt keletkezik: a felhasználó a Hash-t csak az egyik mezőre definiálja, míg az operator== kettőre. Ilyenkor két különböző rekord azonos hash-re kerül — ez önmagában még nem hiba, csak ütközés. Fordított esetben viszont, ha az egyenlő kulcsok hash-e eltér, a tároló soha nem találja meg a beszúrt elemet: a find a rossz bucketben keres. Ez nem diagnosztizált hiba, csak csendesen hibás program.

28.5.1.1 Transparent lookup

A C++20 heterogén keresést tesz lehetővé az unordered tárolókban is: ha a Hash-nek és a KeyEqual-nek van is_transparent tagtípusa, akkor a find, count, contains, equal_range olyan kulcstípusokra is hívható, amelyek nem key_type-úak, de a hash és az egyenlőség értelmezi őket. Gyakorlati nyereség: std::string_view-vel keresve nem kell ideiglenes std::string-et allokálni. A feltétel továbbra is a konzisztencia — a két kulcstípusra adott hash-értéknek egyeznie kell, amikor az egyenlőség igazat ad. Ezért érdemes mindkét overloadot ugyanarra az alacsony szintű hash-re építeni:

struct IdHash {
    using is_transparent = void;
    std::size_t operator()(const SessionKey& k) const noexcept {
        return std::hash<std::string_view>{}(std::string_view{k.id});
    }
    std::size_t operator()(std::string_view id) const noexcept {
        return std::hash<std::string_view>{}(id);
    }
};

A std::hash<std::string> és a std::hash<std::string_view> értéke a szabvány szerint nincs összehangolva, ezért a fenti példa mindkét ágon ugyanazt a string_view hash-t használja.

28.5.2 Buckets, load factor és újraelosztás

A tároló belső állapotát három szám jellemzi: a size() (elemek száma), a bucket_count() (bucketek száma) és a max_load_factor() (alapérték $1.0$). Ezekből származik a terheltségi tényező:

$$\text{load\_factor} = \frac{\text{size()}}{\text{bucket\_count()}}$$

A tároló a beszúrás után garantálja, hogy load_factor() <= max_load_factor(); ha ez megsérülne, rehash történik: a bucket-tömb újraallokálódik (jellemzően nagyobbra), és minden elem új bucketbe kerül az új $B'$ méret szerint. A két vezérlő művelet előfeltétele és utófeltétele:

• rehash(n): utófeltétel $B' \ge \max(n, \lceil \text{size}() / \text{max\_load\_factor}() \rceil)$. Komplexitása átlagosan lineáris, legrosszabb esetben négyzetes size()-ben.
• reserve(n): $B' \ge \lceil n / \text{max\_load\_factor}() \rceil$, azaz előre felkészít $n$ elemre. Ezt a max_load_factor beállítása után kell hívni, mert a reserve a pillanatnyi értékkel számol.

A reserve a legolcsóbb védelem a rehash-viharok ellen: ha előre tudjuk, hogy $n$ elem lesz, egy allokációval megússzuk azt, amit egyébként $\log n$ körüli újraépítés jelentene — és ami ennél fontosabb, az iterátorok érvényessége kiszámíthatóvá válik.

28.5.2.1 Iterator versus referencia invalidáció

A node-alapú felépítésből adódó invalidációs táblázat (C++20 [unord.req]):

A gyakorlati tanulság: hosszú életű, stabil hivatkozásra (Session*, Value&) az unordered tároló kiválóan alkalmas, hosszú életű iterátorra viszont nem. Aki iterátort cache-el és közben beszúr, az a find visszatérési értékét használja olyan művelet után, ami rehash-t okozhatott — ez nem definiált viselkedés.

28.5.3 Multi változatok

Az unordered_multimap és unordered_multiset ugyanazt a hash/equality szerződést használja, de ekvivalens kulcsokból többet is tárolhat. Következmények:

• insert mindig sikeres, nem ad bool-t a visszatérési értékben.

• count(k) az ekvivalens elemek számát adja, equal_range(k) az őket tartalmazó fél-nyílt tartományt.

• find(k) az ekvivalens csoport valamelyik elemét adja vissza — az, hogy melyiket, nem specifikált.

• operator[] és at() nincs, mert nem egyértelmű, melyik elemhez rendelnénk.

• erase(k) az összes ekvivalens elemet törli. Egyetlen példány törlésénél előbb ellenőrizni kell, hogy van-e találat: az erase(equal_range(k).first) hiányzó kulcsnál erase(end()) lenne, ami nem definiált viselkedés. A helyes minta:

  if (auto it = c.find(k); it != c.end()) c.erase(it);   // legfeljebb egy elem

  Buildjegyzőkönyv (lab-gcc profil). Egy erase_one sablonba csomagolva, unordered_multimap<std::string, int>-en -D_GLIBCXX_DEBUG mellett tesztelve: hiányzó kulcsnál nem töröl (méret 3 marad), egy találatnál azt törli, két ekvivalens elemnél pontosan egyet.

28.5.4 Container adapterek

A stack, queue és priority_queue nem tárolók, hanem adapterek: egy meglévő Sequence tárolót csomagolnak egy szűkebb felülettel. Nincs begin()/end(), nincs iterátor, nincs size_type-on kívüli méretkezelés — szándékosan, hogy a használat korlátozása az adatszerkezet invariánsát védje. A mögöttes tároló template-paraméter, és az adapter csak azokat a műveleteket hívja, amelyekre szüksége van:

A priority_queue esetében a Compare strict weak ordering kell legyen, és a top() az az elem, amelyre comp(top(), x) egyetlen $x$-re sem igaz — std::less<> mellett tehát ez maximum-kupac. Minimum-kupachoz std::greater<> kell.

Az adapterek invalidációs tulajdonságai az alapkonténerből öröklődnek. Ez a gyakorlatban a legtöbbet elrontott pont: std::vector-on ülő priority_queue esetén a push push_back-et hív, ami újraallokálhat, és ilyenkor a korábban vett top() referencia danglinggá válik. std::deque-on ülő stack esetén a push_back nem invalidálja a meglévő elemekre mutató referenciákat, csak az iterátorokat (amikhez amúgy sem férünk hozzá).

28.5.5 Adverzariális ütközés és költségmodellek

A standard garantált komplexitásai az unordered tárolókra: find, count, ==, != átlagos esetben $\mathcal{O}(1)$, legrosszabb esetben $\mathcal{O}(\text{size}())$; insert/erase átlagosan $\mathcal{O}(1)$, legrosszabb esetben lineáris. A „legrosszabb eset” nem elméleti kuriózum: ha minden kulcs ugyanabba a bucketbe hash-el, a tároló gyakorlatilag láncolt listává degenerálódik, és a beszúrás négyzetes összköltségűvé válik.

A std::hash specializációi (például std::string-re) nem garantáltan ütközésrezisztensek, és a szabvány nem ír elő processzenkénti véletlen seedelést. Ez azt jelenti, hogy támadó által befolyásolt kulcsokkal (HTTP header nevek, query paraméterek, tenant azonosítók) a hash-elés HashDoS felület: a támadó előre kiszámolhatja az ütköző kulcsokat. A védelem nem az unordered_map lecserélése, hanem a hash-függvény megválasztása: per-process vagy per-tároló véletlen seeddel dolgozó, kriptográfiailag tisztességes keverő (pl. SipHash-szerű konstrukció) vagy legalább a seedet a Hash állapotában hordozó funktor.

Fontos különbség a két kategória között: az átlagos költség a hash-eloszlás függvénye, nem a tároló tulajdonsága. Egy jó hash mellett a $0.75$ körüli terheltség mellett a várható lánchossz kicsi, a locality viszont rossz — a csomópontok szétszórva allokálódnak, ezért végigiterálás drágább, mint egy std::vector esetén. A választás tehát nem Big-O-verseny: a map-et akkor érdemes választani, ha sorrendre, range-lekérdezésre vagy determinisztikus iterációs rendre van szükség; az unordered_map-et akkor, ha a kulcs-hőmérséklet magas és a sorrend irreleváns.

28.5.6 Kidolgozott példa

Az alábbi program egy összetett kulcsú munkamenet-tárat mutat be: beállítja a terheltségi tényezőt, előfoglal, majd kényszerített rehash mellett demonstrálja a referencia-stabilitást.

// unordered_lab.cpp -- ISO C++20, GCC 13 / Clang 17, Linux x86-64
#include <cstddef>
#include <functional>
#include <iostream>
#include <string>
#include <unordered_map>

struct SessionKey {
    std::string tenant;
    std::string id;

    friend bool operator==(const SessionKey& a, const SessionKey& b) {
        return a.tenant == b.tenant && a.id == b.id;
    }
};

struct SessionKeyHash {
    std::size_t operator()(const SessionKey& k) const noexcept {
        const std::size_t h1 = std::hash<std::string_view>{}(k.tenant);
        const std::size_t h2 = std::hash<std::string_view>{}(k.id);
        return h1 ^ (h2 + 0x9e3779b97f4a7c15ULL + (h1 << 6) + (h1 >> 2));
    }
};

int main() {
    std::unordered_map<SessionKey, int, SessionKeyHash> sessions;
    sessions.max_load_factor(0.75f);   // elobb a terheltseg, aztan a reserve
    sessions.reserve(4096);

    std::cout << "bucket_count=" << sessions.bucket_count()
              << " size=" << sessions.size()
              << " load_factor=" << sessions.load_factor() << '\n';

    sessions[SessionKey{"acme", "s-1"}] = 10;
    sessions.emplace(SessionKey{"acme", "s-2"}, 20);

    auto it = sessions.find(SessionKey{"acme", "s-1"});
    int* stable = &it->second;         // referencia/pointer az elemre

    const auto before = sessions.bucket_count();
    sessions.rehash(before * 2);       // garantalt ujraelosztas

    std::cout << "rehash: " << before << " -> " << sessions.bucket_count() << '\n';
    // 'it' E R V E N Y T E L E N, 'stable' valtozatlanul ervenyes:
    std::cout << "stable=" << *stable << '\n';
    std::cout << "bucket(s-1)=" << sessions.bucket(SessionKey{"acme", "s-1"}) << '\n';
}

Fordítás és futtatás a tanuló laborjában:

g++ -std=c++20 -Wall -Wextra -Wpedantic -Wconversion -O2 \
    -o unordered_lab unordered_lab.cpp && ./unordered_lab
# vagy
clang++ -std=c++20 -Wall -Wextra -Wpedantic -Wconversion -O2 \
    -o unordered_lab unordered_lab.cpp && ./unordered_lab

A kimenet konkrét számai implementációfüggők (a bucket-számok prímek vagy kettőhatványok lehetnek), ezért mért eredményként nem állítom őket; a program célja a szerződés megfigyelése. Ellenőrzési feltétel: a load_factor() értéke mindig $\le 0.75$, és a stable pointer a rehash után is a helyes értéket olvassa.

Egy min-kupac adapter:

#include <functional>
#include <queue>
#include <vector>

std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
min_heap.push(3);
min_heap.push(1);
min_heap.push(2);          // min_heap.top() == 1

const int& top_ref = min_heap.top();
min_heap.push(0);          // a vector push_back-je ujraallokalhat
// top_ref itt mar E RVENYTELEN lehet

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

1. Inkonzisztens hash/equality. operator== két mezőt hasonlít, a hash csak egyet. Tünet: find néha nem talál meg egyértelműen jelen lévő elemet. Javítás: a hash minden olyan mezőt keverjen bele, amit az egyenlőség figyelembe vesz.
2. Iterátor cache-elése beszúrások között. Javítás: index vagy kulcs szerint keress újra, vagy referenciát/pointert tárolj iterátor helyett.
3. reserve a max_load_factor előtt. Ilyenkor a számítás a régi tényezővel történik, és a tároló a vártnál korábban rehash-el.
4. priority_queue referenciájának megtartása push után. Az alapkonténer vector, ami újraallokál. Javítás: a top()-ot minden használat előtt hívd, vagy deque-et adj meg alapkonténernek.
5. std::hash<std::string>-et támadói bemenetre bízni. Nem garantáltan ütközésrezisztens, és seedelése nem szabványos.
6. Rendezett iterációt várni. Az unordered tároló iterációs sorrendje nem specifikált, és rehash után megváltozik. Ha determinisztikus sorrend kell, a végén rendezni kell, vagy std::map-et kell használni.

28.5.8 Feladatok

1. feladat (magyarázó). Egy kollégád ezt írja: „A hash-em jó, mert két különböző kulcsra is ugyanazt adja vissza, így kevesebb bucket kell.” Fogalmazd meg pontosan, miért hibás ez az érvelés, és melyik irányban követeli meg a szabvány a konzisztenciát.

2. feladat (kódolási). Adott $N = 100\,000$ darab, előre ismert számú munkamenet-azonosító. Készíts egy std::unordered_set<std::string>-et úgy, hogy a beszúrások során egyetlen rehash se történjen, és a load_factor soha ne haladja meg a $0.7$-et. Számítsd ki a szükséges bucket-szám alsó korlátját, és ellenőrizd bucket_count()-tal.

3. feladat (diagnosztikai). Az alábbi kódrészlet egy cache-t tart karban. Mely sorokban van érvénytelenségi hiba, és hogyan javítanád?

std::unordered_map<SessionKey, Payload, SessionKeyHash> cache;
cache.reserve(64);
cache[SessionKey{"acme", "s-1"}] = Payload{};
auto it = cache.find(SessionKey{"acme", "s-1"});
Payload* p = &it->second;
for (int i = 0; i < 10; ++i)
    cache.emplace(SessionKey{"acme", "s-" + std::to_string(i + 100)}, Payload{});
std::cout << it->second.size << ' ' << p->size << '\n';

4. feladat (adapter). Válassz alapkonténert egy stack-hez, amelyre egymillió, váltakozó push/pop/top művelet érkezik, és a top() referenciáját a hívó rövid ideig megtartja. Indokold a választást locality és invalidáció szempontjából, és hasonlítsd össze a deque és a vector viselkedését.

28.5.9 Megoldások

1. megoldás. A szabvány csak egy irányt követel: ha eq(a,b), akkor h(a) == h(b). Az ütközés (különböző kulcsokra azonos hash) megengedett, sőt elkerülhetetlen, hiszen a hash értékkészlete véges, a kulcsoké nem. A „kevesebb bucket” érv tehát nem áll: a bucket-számot nem a hash értékkészlete, hanem a max_load_factor és a size() szabja meg. Ráadásul a sok ütközés pont a legrosszabb esetet hozza: a find lineárissá válik. Az ellenkező irány megsértése (egyenlő kulcsokra eltérő hash) viszont tényleges hiba: az elem a beszúráskori bucketjében marad, a keresés viszont a másik bucketben néz.

2. megoldás. A reserve utófeltétele $B \ge \lceil n / \text{max\_load\_factor} \rceil$, tehát $B \ge \lceil 100000 / 0.7 \rceil = \lceil 142857{,}14\ldots \rceil = 142858$. A helyes sorrend:

std::unordered_set<std::string> s;
s.max_load_factor(0.7f);
s.reserve(100000);
// ... 100000 beszúrás ...
assert(s.bucket_count() >= 142858);
assert(s.load_factor() <= 0.7f);

Az ellenőrzési feltétel a két assert; a tényleges bucket_count() ettől nagyobb is lehet (a prím- vagy kettőhatvány-választás miatt), de kisebb nem. A beszúrások alatt a rehash elmarad, mert a terheltség a reserve által biztosított tartományban marad.

3. megoldás. A reserve(64) után a max_load_factor alapértéke $1.0$, tehát a tároló kb. 64 elemig nem hash-el újra. A ciklus tíz elemet szúr be, így a ciklus után size() kicsi — a rehash valószínűleg nem következik be, de erre nem lehet építeni: a reserve alsó korlátot ad, nem felsőt, és az implementáció a reserve-nél nagyobb bucket-számot is választhat. A hiba tehát nem az, hogy biztosan rehash történik, hanem hogy az it használata a beszúrások után nem garantáltan érvényes. A p viszont az, mert node-alapú tárolóban a beszúrás és a rehash nem invalidálja a referenciákat. Javítás: az it-et a ciklus után újra kell keresni (cache.find(...)), vagy csak p-t kell használni. Helyes záró sor:

auto it2 = cache.find(SessionKey{"acme", "s-1"});
std::cout << it2->second.size << ' ' << p->size << '\n';

Ellenőrzési feltétel: a két érték megegyezik, és az it sehol nem szerepel a beszúrások után.

4. megoldás. A deque a jobb választás, és ezért is ez a stack alapértéke. A push_back/pop_back amortizáltan $\mathcal{O}(1)$, és — ami a feladat szempontjából döntő — a deque végére történő beszúrás nem invalidálja a meglévő elemekre mutató referenciákat. A vector ezzel szemben a kapacitás túllépésekor újraallokál, és ilyenkor minden korábbi top() referencia danglinggá válik. Cserébe a vector jobb locality-t ad: az elemek folytonosak, a top() és pop() egy cache-vonalon marad. Nagy elemszámnál és rövid életű referenciáknál ez a locality előny számíthat, de a feladatban a hívó megtartja a referenciát, ezért a biztonság elsőbbséget élvez. Ellenőrzési feltétel: a push/pop váltakozó sorozata után a megtartott referencia olvasása nem változik meg, és -fsanitize=address alatt sem jelez hibát.

28.5.10 Összefoglaló

Az unordered tárolók szerződése egy ekvivalenciareláció (KeyEqual) és egy azzal konzisztens hash-függvény (Hash); a konzisztencia iránya egyutas: egyenlő kulcsokra egyenlő hash, fordítva nem. A tároló átlagos $\mathcal{O}(1)$ műveleteket ígér, de a legrosszabb eset lineáris, és ez támadó által befolyásolt kulcsoknál elérhető — a std::hash nem garantáltan ütközésrezisztens. A load_factor, max_load_factor, reserve és rehash együtt adják a teljesítmény- és invalidációs modellt: rehash esetén az iterátorok érvénytelenné válnak, a referenciák és pointerek nem. A stack, queue és priority_queue adapterek nem tárolók, hanem egy alapkonténer szűkített felületei, ezért műveleti költségük és invalidációs viselkedésük az alapkonténeréből öröklődik — ezt a választást a locality, a referencia-stabilitás és a szükséges műveletek együtt határozzák meg, nem pusztán a aszimptotikus bonyolultság.