28.4 map, set és rendezett asszociatív tárolók

A rendezett asszociatív tárolók – a std::map, std::set, std::multimap és std::multiset – a modern C++ mindennapi eszközei. DevOps-környezetben tipikusan hosztnév- vagy PID-indexként, konfigurációs kulcstérként, időablakos eseménytárolóként találkozunk velük. A gyakorlati hibák ritkán szintaktikaiak: sokkal gyakrabban a comparator szerződésének megsértése, a lookup API mellékhatása, vagy az iteratorok érvényességi tartományának félreértése áll a háttérben. Ez az alfejezet a szerződéseket és a tipikus döntési helyzeteket tárgyalja, nem a member functionök katalógusát.

28.4.1 A rendezett asszociatív tárolók szerződése

A tárolók a Compare template paraméter által meghatározott rendezést használják. A Compare egy függvényobjektum-típus, amelynek comp(a, b) hívása strict weak orderingot (szigorú gyenge rendezést) valósít meg a kulcsokon. Ennek feltételei:

1. irreflexív: comp(a, a) hamis;
2. aszimmetrikus: ha comp(a, b), akkor !comp(b, a);
3. tranzitív: ha comp(a, b) és comp(b, c), akkor comp(a, c);
4. az ekvivalencia tranzitív: ha $a \sim b$ és $b \sim c$, akkor $a \sim c$, ahol $$a \sim b \iff \neg comp(a,b) \land \neg comp(b,a).$$

Az ekvivalencia itt nem azonos a == operátorral. Egy case-insensitive comparator szerint "API" és "api" equivalent, noha nem egyenlőek. A std::map és std::set egyedi kulcsú: ha egy equivalent kulcs már szerepel, a beszúrás nem történik meg, a meglévő elem marad. A std::multimap és std::multiset több equivalent kulcsot is tárolhat; ezek egymáshoz viszonyított sorrendje nem része a szerződésnek.

A std::map value_type-je std::pair<const Key, T>, a std::set-é Key. A kulcs az iterátoron keresztül nem módosítható. A const_cast használata a fa invariánsát sérti, és nem definiált viselkedéshez vezet.

28.4.2 Lookup és update: a félreérthetetlen API

A leggyakoribb hiba az operator[] használata olvasásra. A m[k] a std::map-en akkor is beszúr egy T() értéket, ha a kulcs nem szerepelt. Ezért const map-en nem is hívható, és a m[k].empty() típusú ellenőrzés mellékhatásként létrehozza az elemet. Ha csak olvasni akarunk, a find, at vagy C++20-ban a contains a helyes választás.

A lower_bound(k) az első olyan elemre mutat, amelyre !comp(elem, k), azaz nem kisebb, mint k. Az upper_bound(k) az első olyan elemre, amelyre comp(k, elem), azaz nagyobb, mint k. Az equal_range(k) a kettőt adja vissza. Ezekkel a [lo, hi) intervallum lekérdezhető; a range query összefüggő intervallumot ad, ha a comparator konzisztens a keresett értékkel.

28.4.3 Heterogén lookup és transparent comparator

A std::map<std::string, T> alapértelmezett comparatorja std::less<std::string>. Ha find("api.example.com")-ot hívunk, a const char*-ból std::string temporális objektum készülhet, ami allokálhat. A std::less<> – a void specializáció – transparent comparator: rendelkezik is_transparent típusdefinícióval, és a tároló find, count, lower_bound, upper_bound, equal_range, valamint C++20-ban contains műveletei heterogén kulcstípussal is hívhatók, ha a comparator össze tudja hasonlítani a kulcstípust a keresett típussal.

C++14 óta a std::less<> transparent. A std::string és a std::string_view összehasonlítható, ezért a std::map<std::string, T, std::less<>> és a find(std::string_view) allokáció nélkül működik. C++17-es fallback: m.find(std::string(k)), ami viszont allokálhat; a C++20-as contains C++17-es megfelelője a find(k) != m.end().

28.4.4 Node handle, merge és allocator feltételek

