28.3 deque, list és forward_list

A folytonos tárolás (std::array, std::vector és folytonos tárolás (28.1)) után könnyű azt a benyomást kelteni, hogy a std::vector mindenre jó, és a láncolt tárolók csak tankönyvi maradványok. Ez téves. A standard sequence containerek között nem teljesítményrangsor van, hanem eltérő szerződések: más az iterátor-kategória, más az érvényességi (invalidation) szabály, más az elemenkénti tárolási költség, és más a memóriahozzáférés localityje. Ez az alfejezet a std::deque, a std::list és a std::forward_list szerződéseit rögzíti, és megmutatja, hogyan kell ezeket műveleti minta alapján megválasztani. A C-s láncolt listákról szóló rész (Láncolt és intrusive listák (13.2)) az explicit pointer- és ownership-modellt tanította; itt azt nézzük meg, mit garantál ebből a standard könyvtár, és mit nem.

28.3.1 A tárolóválasztás mint szerződés, nem Big-O verseny

Egy sequence container a C++ objektummodellben olyan objektum, amely azonos típusú elemek sorozatát tárolja, és legalább az alapműveleteket (begin/end, size, insert, erase, clear) meghatározott komplexitással és meghatározott érvényességi szabállyal nyújtja. A szerződésnek négy, egymástól független dimenziója van:

• komplexitás: műveletenként külön, és ahol a szabvány megengedi, amortizált és worst-case érték külön;
• iterátor-kategória: forward, bidirectional vagy random access — ez nem kényelmi kérdés, mert az algoritmusok és a std::sort előfeltételei ezen múlnak;
• érvényesség: mely művelet után mely iterátor, referencia és pointer marad használható;
• tárolási elrendezés és per-elem költség: folytonos-e, mennyi a node-overhead, hány allokáció történik műveletenként.

Egy elemre mutató T* vagy std::list<T>::iterator nem puszta cím, hanem időben kiterjesztett hivatkozás: az értéke addig használható, amíg a szerződés szerint érvényes. A konténer-választás ezért leggyakrabban arról szól, hogy kell-e ilyen hosszú életű hivatkozást tárolnunk egy másik adatszerkezetben (index, cache, eseményregiszter).

A Big-O önmagában félrevezet. A std::list középső beszúrása adott iterátorra $O(1)$, de ha az iterátort kereséssel kell megkeresni, a teljes művelet $O(n)$, és közben egy allokáció és két-három cache miss történik. A std::vector középső beszúrása $O(n)$ mozgatás, de az elmozdítás memmove-szerű, előre jelezhető mintázatú, ami néhány ezer elemig gyorsabb lehet. A döntést tehát a műveleti minta hozza: mit végzünk gyakrabban — bejárunk, véletlen hozzáférünk, végpontokon módosítunk, vagy hivatkozásokat őrzünk meg.

28.3.2 A std::deque blokkos tárolója

A std::deque<T> double-ended queue: random access sequence container, amelynek elülső és hátsó végén a beszúrás és a törlés amortizáltan konstans, és — ez a lényeg — nem folytonos. A tipikus implementáció egy pointerekből álló tömböt (a „map”-et) tart, amely fix méretű blokkokra mutat, a blokkokban pedig folytonosan helyezkednek el az elemek. A blokkméret implementációfüggő; a libstdc++ jellemzően 512 bájtos blokkot használ, illetve sizeof(T) > 512 esetén egy elemet blokkonként — ez implementációfüggő részlet, nem ISO-garancia.

Következmények:

• operator[], at, valamint az iterátoron végzett +=, - $O(1)$ — az iterátor-kategória random access;
• nincs data(), mert nincs mögöttes folytonos tömb; a deque tartalma nem adható át C API-nak;
• a deque nem rendelkezik reserve/capacity-vel, mert nem egyetlen tömböt növeszt;
• az iterátor több információt hordoz, mint egy pointer (blokk-hivatkozás és blokkon belüli index), ezért jellemzően nagyobb, mint egy T* — konkrét méret implementációfüggő;
• végponti beszúrásnál nem történik meg a meglévő elemek átmásolása, ezért a deque az egyetlen standard sequence container, amelynél a referenciák és pointerek érvényesek maradnak végponti beszúráskor.

Ez utóbbi a deque valódi indoka. Ha egy hosszú életű hivatkozást akarunk tartani egy olyan sor elemeire, amely mindkét végén nő, a vector erre nem alkalmas (reallokáció), a deque viszont igen — miközben az iterátorai ugyanekkor érvénytelenné válnak. Az iterátor és a referencia érvényessége itt élesen elválik, és ezt a két fogalmat soha nem szabad együtt kezelni.

