43.1 flat_map és flat_set: rendezett tárolás folytonos memóriában

A std::flat_map és a std::flat_set a C++23-ban jelent meg (P0429 szabványterv). A nevükben a „flat” arra utal, hogy nem csomópont-alapú tárolót használnak, hanem a kulcsokat és az értékeket lapos, rendezett konténerekben tartják. Ez a felépítés a keresést és az iterációt cache-baráttá teszi, a beszúrást és a törlést viszont lineáris költségűvé teszi. A fejezet a szerződéseket, a költségeket és a választási szempontokat tárgyalja; a konkrét implementációtámogatást nem tekintjük ellenőrzöttnek, ezért feature-test makrót és compile probe-ot adunk. A rendezett asszociatív tárolók alapjait a map, set és rendezett asszociatív tárolók részben rögzítettük, a tárolóválasztás általános szempontjait a Tárolóválasztási és invalidációs labor, a cache-viselkedés hátterét az Object layout, EBO és adatközpontú tervezés tárgyalta.

43.1.1 Mi a flat_map és a flat_set?

A std::flat_map asszociatív konténer-adaptor, amely rendezett kulcs-érték párokat tárol két párhuzamos konténerben. A kulcstároló és az értéktároló azonos méretű; az i-edik kulcs az i-edik értékhez tartozik. A kulcsok a Compare szerint rendezettek és egyediek. A std::flat_set ugyanez egyetlen kulcstárolóval. A flat_multimap és a flat_multiset ekvivalens kulcsokat is megenged; a beszúrás az ekvivalens kulcsok felső határára történik, hogy a sorrend stabil maradjon.

A default tároló std::vector, de a kulcs- és értéktároló template paraméterrel cserélhető:

template<class Key, class T, class Compare = std::less<Key>,
         class KeyContainer = std::vector<Key>,
         class MappedContainer = std::vector<T>>
class flat_map;

template<class Key, class Compare = std::less<Key>,
         class KeyContainer = std::vector<Key>>
class flat_set;

A flat_map nem std::pair<const Key, T> elemeket tárol, hanem külön kulcs- és értéktárolót. Ezért a value_type std::pair<Key, T>, a reference pedig egy proxy: std::pair<const Key&, T&>. A kulcs a tárolóban nem módosítható, az érték igen. A flat_set iterátora a kulcstároló const iterátora, ezért a kulcsok ott sem módosíthatók.

43.1.2 Tárolószerkezet és a sorted_unique szerződés

A sorted_unique tag azt jelöli, hogy a konstruktornak átadott kulcs- és értéktároló már a Compare szerint rendezett, és a kulcsok egyediek. A tag nem ellenőriz, hanem előfeltételt rögzít; ha a bemenet nem rendezett vagy nem egyedi, a viselkedés nem definiált (UB). A tag előnye, hogy elkerüli az O(n log n) rendezést és az egyediség ellenőrzését. A sima konstruktor ezzel szemben rendez, és a flat_map esetében az ekvivalens kulcsok közül egyet megtart.

std::flat_map<int, std::string> m(
    std::sorted_unique,
    std::vector<int>{1, 2, 3},
    std::vector<std::string>{"one", "two", "three"});

A sorted_unique akkor hasznos, ha a kulcsokat egy korábbi lépésben már rendeztük, vagy ha természetes sorrendben érkeznek. A flat_multimap és flat_multiset esetében a tag neve sorted_equivalent, mert ott az ekvivalens kulcsok megengedettek. A mögöttes konténereknek véletlen hozzáférésűnek kell lenniük, és támogatniuk kell a beszúrást és a törlést; a default std::vector folytonos, de például egy std::deque választása esetén a folytonosság és a cache-előny részben elvész.

43.1.3 Műveleti költségek és cache-viselkedés

A flat tárolók költségei a mögöttes konténerek műveleteiből származnak. A keresés a kulcstárolón bináris keresés, ezért O(log n) összehasonlítás; a beszúrás és a törlés a vektoros eltolás miatt O(n). A csomópont-alapú és hash tárolókhoz viszonyítva:

A keresés a kulcsok tömbjén fut, nem a párokon, ezért a kulcsok folytonos tárolása jobb cache-kihasználást ad, mint a std::map csomópontjainak követése. A bináris keresés első lépései ugrálnak, de a tömb egyes részei cache-vonalban vannak. A flat_map előnye különösen akkor jelentős, ha a kulcsok kicsik, az összehasonlítás olcsó, és a keresés gyakori. Nagy kulcsok (például hosszú stringek) esetén a bináris keresés több összehasonlítást végez, mint egy hash-alapú keresés, ezért a unordered_map versenyképes lehet.