C++17 óta a rendezett tárolók támogatják a node handle-t. Az extract(key) vagy extract(iterator) kivesz egy node-ot, és visszaad egy node_type objektumot, amely a node-ot birtokolja. A node_type move-only; ha nem kerül beillesztésre, a destruktora felszabadítja a node-ot. A beszúrás tulajdonátadása overloadonként eltér (map/set esetén):

• insert(node_type&& nh) insert_return_type-ot ad vissza (position, inserted, node). Az nh minden esetben kiürül. Siker esetén inserted == true, a node üres; ha a kulcs már szerepelt, inserted == false, a position a meglévő elemre mutat, és a node a result.node-ba kerül — onnan kell továbbvinni, nem az eredeti nh-ból.
• insert(const_iterator hint, node_type&& nh) iterátort ad vissza. Siker esetén az nh kiürül; ha a kulcs már szerepelt, az nh változatlan marad (továbbra is birtokolja a node-ot), a visszaadott iterátor pedig a meglévő elemre mutat.

A node egyik esetben sem vész el; a kérdés csak az, melyik objektum birtokolja.

// node_insert_failure.cpp — C++20: sikertelen node-beszúrás overloadonként
#include <cassert>
#include <map>
#include <string>

int main() {
    std::map<int, std::string> src{{1, "uj"}}, dst{{1, "regi"}};

    // 1) insert(node_type&&) -> insert_return_type
    auto nh = src.extract(1);
    auto result = dst.insert(std::move(nh));
    assert(!result.inserted);                     // a kulcs már létezett
    assert(nh.empty());                           // az eredeti handle kiürült
    assert(!result.node.empty());                 // a node a result.node-ban van
    assert(result.position->second == "regi");    // a meglévő elemre mutat
    assert(result.node.mapped() == "uj");         // a rekord nem veszett el

    // 2) insert(hint, node_type&&) -> iterator; sikertelenségnél nh változatlan
    auto nh2 = std::move(result.node);
    auto pos = dst.insert(dst.end(), std::move(nh2));
    assert(!nh2.empty() && nh2.mapped() == "uj"); // a node maradt a handle-ben
    assert(pos->second == "regi");

    // A megtartott node máshová beszúrható:
    std::map<int, std::string> other;
    assert(other.insert(std::move(nh2)).inserted);
    assert(other.at(1) == "uj");
}

Buildjegyzőkönyv (lab-gcc profil). g++ -std=c++20 -Wall -Wextra -Wpedantic -D_GLIBCXX_DEBUG node_insert_failure.cpp figyelmeztetés nélkül fordult, és a futás egyik assert-et sem sértette.

A merge(source) átmozgatja a forrás elemeit a célba. Map/set esetén csak azok kerülnek át, amelyek kulcsa a célban még nem szerepel; a többi a forrásban marad. Multimap/multiset esetén minden elem áthelyeződik, mert nincs egyediség. A merge előfeltétele, hogy a két tároló allocatora egyenlő legyen (get_allocator() == source.get_allocator()); ellenkező esetben a viselkedés nem definiált. A művelet allokáció nélkül mozgatja a node-okat. Az áthelyezett elemekre mutató pointerek és referenciák érvényesek maradnak; az iterátorok is érvényesek, és továbbra is ugyanarra az elemre mutatnak, de a merge után a cél tároló iterátoraiként viselkednek ([C++20] [associative.reqmts]). Ezért csak a cél tároló iterátoraival alkothatnak tartományt vagy hasonlíthatók össze (például it != target.end()), a forráséval nem.

Az extract és a merge élettartam-szabályai egy életcikluson követhetők:

1. Kivétel előtt referenciát vagy pointert veszünk egy elemre.
2. extract után az elem iterátora érvénytelen, a referencia és a pointer viszont nem lógó: ugyanarra az elemre mutat, amelyet most a node_type birtokol. Amíg a node a handle-ben van, rajtuk keresztül hozzáférni nem definiált viselkedés; a kulcs ilyenkor a nh.key()-en át módosítható.
3. Sikeres insert után a node újra a tárolóé, és a kivétel előtt vett referencia és pointer ismét használható. (A node-birtoklás alatt vett referenciák viszont a sikeres beszúráskor érvénytelenné válnak.)