// deque_ref.cpp -- C++20
#include <cassert>
#include <deque>

int main() {
    std::deque<int> d{1, 2, 3};
    int& r = d[1];      // referencia a 2-es elemre
    d.push_front(0);
    d.push_back(4);
    assert(r == 2);     // [ISO] a referencia érvényes marad
    assert(d.size() == 5);
    // Ugyanakkor a push_front/push_back UTÁN minden korábbi deque-iterátor
    // érvénytelen; a korábbi d.begin() nem használható tovább.
}

g++ -std=c++20 -Wall -Wextra -Wpedantic -O2 -o deque_ref deque_ref.cpp

A std::deque természetes felhasználása a munkasor, a csúszóablak és a korlátos puffer, ahol a fogyasztó elöl, a termelő hátul dolgozik, és a már kiosztott elemek címét meg akarjuk őrizni.

28.3.3 std::list és std::forward_list: node-tárolás

A std::list<T> kétszeresen láncolt lista, bidirectional iterátorral. A std::forward_list<T> egyszeresen láncolt, forward iterátorral, before_begin() sentinellel, insert_after/erase_after/splice_after műveletekkel — és nincs size() tagfüggvénye (a méret lekérése $O(n)$ bejárás). A std::list::size() ezzel szemben C++11 óta $O(1)$.

Egy csomópont (node) elvi tartalma x86-64 LP64 alatt:

Az itt szereplő számok illusztratív számítások, nem mért értékek: a konkrét fordítási profil, az ABI és a használt std::string implementáció nélkül a layout nem állítható. A lényeg a nagyságrend: a std::list<int> egy elemre nagyjából hatszor annyi processzmemóriát foglal, mint a std::vector<int>, és ehhez minden beszúrás egy külön allokációt indít.

A láncolt tárolók tényleges szerződéselőnye nem a komplexitás, hanem az érvényesség: beszúrás, törlés és splice nem invalidálja a többi elem iterátorát és referenciáját; csak a ténylegesen törölt elemeké válik érvénytelenné. Ez teszi lehetővé, hogy az iterátort hosszú életű hivatkozásként tároljuk például egy unordered_map értékében.

A splice a láncolt tároló saját művelete: csomópontok átkötése két lista között, elemek másolása és mozgatása nélkül. Egész lista és egyetlen elem átemelése konstans idő, feltéve hogy a két lista get_allocator() értéke egyenlő; eltérő allocator mellett ez a túlterhelés nem megengedett. A művelet nem allokál, és az átemelt elemek iterátorai, referenciái érvényesek maradnak — a cél itt az, hogy egy elem „áthelyezése” valóban $O(1)$ legyen, ne pedig egy csomópont-allokációs ciklus.

// fl.cpp -- C++20
#include <forward_list>
#include <iostream>
#include <string>

struct Entry { std::string path; bool stale; };

void drop_stale(std::forward_list<Entry>& xs) {
    xs.remove_if([](const Entry& e) { return e.stale; });
}

int main() {
    std::forward_list<Entry> xs{{"/a", false}, {"/b", true}, {"/c", false}};
    drop_stale(xs);
    for (const auto& e : xs) std::cout << e.path << '\n';  // várt: /a, /c
}

g++ -std=c++20 -Wall -Wextra -Wpedantic -O2 -o fl fl.cpp

A remove_if a forward_list esetében is $O(n)$ és egyetlen bejárás; a törlés az előd-mutatón keresztül történik, ezért nem kell külön iterátortömb.

28.3.4 Invalidációs táblázat

Az alábbi táblázat az ISO szerződést rögzíti; a std::vector referenciasora összehasonlításul szerepel.

Két gyakorlati következtetés. Egyrészt a deque-nél a végponti beszúrás után a T* és a T& újra felhasználható, de az iterator nem — a kettőt külön kell nyilvántartani. Másrészt a láncolt tárolóknál a stabilitás csak a meg nem szüntetett elemekre vonatkozik: ha a tárolót megszüntetjük, minden hivatkozás dangling lesz.

28.3.5 Allokátor, per-node költség és locality

A std::list és a std::forward_list minden beszúrása allokál (a splice kivétel), és minden törlése felszabadít. Ezért ezek a tárolók érzékenyek az allokátor sebességére: konténerenkénti egyedi allokátorral vagy arena/pool allokációval (Arena, pool és region lifetime (13.4)) a node-költség jelentősen csökkenthető. A deque ezzel szemben blokkonként allokál, tehát egy blokknyi elemre egy allokáció jut.