A beszúrás költsége a beszúrási pozíciótól függ. A végére beszúrás eltolás nélkül, amortizált O(1); a közepére beszúrás O(n). Rendezett sorrendben érkező beszúrások a flat tárolók kedvező esete. Az iteráció folytonos, ezért a teljes bejárás gyors; a std::map iterációja pointer chasing miatt lassabb. A memóriahasználat szempontjából a flat tároló kevesebb allokációt végez, és kisebb az egy eleme jutó overhead, mert nincsenek csomópontpointerek és színinformációk.

43.1.4 Invalidáció és kivételbiztonság

A flat_map::insert, erase, clear és operator[] minden iterátort és referenciát invalidál, nem csak a beszúrt vagy törölt elemre vonatkozót. Az ok a mögöttes vektoros tárolás: a beszúrás eltolhatja az elemeket, és újraallokálhat, ami az összes címre hat. A reserve nem invalidál, de a kapacitás növelése után a beszúrás még mindig eltolhat. A swap nem invalidál, de az iterátorok a másik konténer elemeire mutatnak tovább.

A flat_map::reference proxy jellege miatt a for (auto& [k, v] : fm) alak nem fordul le, mert az iterátor dereferálása egy prvalue std::pair<const Key&, T&>-t ad. Helyes: for (auto&& [k, v] : fm) vagy for (auto [k, v] : fm). A k ekkor const Key&, a v T&, tehát az érték módosítható, a kulcs nem.

A flat_map::insert dokumentált szerződése erős kivételgaranciát ad: ha a beszúrás bármely lépése kivételt dob, a tároló változatlan marad. Ez a mögöttes konténerek garanciáin múlik; a konkrét implementációt ellenőrizni kell. A flat_map::erase a mögöttes konténerek erase-műveleteire támaszkodik, ezért a kivételbiztonsága azok garanciáitól függ.

43.1.5 Kidolgozott példa és build

Az alábbi program bemutatja a sorted_unique tagot, a keresést, a beszúrást és a proxy referenciát. A példa önállóan fordítható, ha a fordító és a standard library támogatja a flat_map-et.

#include <flat_map>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

int main() {
    using map_t = std::flat_map<int, std::string>;

    // Rendezett, egyedi kulcsok: a sorted_unique tag nem ellenőriz.
    std::vector<int> keys{1, 3, 5};
    std::vector<std::string> vals{"one", "three", "five"};
    map_t m(std::sorted_unique, std::move(keys), std::move(vals));

    // Keresés a kulcstömbön.
    auto it = m.find(3);
    if (it != m.end()) {
        std::cout << it->first << " -> " << it->second << '\n';
    }

    // Beszúrás: minden korábbi iterátor és referencia invalidálódik.
    m.insert({2, "two"});
    // it = m.find(3); // ha kell, újra kell keresni

    // Iteráció: a reference proxy, ezért auto&& kell.
    for (auto&& [k, v] : m) {
        std::cout << k << '=' << v << '\n';
    }
}

A buildparancs GCC-vel és Clanggel:

g++ -std=c++23 -O2 -Wall -Wextra -pedantic flat_map_demo.cpp -o flat_map_demo
clang++ -std=c++23 -O2 -Wall -Wextra -pedantic flat_map_demo.cpp -o flat_map_demo

A tényleges fordíthatóságot a laborprofilban rögzített fordító- és könyvtárverzió dönti el; a következő szakaszban adott compile probe ezt hivatott ellenőrizni.

43.1.6 Benchmark: olvasás- és írásdomináns terhelés

A flat tárolók és a csomópont-alapú, illetve hash tárolók összehasonlítását méréssel kell eldönteni. A fejezet nem állítja, hogy a flat_map minden esetben gyorsabb; a mérés a tanuló laborjához tartozik. A mérési terv:

• Hasonlítsd össze a flat_map, std::map és std::unordered_map tárolókat azonos kulcshalmazon, azonos compiler flaggel és azonos standard library-vel.
• Olvasás-domináns terhelés: például 90% find, 10% insert. Írás-domináns terhelés: 90% insert/erase, 10% find.
• Használj legalább $N=10^5$ és $N=10^6$ méretet, véletlen kulcsokat, és ismételd meg a mérést legalább ötször; a mediánt közöld.
• Külön eset a rendezett sorrendben érkező beszúrás, mert ez a flat tároló kedvező esete.
• Mérd a wall time-ot std::chrono::steady_clock-kal, a cache-misseket perf stat -e cache-misses,cache-references segítségével, és az allokációk számát például számláló allocatorral vagy valgrind eszközzel.
• Melegíts, és a fordító optimalizálását ne engedd kiejteni a kereséseket: összegezd a találatokat, vagy használj DoNotOptimize-szerű megoldást.
• A mért eredményt, a várt eredményt és az illusztrációt külön kategóriaként kezeld; a fejezet nem közöl mért számokat.