// node_lifecycle.cpp — C++20: extract → kulcsmódosítás → insert, és merge
#include <cassert>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> routes{{"api-old", 1}, {"web", 2}};

    // (1) A kivétel ELŐTT vett referencia és pointer.
    int& ref = routes.at("api-old");
    int* ptr = &ref;

    // (2) extract: az iterátor érvénytelen, a ref/ptr NEM — de amíg a node
    //     a node_type-ban van, rajtuk keresztül hozzáférni UB.
    auto nh = routes.extract("api-old");
    nh.key() = "api";                 // a kulcs a handle-ön át módosítható
    // *ptr = 5;                      // HIBA lenne: a node a handle birtokában

    // (3) Sikeres insert: a node visszakerül, a ref/ptr újra használható.
    auto r = routes.insert(std::move(nh));
    assert(r.inserted && r.position->first == "api");
    ref += 10;                        // ugyanarra az elemre hat
    assert(routes.at("api") == 11 && *ptr == 11);

    // (4) merge: az áthelyezett elem korábbi iterátora érvényes marad,
    //     és innentől a CÉL tároló iterátoraként viselkedik.
    std::map<std::string, int> extra{{"db", 3}, {"web", 99}};
    auto it_db = extra.find("db");
    routes.merge(extra);
    assert(it_db->first == "db" && it_db->second == 3);
    assert(&*it_db == &*routes.find("db")); // a célban ugyanazt az elemet azonosítja
    assert(extra.size() == 1 && extra.begin()->first == "web");  // ütköző kulcs maradt
}

Buildjegyzőkönyv (lab-gcc profil). g++ -std=c++20 -Wall -Wextra -Wpedantic -fsanitize=address,undefined node_lifecycle.cpp figyelmeztetés nélkül fordult, a futás egyik assert-et sem sértette, ASan/UBSan nem jelzett. Megjegyzés a diagnosztikához: a libstdc++ -D_GLIBCXX_DEBUG módja a merge után is a forráshoz rendeli az áthelyezett elem iterátorát, és az it_db == routes.find("db") összehasonlítást attempt to compare iterators from different sequences hibával elutasítja, noha a szabvány szerint az iterátor ekkor már a célhoz tartozik. Ezért a példa a címazonosságot (&*it_db == &*routes.find("db")) ellenőrzi, amely debug módban is lefut; a libc++ (Clang 22) a közvetlen iterátor-összehasonlítást is elfogadta.

28.4.5 Iteratorstabilitás és komplexitás

A merge komplexitása $O(n \log n)$, ahol $n$ a forrás elemszáma, mert minden elemet össze kell hasonlítani a cél kulcsaival. A bejárás $O(n)$, de a node-ok nem folytonosak, ezért a cache-viselkedés gyengébb, mint a std::vector esetében. A tárolóválasztásnál tehát a Big-O mellett a localityt, az allokációs mintát és az iteratorstabilitást is mérlegelni kell.

28.4.6 Kidolgozott példa: routing tábla

Az alábbi példa egy hosztnév-alapú routing táblát mutat. A std::less<> transparent comparator miatt a lookup std::string_view-vel allokáció nélkül működik. A with_prefix a lower_bound-ot használja: a lexikografikus rendezésben az azonos prefixű kulcsok összefüggő intervallumba esnek.

#include <map>
#include <string>
#include <string_view>
#include <vector>
#include <iostream>
#include <stdexcept>
#include <utility>

struct Endpoint {
    std::string host;
    unsigned short port;
};

class RoutingTable {
public:
    void upsert(std::string key, Endpoint ep) {
        table_.insert_or_assign(std::move(key), std::move(ep));
    }

    const Endpoint* lookup(std::string_view key) const noexcept {
        auto it = table_.find(key);
        return it == table_.end() ? nullptr : &it->second;
    }

    const Endpoint& at(std::string_view key) const {
        auto it = table_.find(key);
        if (it == table_.end()) throw std::out_of_range("no route");
        return it->second;
    }