A locality szempont ellenkező irányba mutat: a láncolt lista bejárása minden elemnél új csomópontot érint, ami tipikusan cache miss, és a hardver prefetcher nem tud előreolvasni. A vector bejárása lineáris, előre jelezhető. A deque a kettő között van: blokkon belül folytonos és jól prefetchelhető, blokkváltásnál viszont ugrik.

Ebből következik a gyakorlati döntési minta:

• sok bejárás, kevés módosítás, kis elemek → vector;
• mindkét végén módosítás, referencia-stabilitás, C API-hoz nem kell folytonosság → deque;
• nagy elemek, garantált referencia-stabilitás, splice-alapú átrendezés → list;
• ugyanaz, de elég az előre iterálás és a hely a kritikus → forward_list.

28.3.6 Kidolgozott példa: LRU-sor splice-szal

A klasszikus eset, amikor a std::list nem Big-O, hanem érvényességi alapon nyer: LRU (least recently used) sor, amelyhez egy index társul. Az index iterátorokat tárol, és ezek akkor maradnak érvényesek, ha a listából csak splice-szal mozgatunk, illetve ha a beszúrás és a törlés a szerződés szerint nem invalidál.

// lru_list.cpp -- C++20, Linux, x86-64
#include <cstddef>
#include <iostream>
#include <list>
#include <stdexcept>
#include <string>
#include <unordered_map>

struct Session {
    std::string id;
    int hits = 0;
};

class LruSessions {
public:
    explicit LruSessions(std::size_t capacity) : capacity_(capacity) {
        if (capacity_ == 0)
            throw std::invalid_argument("LruSessions: capacity must be > 0");
    }

    // Az index a saját lista csomópontjaira mutató iterátorokat tárol.
    // Tagonkénti másolásnál a másolat indexe az EREDETI listába mutatna,
    // ezért a másolás tiltott. A mozgatás biztonságos: a std::list
    // mozgatása a csomópontokat viszi át, az iterátorok érvényesek maradnak.
    LruSessions(const LruSessions&) = delete;
    LruSessions& operator=(const LruSessions&) = delete;
    LruSessions(LruSessions&&) noexcept = default;
    LruSessions& operator=(LruSessions&&) noexcept = default;

    // Erős garancia: ha bármelyik allokáció dob, a lista és az index
    // változatlan, és továbbra is ugyanazokat az azonosítókat tartalmazza.
    Session& touch(const std::string& id) {
        auto it = index_.find(id);
        if (it == index_.end()) {
            items_.push_front(Session{id, 0});        // 1. dobhat: semmi nem változott
            auto pos = items_.begin();
            try {
                index_.emplace(id, pos);               // 2. dobhat: ...
            } catch (...) {
                items_.pop_front();                    // ...visszagörgetjük az 1. lépést
                throw;
            }
            if (items_.size() > capacity_) {           // 3. kilakoltatás a commit után:
                index_.erase(items_.back().id);        //    std::hash<std::string> nem dob,
                items_.pop_back();                     //    erase/pop_back nem allokál
            }
            return *pos;
        }
        // splice: nem allokál, nem mozgat, nem invalidál
        if (it->second != items_.begin())
            items_.splice(items_.begin(), items_, it->second);
        it->second->hits += 1;
        return *it->second;
    }

    std::size_t size() const { return items_.size(); }

    // Teszteléshez: a két tároló ugyanazokat az azonosítókat tartalmazza-e.
    bool consistent() const {
        if (items_.size() != index_.size() || items_.size() > capacity_) return false;
        for (auto i = items_.begin(); i != items_.end(); ++i) {
            auto f = index_.find(i->id);
            if (f == index_.end() || f->second != i) return false;
        }
        return true;
    }

private:
    std::size_t capacity_;
    std::list<Session> items_;   // legutóbb használt elöl
    std::unordered_map<std::string, std::list<Session>::iterator> index_;
};

int main() {
    LruSessions lru{3};
    lru.touch("a");
    lru.touch("b");
    lru.touch("a");   // "a" előre; az indexben tárolt iterátor érvényes marad
    lru.touch("c");
    lru.touch("d");   // "b" esik ki (legrégebben használt)
    std::cout << "size=" << lru.size() << '\n';   // várt: size=3
}

g++ -std=c++20 -Wall -Wextra -Wpedantic -O2 -o lru_list lru_list.cpp && ./lru_list