43.1.7 Támogatás ellenőrzése és C++20 fallback

A flat_map és flat_set elérhetőségét feature-test makróval és compile probe-bal kell ellenőrizni. A várt makró neve __cpp_lib_flat_map; a szabványterv alapján a várt érték 202207L, de a tényleges értéket a <version> headerből kell kiolvasni. A következő probe nem támogatott környezetben #error-ral áll meg:

#include <version>
#if !defined(__cpp_lib_flat_map) || __cpp_lib_flat_map < 202207L
#error "A flat_map/flat_set nem tamogatott ezen a forditón es standard library-n."
#endif
#include <flat_map>
#include <flat_set>

C++20-ban a std::flat_map nem elérhető. A leggyakoribb fallback egy rendezett std::vector<std::pair<Key, T>> és std::lower_bound; ez a keresést és a beszúrást utánozza, de nem nyújtja a teljes API-t:

#include <algorithm>
#include <utility>
#include <vector>

template<class Key, class T, class Compare = std::less<Key>>
class flat_map_cpp20 {
    std::vector<std::pair<Key, T>> data_;
    Compare comp_{};
public:
    using value_type = std::pair<Key, T>;
    using iterator = typename std::vector<value_type>::iterator;
    using const_iterator = typename std::vector<value_type>::const_iterator;

    const_iterator find(const Key& k) const {
        auto it = std::lower_bound(data_.begin(), data_.end(), k,
            [this](const value_type& p, const Key& key) {
                return comp_(p.first, key);
            });
        if (it != data_.end() && !comp_(k, it->first)) return it;
        return data_.end();
    }

    std::pair<iterator, bool> insert(value_type v) {
        auto it = std::lower_bound(data_.begin(), data_.end(), v.first,
            [this](const value_type& p, const Key& key) {
                return comp_(p.first, key);
            });
        if (it != data_.end() && !comp_(v.first, it->first)) {
            return {it, false};
        }
        return {data_.insert(it, std::move(v)), true};
    }
};

A fallback beszúrása szintén O(n), és minden iterátort invalidál. A std::lower_bound feltétele, hogy a tartomány a comparator szerint rendezett legyen; ezt a beszúrásnak fenn kell tartania.

43.1.8 Gyakori hibák

• A flat_map iterátorát vagy referenciáját beszúrás vagy törlés után használni. A művelet minden iterátort és referenciát invalidál.
• A flat_map::reference-t valódi std::pair<const Key, T>&-nek hinni. Az egy proxy std::pair<const Key&, T&>, ezért auto& helyett auto&& vagy auto kell.
• A sorted_unique tagot ellenőrzés nélkül használni nem rendezett vagy nem egyedi bemenetre. Ez UB.
• A flat_map-et írás-domináns terhelésre választani, ahol a beszúrás és a törlés O(n) költsége dominál.
• Keresésre a flat_map::operator[]-t használni, mert az beszúr, ha a kulcs nincs; helyette find vagy at kell.
• A flat tároló kulcsát módosítani próbálni. A kulcsok const hozzáféréssel érhetők el; a módosítás a rendezettséget sértené.

43.1.9 Feladatok

1. Tárolóválasztás. Egy olvasás-domináns szolgáltatásban a konfigurációs kulcsokat gyakran keresik, ritkán módosítják. Egy írás-domináns eseményaggregátorban sok beszúrás és törlés van. Egy nagy, egyedi azonosítós cache-ben a kulcsok egészek, a keresés gyakori. Válassz tárolót mindhárom esetre, és indokold a komplexitás, az invalidáció és a memória alapján.

2. Kódolás. Írj egy build_flat_map függvényt, amely egy std::vector<std::pair<std::string, int>> bemenetből std::flat_map<std::string, int>-et épít. Ha a bemenet rendezett és egyedi, használd a sorted_unique tagot; különben a sima konstruktort. Dokumentáld az előfeltételeket, és ellenőrizd a rendezettséget és az egyediséget.

3. Diagnosztika. Az alábbi kód UB-t tartalmaz. Mutasd meg, miért, és javítsd.

std::flat_map<int, std::string> m{{1, "one"}, {2, "two"}};
auto it = m.find(1);
m.insert({3, "three"});
std::cout << it->second;

4. Benchmarkterv. Tervezz benchmarkot a flat_map, std::map és std::unordered_map összehasonlítására. Add meg a terhelési arányokat, a méreteket, az ismétlések számát, a mért metrikákat és a lehetséges torzításokat. Ne állítsd, hogy a flat_map gyorsabb.