    std::vector<std::string> with_prefix(std::string_view p) const {
        std::vector<std::string> out;
        auto it = table_.lower_bound(p);
        while (it != table_.end() && it->first.starts_with(p)) {
            out.push_back(it->first);
            ++it;
        }
        return out;
    }

private:
    std::map<std::string, Endpoint, std::less<>> table_;
};

int main() {
    RoutingTable rt;
    rt.upsert("api.example.com", {"10.0.0.1", 443});
    rt.upsert("api.internal", {"10.0.0.2", 8443});
    rt.upsert("web.example.com", {"10.0.0.3", 80});

    if (auto* ep = rt.lookup("api.example.com")) {
        std::cout << ep->host << ':' << ep->port << '\n';
    }
    for (auto& k : rt.with_prefix("api.")) std::cout << k << '\n';
}

Buildparancs GCC-vel vagy Clanggel:

g++ -std=c++20 -Wall -Wextra -Wpedantic -O2 routing.cpp -o routing
# vagy: clang++ -std=c++20 -Wall -Wextra -Wpedantic -O2 routing.cpp -o routing

A starts_with C++20-as; C++17-es fallback: it->first.compare(0, p.size(), p) == 0. Az insert_or_assign C++17-es. A példa a megadott forrásokon kívül nem került lefuttatásra; a várt viselkedés a C++20 szerződésen alapul, a tényleges eredményt a tanuló laborja igazolja.

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

• <= comparator. A [](int a, int b) { return a <= b; } megsérti az irreflexivitást: comp(a,a) igaz. A std::set belső invariánsa sérül, a viselkedés nem definiált. Javítás: return a < b;.
• operator[] olvasásra. A m[k] beszúr. Helyette find, at vagy contains.
• find eredményének bool-ként való használata. Az iterator nem konvertálható bool-lá. Helyesen it != m.end() vagy m.contains(k).
• Iterátor invalidáció törlés közben. C++11 óta it = m.erase(it) a helyes; a m.erase(it++) régi minta.
• Kulcs módosítása. A const_cast<Key&>(it->first) = ... a fa invariánsát sérti; nem definiált viselkedés.
• Dangling comparator. Ha a comparator egy külső objektumra hivatkozik, annak élettartama legalább a tárolóéval kell egyezzen.

28.4.8 Feladatok

1. (Könnyű) Magyarázd el, miért nem megfelelő a [](const int& a, const int& b) { return a <= b; } comparator egy std::set<int>-hez. Add meg a javítást, és mondd meg, milyen viselkedést okoz a hibás változat.

2. (Közepes) Adott egy std::map<std::string, int> számláló. Írj függvényt, amely megnöveli a kulcs számlálóját, de csak akkor, ha a kulcs már létezik; új kulcsot ne hozzon létre. Hasonlítsd össze a operator[], az at és a find megoldásokat.

3. (Nehéz) Implementálj egy TimeWindowIndex osztályt, amely std::multimap<std::int64_t, std::string>-ben tárol eseményeket timestamp szerint. Támogassa a [from, to) intervallum-lekérdezést, és egy merge_from(TimeWindowIndex&) műveletet node handle-lel. Add meg a buildparancsot és az érvényességi feltételeket.

28.4.9 Megoldások

1. A <= sérti az irreflexivitást: comp(a,a) igaz lesz. A std::set beszúrásai és keresései hibás fába vezetnek; az elemek egy része elveszhet, a find hibásan működhet, a viselkedés nem definiált. Javítás: return a < b;. Ellenőrzési feltétel: a comparator szigorúan monoton, és comp(a,a) hamis.

2. A helyes megoldás egyetlen lookup:

void increment_existing(std::map<std::string, int>& m, const std::string& key) {
    auto it = m.find(key);
    if (it != m.end()) ++it->second;
}

Az operator[] beszúrna egy 0-t, ezért nem jó. Az at kivételt dob, ha nincs, ezért try/catch kellene, ami nem hatékony. A find nem szúr be, és egy lookup. C++20-ban a contains is használható, de az két lookup lenne. Ellenőrzési feltétel: hiányzó kulcsra a map mérete nem változik.

3. Megoldás:

// time_window.cpp — C++20, teljes program
#include <map>
#include <string>
#include <vector>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <utility>