Az LruSessions két tagja, a lista és az index, nem független: az index a saját lista csomópontjaira mutató iterátorokat tárol. Ezért a tagonkénti (implicit) másolás hibás lenne: a másolat listája új csomópontokat kapna, az indexe viszont az eredeti lista iterátorait. A másolat első splice-a vagy kiesése az eredeti lista csomópontjait módosítaná. A típus ezért a másolást explicit tiltja (= delete). A mozgatást megtartja, mert a std::list mozgatása a csomópontokat adja át, így a tárolt iterátorok érvényesek maradnak, és most már a cél listájába mutatnak. Ha értékszemantikájú másolás kellene, a másoló konstruktornak a lista lemásolása után a másolat saját iterátoraiból kellene újraépítenie az indexet. A nulla kapacitást a konstruktor elutasítja: a referenciát visszaadó touch API-val egy „semmit meg nem őrző” cache nem fogalmazható meg értelmesen, mert nem lenne elem, amelyre a visszaadott referencia mutathat.

A touch új kulcsnál tranzakcióként kezeli a két tárolót. Először a listába szúr (1. lépés, dobhat — ekkor semmi nem változott), majd az indexbe (2. lépés, dobhat — ekkor visszagörgeti az 1. lépést), és csak a sikeres beszúrás után lakoltatja ki a legrégebbi elemet (3. lépés: index_.erase a std::hash<std::string> miatt nem dob, a pop_back nem allokál). Így a kapacitás átmenetileg eggyel túlléphető, cserébe a művelet erős garanciát ad: kivétel után a lista és az index ugyanazokat az azonosítókat tartalmazza, és egyetlen régi elem sem vész el. A korábbi „előbb kilakoltat, aztán beszúr” sorrend kivételnél elveszítette a kilakoltatott elemet, a beszúrás utáni dobás pedig indexeletlen listacsomópontot hagyott.

Buildjegyzőkönyv (lab-gcc profil). A program figyelmeztetés nélkül fordult, a kimenete size=3. Egy külön tesztprogram (lru_test.cpp) a main nélküli osztályt használja: a 0 kapacitást elutasítottnak, az 1 és a 3 kapacitást konzisztensnek találta, majd egy lecserélt globális operator new-val teli cache-be szúrt új, SSO-n túli kulcsot úgy, hogy rendre minden allokációs pont egyszer dobjon. Mind a 4 injektált kivétel után a consistent() igaz volt és a méret 3 maradt (kimenet: injected=4 consistent=1). A régi sorrenddel ugyanez a teszt az első injektálásnál lru.size() == 3 assert-hibával állt le. (A malloc/free-re épülő operator new csere miatt a GCC 13 -Wmismatched-new-delete hamis pozitív figyelmeztetést ad; a tesztet -Wno-mismatched-new-delete-tel fordítottuk.) A javítás előtti, implicit másolást engedő változatban egy másolat touch hívása -D_GLIBCXX_DEBUG mellett attempt to compare iterators from different sequences hibával állt le. A javított változatban egy LruSessions b = a; sor use of deleted function fordítási hibát ad. A mozgató konstrukció és értékadás után a cél tovább használható; ezt -D_GLIBCXX_DEBUG és ASan/UBSan mellett is hibátlanul futtattuk.

Az ownership-térkép: a Session objektumok tulajdonosa az items_ lista; az index_ nem tulajdonol, csak nem tulajdonló hivatkozást (iterátort) őriz. Az invalidáló művelet, amelytől tartózkodni kell, a list::erase/pop_back azon elemre, amelynek iterátorát az indexben tároljuk — ezért a sorrend mindig „index törlése, majd node törlése”. Ha valaki itt std::vector-ra cserélné a listát, a push_front miatt minden tárolt iterátor azonnal érvénytelenné válna, és a hiba csak jóval később, dangling olvasásként jelentkezne.

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

• „A list gyorsabb, mert O(1) a beszúrás.” A kereséssel együtt a beszúrás $O(n)$, plusz allokáció és cache miss. Javítás: a műveleti minta rögzítése, majd mérés a saját terhelésen.
• Iterátor és referencia összekeverése a deque-nél. push_back után a T& érvényes, az iterator nem. Javítás: a kétféle hivatkozást külön típusban és külön névvel tároljuk.
• &v[i] eltárolása, majd v.push_back. Reallokáció esetén dangling pointer. Javítás: index tárolása pointer helyett, vagy std::deque.
• std::sort(list.begin(), list.end()). Nem fordul le: a std::sort random access iterátort igényel. Javítás: list::sort használata.
• forward_list::erase_after(it) félreértése. Az it az előző elemre mutat; az első elemhez before_begin() kell.
• Különböző allocatorú listák között splice. A standard ezt az esetet nem engedi meg. Javítás: azonos allocator-típus és -példány használata.
• deque::data() feltételezése. Nincs ilyen tag; a deque nem folytonos.