43.1.10 Megoldások

43.1.10.1 1. feladat megoldása

Az olvasás-domináns konfigurációs szolgáltatásban a flat_map jó választás: a keresés O(log n) folytonos kulcstömbön, az iteráció gyors, a memóriaoverhead kicsi. Ha a kulcsok nagyok és a hash számítás olcsó, a unordered_map is versenyképes. Az írás-domináns eseményaggregátorban a unordered_map vagy a std::map a jobb, mert a flat_map beszúrása és törlése O(n); ha a rendezettség nem kell, a hash tároló, ha kell, a csomópont-alapú map választandó. A nagy, egyedi azonosítós cache-ben a unordered_map a kézenfekvő, mert a hash átlag O(1); ha a cache kicsi és a keresés a domináns, a flat_map is szóba jön.

43.1.10.2 2. feladat megoldása

#include <algorithm>
#include <flat_map>
#include <string>
#include <utility>
#include <vector>

std::flat_map<std::string, int>
build_flat_map(std::vector<std::pair<std::string, int>> input) {
    const bool sorted_unique = std::is_sorted(
        input.begin(), input.end(),
        [](const auto& a, const auto& b) { return a.first < b.first; })
        && std::adjacent_find(
            input.begin(), input.end(),
            [](const auto& a, const auto& b) { return a.first == b.first; })
           == input.end();

    if (sorted_unique) {
        std::vector<std::string> keys;
        std::vector<int> vals;
        keys.reserve(input.size());
        vals.reserve(input.size());
        for (auto& p : input) {
            keys.push_back(std::move(p.first));
            vals.push_back(p.second);
        }
        return std::flat_map<std::string, int>(
            std::sorted_unique, std::move(keys), std::move(vals));
    }
    return std::flat_map<std::string, int>(input.begin(), input.end());
}

A sorted_unique ág előfeltétele, hogy a kulcsok a std::less<std::string> szerint rendezettek és egyediek legyenek; ezt az std::is_sorted és az std::adjacent_find ellenőrzi. A másik ág a range konstruktort használja, amely rendez és egyedivé tesz. Az ellenőrzés feltétele, hogy a bemenet a kulcs szerint rendezett legyen; ha nem az, a rendezett ág nem választható.

43.1.10.3 3. feladat megoldása

A hiba oka, hogy a flat_map::insert a mögöttes vektorba szúr, ami eltolhatja az elemeket és újraallokálhat, ezért minden korábbi iterátor és referencia invalidálódik. Az it a régi tárolóra mutat, a használata UB. A javítás: az insert után újra kell keresni.

std::flat_map<int, std::string> m{{1, "one"}, {2, "two"}};
m.insert({3, "three"});
auto it = m.find(1);
if (it != m.end()) {
    std::cout << it->second << '\n';
}

Az insert visszatérési értéke egy std::pair<iterator, bool>, amely a beszúrt elemre mutató iterátort adja; ez használható, de a régi iterátor nem.

43.1.10.4 4. feladat megoldása

A benchmark három tárolót hasonlít össze: flat_map, std::map, std::unordered_map. Az olvasás-domináns terhelés 90% find, 10% insert; az írás-domináns 90% insert/erase, 10% find. A méretek $N=10^5$ és $N=10^6$, a kulcsok véletlen eloszlásúak, a beszúrások véletlen és rendezett sorrendben is futnak. Az ismétlések száma legalább öt, a közölt érték a medián. Mért metrikák: wall time std::chrono::steady_clock-kal, cache-missek perf stat-tal, allokációk száma számláló allocatorral. A torzításforrások: a keresési kulcsok eloszlása, a beszúrások sorrendje, a compiler optimalizálása, a standard library verziója, a cache mérete és a rendszer terheltsége. A flat_map előnye az olvasás-domináns, kis módosítású esetben várható; ezt a mérésnek kell igazolnia, nem a fejezetnek.

43.1.11 Összefoglaló

A flat_map és a flat_set a C++23 rendezett, folytonos tárolású adaptorai. A keresés és az iteráció cache-baráts, a beszúrás és a törlés O(n). A választás a terheléstől függ: olvasás-domináns, kis módosítású adatokra kiváló; írás-domináns terhelésre a csomópont-alapú vagy hash tárolók jobbak. A sorted_unique tag előfeltétel, nem ellenőrzés. A beszúrás és a törlés minden iterátort és referenciát invalidál. A támogatást feature-test makróval és compile probe-bal kell ellenőrizni; C++20-ban rendezett vector és std::lower_bound a fallback.