class TimeWindowIndex {
public:
    using key_type = std::int64_t;
    using mapped_type = std::string;
    using container = std::multimap<key_type, mapped_type>;

    void add(key_type ts, std::string event) {
        index_.emplace(ts, std::move(event));
    }

    // Félig nyílt [from, to) intervallum. Policy: from >= to esetén üres
    // eredmény; az ellenőrzés az iterátorok képzése előtt történik, mert
    // from > to esetén lo a hi után állna, és a ciklus túlfutna.
    std::vector<std::string> range(key_type from, key_type to) const {
        std::vector<std::string> out;
        if (from >= to) return out;
        auto lo = index_.lower_bound(from);
        auto hi = index_.lower_bound(to);
        for (auto it = lo; it != hi; ++it) out.push_back(it->second);
        return out;
    }

    void merge_from(TimeWindowIndex& other) {
        index_.merge(other.index_);
    }

private:
    container index_;
};

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

int main() {
    TimeWindowIndex empty;
    CHECK(empty.range(0, 100).empty());           // üres index

    TimeWindowIndex w;
    w.add(10, "a"); w.add(20, "b"); w.add(20, "b2"); w.add(30, "c");
    CHECK(w.range(20, 20).empty());               // from == to
    CHECK(w.range(15, 30).size() == 2);           // from < to: b, b2
    CHECK(w.range(10, 31).size() == 4);
    CHECK(w.range(25, 15).empty());               // from > to: üres

    TimeWindowIndex other;
    other.add(20, "x");
    w.merge_from(other);
    CHECK(w.range(20, 21).size() == 3 && other.range(0, 100).empty());
    std::puts("time_window: ok");
}

Build: g++ -std=c++20 -Wall -Wextra -Wpedantic time_window.cpp -o time_window && ./time_window. A range a félig nyílt [from, to) intervallumot adja, a lower_bound(from) és lower_bound(to) közötti iterátorokkal. A dokumentált policy: from >= to esetén az eredmény üres, és ezt az ellenőrzést az iterátoros ciklus előtt kell elvégezni; from > to esetén ugyanis a lo a hi után állna, és a ciklus a tároló végén túlra lépne. A to felső határ, ezért lower_bound(to) a helyes, nem upper_bound. A merge multimap esetén minden elemet áthelyez. Érvényességi feltétel: a két tároló allocatora egyenlő kell legyen. A merge után az áthelyezett elemekre korábban vett iterátorok érvényesek maradnak, de már a cél tároló (w) iterátorai: a forrás (other) end()-jével nem alkothatnak tartományt.

Buildjegyzőkönyv (lab-gcc profil). A program figyelmeztetés nélkül fordult, és a négy esetet (üres index, from == to, from < to, from > to), valamint a merge_from hatását ellenőrizve time_window: ok kimenettel futott, -D_GLIBCXX_DEBUG és ASan/UBSan mellett is. A javítás előtti változat range(25, 15) hívása -D_GLIBCXX_DEBUG mellett attempt to dereference a past-the-end iterator hibával állt le.

28.4.10 Összefoglaló

A rendezett asszociatív tárolók akkor használhatók biztonságosan, ha a comparator strict weak ordering, a lookup nem jár mellékhatással, és az iteratorok érvényességi tartományát ismerjük. A std::less<> heterogén lookupja allokációt spórol; a node handle és a merge allokáció nélküli áthelyezést tesz lehetővé, de allocator-feltétele van. A std::map nem mindenre jobb, mint a std::vector; a rendezettség és az iteratorstabilitás ára a gyengébb locality.

28.4.11 Források és korlátok

A fejezet a C++20 szabvány asszociatív tároló követelményeire támaszkodik (ISO/IEC 14882:2020, [associative.reqmts]). A konkrét implementációk – libstdc++, libc++ – eltérhetnek a node handle és a merge részleteiben. A szöveget nem kísérte automatikus forrásellenőrzés; a tanulónak a saját compiler- és library-verzióján kell ellenőriznie a viselkedést. A megadott kiinduló URL-eket a fejezet nem használta fel ellenőrzött bizonyítékként.