28.3.8 Összefoglaló

A std::deque blokkos, nem folytonos random access tároló: végponti beszúrásra referenciát stabilan tart, iterátort nem. A std::list és std::forward_list node-alapú tároló, ahol a beszúrás, törlés és splice nem invalidálja a többi elem iterátorát és referenciáját — ez a tényleges szerződéselőny, nem a Big-O. Az árat a csomópontonkénti allokáció, a per-node overhead és a gyenge locality jelenti. A választás ezért mindig a műveleti minta, az iterátor-kategória és a szükséges érvényességi szint együttes vizsgálatából születik; a konténerek közötti döntés részletes ellenőrzését a Tárolóválasztási és invalidációs labor (28.6) laborja gyakoroltatja.

28.3.9 Feladatok

1. feladat (magyarázó). Adott egy std::deque<int> d és egy std::vector<int> v. Mindkettőre elvégzünk egy push_back-et, és korábban eltároltuk az első elemre mutató int*-ot. Melyik esetben marad a pointer érvényes, és melyik esetben nem, feltéve hogy a vector kapacitása betelt? Fogalmazd meg a szabályt iterátorra és referenciára külön.

2. feladat (kódolási). Egészítsd ki az LRU-példát egy evict_all() tagfüggvénnyel, amely kiüríti a tárolót, és egy contains(id) függvénnyel. Indokold, milyen sorrendben kell az index_ és az items_ tartalmát törölni, és mi történne fordított sorrendben.

3. feladat (diagnosztikai). Egy szolgáltatás eseménynaplója std::list<Event>-ben tárolódik; a profil azt mutatja, hogy a processzoridő nagy része a napló bejárásában telik, a beszúrások száma viszont elhanyagolható. Fogalmazz meg egy mérési tervet, majd egy cserét, és add meg, milyen szerződést kell feladni a cserével.

28.3.10 Megoldások

1. megoldás. A deque esetében a push_back végponti beszúrás: az ISO szerződés szerint minden iterátor érvénytelenné válik, de a meglévő elemekre mutató referenciák és pointerek érvényesek maradnak, mert a meglévő elemek nem mozdulnak el. A vector esetében, ha a push_back reallokációt vált ki, mind az iterátorok, mind a referenciák és pointerek érvénytelenné válnak; ha a kapacitás elegendő, csak a past-the-end iterátor válik érvénytelenné, a referenciák nem. Az általános szabály tehát: az iterátor és a referencia érvényessége külön szerződés, és a deque az az eset, ahol a kettő végponti beszúrásnál elválik. Ellenőrzési feltétel: a válasz nevezze meg a tárolót, a műveletet és azt, hogy történt-e újraallokáció.

2. megoldás. Az evict_all()-ban először az index_.clear(), majd az items_.clear() hívandó. Indoklás: az index_ iterátorokat tárol nem tulajdonló hivatkozásként; ha előbb az items_-et ürítenénk, az indexben dangling iterátorok maradnának, és bár a clear() azokat már nem dereferálja, a sorrend megfordítása egy későbbi módosításnál (például egy feltételes törlésnél) már valódi hibát okozhat. A tulajdonos mindig előbb szabadítja fel a nem tulajdonló nézeteket. A contains(id) egyszerűen index_.find(id) != index_.end(), $O(1)$ átlagos esetben. Ellenőrzési feltétel: a kód forduljon -Wall -Wextra -Wpedantic mellett figyelmeztetés nélkül, és az evict_all() után a size() nulla.

3. megoldás. A mérési terv: rögzített fordítási profil és flags mellett (például g++ -std=c++20 -O2), azonos bemeneti eseményszámmal mérjük a bejárás idejét, és külön számoljuk az allokációkat egy számláló allokátorral; a mérés nem helyettesíthető becsléssel. A csere: std::vector<Event>, ha a napló csak a végére fűz, és nincs szükség referencia-stabilitásra. A feladott szerződés: a beszúrás amortizáltan konstans marad, de reallokációkor minden korábbi iterátor és referencia érvénytelenné válik, és a középső törlés $O(n)$ lesz. Ha a naplóba bárhonnan törölni kell, és a törölt elemekre mutató hivatkozást máshol tárolunk, a vector nem elfogadható; ekkor std::list marad, de a bejárást kell átalakítani (például gyorsítótárazott összesítéssel), nem a tárolót cserélni. Ellenőrzési feltétel: a döntés nevezze meg a feladott garanciát, és a mérési terv tartalmazzon összehasonlítható alapvonalat.