37.1 Allocator model és allocator_traits

A könyv eddigi részei a helyességet állították előtérbe: a std::vector érvényességi szerződéseit (std::array, std::vector és folytonos tárolás (28.1)), a tároló újrafelhasználásának objektumszabályait (Tároló újrafelhasználása és C++ objektumszabályok (20.6)) és a fordítási idejű típusvizsgálat eszközeit (Type traits, tag dispatch és if constexpr (27.1)) már ismered. Most ugyanazt a tárolót költségoldalról nézzük meg. A kiindulópont az, hogy a standard tárolók nem „memóriát foglalnak”, hanem két külön fázisra bontják a munkát: egy allokátoron keresztül tárolóterületet (storage) szereznek, majd azon belül objektumokat hoznak létre és semmisítenek meg. Ez a szétválasztás teszi lehetővé a visszagörgethető hibakezelést, a költség mérését és azt, hogy az erőforrás mögötti memóriarezsimot kicseréljük anélkül, hogy a tároló típusát vagy az algoritmusokat újraírnánk. Az alábbiakban ezt a szerződést bontjuk ki, majd megmutatjuk, hogy a move és a swap költsége nem a tárolótól, hanem az allokátor egyenlőségétől és propagation tulajdonságaitól függ. A fejezet határozottan nem benchmarkfejezet: itt cost modellt állítunk fel, amit a későbbi, mérési fejezet validál.

37.1.1 A szerződés: tárolás és objektum-élettartam szétválasztása

Allokátor (allocator) alatt olyan típust értünk, amely megfelel a standard allokátorkövetelményeinek: képes n darab T típusú objektum számára megfelelően igazított, inicializálatlan tárolóterületet szerezni, azt visszaadni, és egyenlőség szempontjából összehasonlítható. Az allokátor nem hoz létre objektumot. Ez a C++20 alapban már nyelvi szinten is látszik: a std::allocator<T>::construct és destroy tagok a C++17-es elavulás után kikerültek a szabványból.

A teljes életciklus négy, egymástól elkülönülő lépésből áll, ahol p = traits::allocate(a, n):

1. Tárolószerzés. A p egy n * sizeof(T) méretű, T-re igazított, inicializálatlan területre mutat. Ezen a ponton nincs T objektum: ha bármit is „olvasnál” belőle, az nem definiált viselkedés.
2. Konstrukció. traits::construct(a, p + i, args...) elindítja az i-edik objektum élettartamát. Az allokátor itt csak tanácsadó szerepet játszhat: az allocator_traits a helyettesítő construct-ot akkor hívja, ha az allokátornak van ilyen tagja, különben placement new-t használ.
3. Destrukció. traits::destroy(a, p + i) lezárja az élettartamot; a tároló ettől kezdve újra „csak” nyers terület.
4. Felszabadítás. traits::deallocate(a, p, n) visszaadja a területet. Ennek nem szabad dobnia.

Ebből az következik, hogy az allocate és a construct közötti rés a tároló visszagörgetési pontja. Ha a konstrukció közben kivétel jön, a tároló a már létrehozott elemeket destruálja, majd a területet felszabadítja – ehhez viszont tudnia kell, meddig jutott, és azt, hogy a felszabadítás az ugyanazzal az allokátorral történik. Innen ered a deallocate(p, n) szerződése: ugyanaz az n, és egy olyan allokátorpéldány, amely egyenlő az allokálóval. A részletes objektum-újrafelhasználási szabályokat (placement new, std::launder, élettartamhatárok) a Tároló újrafelhasználása és C++ objektumszabályok (20.6) tárgyalja; itt csak annyit rögzítünk, hogy az allokátor soha nem lép ezek helyébe.

37.1.2 allocator_traits és a rebind mechanizmus

A std::allocator_traits<A> egy fordítási idejű adaptor: az A típusból kiolvassa a szükséges tagokat, a hiányzókat pedig alapértelmezéssel pótolja. Ez teszi lehetővé, hogy egy minimális allokátornak mindössze a value_type, az allocate, a deallocate és az egyenlőség legyen megvalósítva:

// minimal_allocator.cpp — C++20, csak szemléltetés
#include <cstddef>
#include <new>

template <class T>
struct minimal_allocator {
    using value_type = T;

    T* allocate(std::size_t n) {
        return static_cast<T*>(::operator new(n * sizeof(T)));
    }
    void deallocate(T* p, std::size_t) noexcept { ::operator delete(p); }

    template <class U>
    bool operator==(const minimal_allocator<U>&) const noexcept { return true; }
    template <class U>
    bool operator!=(const minimal_allocator<U>&) const noexcept { return false; }
};

Az alapértelmezések, amelyeket az allocator_traits pótol: pointer (A::pointer, különben value_type*), difference_type, size_type, a három propagate_on_* trait (false_type), valamint az is_always_equal (std::is_empty<A>). Ez utóbbi nem kozmetika: ha fordítási időben tudható, hogy minden példány egyenlő, a tároló az allokátor-összehasonlítást és a feltételes ágakat ki tudja ejteni.

A rebind az a leképezés, amely egy T-re paraméterezett allokátort egy másik U típusra állít elő: allocator_traits<A>::rebind_alloc<U>. A szabványos megvalósítás az A::rebind<U>::other tagot használja, ha létezik, különben a template<class> class A formából képzi. Miért kell? Mert a tároló soha nem az int-et allokálja közvetlenül a csomópont-alapú esetekben: a std::list<int, std::allocator<int>> a belső csomóponttípusra bindol, a std::map pedig a std::pair<const K, V>-t tartalmazó csomópontra. A felhasználó által megadott allokátor így is „ugyanaz” marad, csak más elem-típusra.

37.1.3 Egyenlőség, propagation és a move assignment költsége

Az allokátorok egyenlőségének szemantikai definíciója van: a1 == a2 pontosan akkor, ha az a1-gyel megszerzett tároló felszabadítható a2-vel. Ez nem pointer-összehasonlítás, hanem szerződés a memóriarezsim azonosságáról. Állapot nélküli allokátornál mindig igaz; állapotossal (arena, pool, shared memory szegmens) a rezsim azonosítóját kell összehasonlítani.

A propagation trait-ek azt mondják meg, hogy egy tárolószintű művelet átvegye-e a másik tároló allokátorát:

• propagate_on_container_copy_assignment (POCCA) – copy assignment,
• propagate_on_container_move_assignment (POCMA) – move assignment,
• propagate_on_container_swap (POCS) – swap.

Mindhárom alapértéke false_type: az allokátor „ragad” a tárolóhoz, nem vándorol vele.

37.1.3.1 A move assignment esetei

Legyen a1 a cél-, a2 a forrás-tároló allokátora. A v1 = std::move(v2) három ágra bomlik, és a költség gyökeresen más:

1. POCMA igaz. A cél átveszi a forrás allokátorát (a1 = std::move(a2)), és a puffert is átveszi. Nincs új allokáció, nincs elem-mozgatás.
2. POCMA hamis, de a1 == a2. A puffer átvehető, mert a felszabadítást majd a1 is elvégezheti. Az allokátor marad. Szintén nincs új allokáció.
3. POCMA hamis és a1 != a2. A puffer nem vehető át: a forrás tárolója a2-vel allokálódott, a cél majd a1-gyel szabadítaná fel, ami érvénytelen. Ezért a cél a saját allokátorával új tárolót szerez, az elemeket egyenként átmozgatja, a forrás elemeit destruálja és a forrás pufferét felszabadítja.

A cost model tehát, ahol n a forrás elemszáma:

$$\text{költség} \;=\; \underbrace{O(n)}_{\text{régi elemek destruktora}} \;+\; \begin{cases} O(1) & \text{1–2. eset: pufferátvétel}\\[2pt] O(n) + \text{1 allokáció} & \text{3. eset: elem-mozgatás} \end{cases}$$

A 3. esetben a forrás elemei moved-from állapotban maradnak, a forrás tároló pedig továbbra is érvényes, de nem specifikált tartalmú. Fontos feltétel: ez az ág csak akkor értelmezhető, ha T mozgatható (MoveInsertable). A kivételgarancia szintje T move konstruktorának noexcept voltától és az implementációtól függ; ezt ne feltételezd, hanem a T szerződésének részeként kezeld. A pontos megfogalmazást a választott szabványverzió szövegében ellenőrizd – ez a rész verziófüggő részlet.

37.1.3.2 A swap szigorúbb feltétele

A swap itt nem költség-, hanem érvényességi kérdés. Két tároló swap-je akkor definiált, ha POCS igaz, vagy a két allokátor egyenlő. Ha mindkettő hamis, a viselkedés nem definiált. Ezért a generikus kódban soha ne swap-elj olyan tárolókat, amelyek allokátorát nem te irányítod: a hiba nem lassulás, hanem UB.

37.1.4 Az allokátorpéldány élettartama és tulajdonlása

A tároló a konstruktorában kapott allokátorról másolatot tárol (get_allocator() is másolatot ad). Ez a példány a tárolóval együtt jön létre, és a tároló destruktorában utolsóként szűnik meg – a szabvány garantálja, hogy az allokátor addig él, amíg a tároló használja. Copy construction esetén a select_on_container_copy_construction dönt arról, milyen allokátort kap az új tároló (alapértelmezésben ugyanazt).

A lényeg: az allokátorpéldány fogantyú, nem az erőforrás. Ha az allokátor egy arena*-ot vagy memory_resource*-ot tart, akkor az arena élettartama a felhasználó felelőssége. Ha az arena előbb szűnik meg, mint a tároló, a tároló destruktora egy már felszabadított rezsimen hív deallocate-ot: nem definiált viselkedés, tipikusan csendes memoria-korrupció. A tároló csak a sorrendet garantálja (előbb elemek, aztán terület, végül az allokátor másolata), az arena tulajdonjogát nem. Ugyanez a szerződés öröklődik a std::pmr világba (pmr, memory_resource és region lifetime (37.2)): a polymorphic_allocator egy memory_resource*-ot csomagol, és a resource élettartama végig a hívóé.

37.1.5 Fancy pointer és scoped allocator: fogalmi térkép

A allocator_traits<A>::pointer nem kötelezően nyers pointer: lehet osztálytípus, amely kielégíti a NullablePointer követelményt, folytonos tárolónál pedig a random access iterator követelményt. Ezek a fancy pointer-ek. Klasszikus indokuk a shared memory: egy offset_ptr eltolást tárol cím helyett, így a mutató érvényes marad, ha a szegmens más címre mappelődik. Korlát: a folytonos tárolók data()-ja T*-ot ad vissza, ezért a fancy pointer gyakorlatban főleg csomópont-alapú tárolóknál és saját adaptereknél jelenik meg – ez implementációfüggő részlet, amit a konkrét standard library verzióján kell ellenőrizni.

A std::scoped_allocator_adaptor egy allokátor-adaptor, amely a külső allokátort „besugározza” a belső tárolókba: egy vector<vector<T, A>, A> belső vektorai is a külső allokátorral (vagy annak megadott belső párjával) épülnek fel, uses_allocator konstrukción keresztül. Így a beágyazott szerkezet egyetlen memóriarezsimen marad. A fogalmi térkép: külső rezsim → scoped_allocator_adaptor → belső tárolók, ahol a propagation trait-ek itt is ugyanazt a kérdést teszik fel, csak egy szinttel beljebb.

37.1.6 Kidolgozott példa: egyenlőtlen allokátorú move assignment

Az alábbi program állapotos allokátort használ, naplózza az allocate/deallocate hívásokat, és megszámolja az elem-mozgatásokat. A két tároló allokátora szándékosan nem egyenlő, POCMA pedig hamis.

// alloc_move.cpp — C++20, GCC/Clang
#include <cstddef>
#include <cstdio>
#include <memory>
#include <type_traits>
#include <utility>
#include <vector>

struct Tracked {
    int value = 0;
    static inline int moves = 0;
    static inline int copies = 0;

    Tracked() = default;
    explicit Tracked(int v) : value(v) {}
    Tracked(const Tracked& o) : value(o.value) { ++copies; }
    Tracked(Tracked&& o) noexcept : value(o.value) { ++moves; }
    Tracked& operator=(const Tracked&) = default;
    Tracked& operator=(Tracked&&) noexcept = default;
};

template <class T>
struct tagged_allocator {
    using value_type = T;
    using propagate_on_container_move_assignment = std::false_type; // POCMA
    using propagate_on_container_swap = std::false_type;           // POCS
    using is_always_equal = std::false_type;

    int id = 0;

    tagged_allocator() noexcept = default;
    explicit tagged_allocator(int i) noexcept : id(i) {}
    template <class U>
    tagged_allocator(const tagged_allocator<U>& o) noexcept : id(o.id) {}

    T* allocate(std::size_t n) {
        std::printf("  allocate(%zu) id=%d\n", n, id);
        return static_cast<T*>(::operator new(n * sizeof(T)));
    }
    void deallocate(T* p, std::size_t n) noexcept {
        std::printf("  deallocate(%zu) id=%d\n", n, id);
        ::operator delete(p);
    }

    template <class U>
    bool operator==(const tagged_allocator<U>& o) const noexcept { return id == o.id; }
    template <class U>
    bool operator!=(const tagged_allocator<U>& o) const noexcept { return id != o.id; }
};

int main() {
    using Vec = std::vector<Tracked, tagged_allocator<Tracked>>;

    Vec src(tagged_allocator<Tracked>{1});
    src.reserve(4);                 // egyetlen allokáció, nincs reallokáció
    src.emplace_back(1);
    src.emplace_back(2);
    src.emplace_back(3);

    Tracked::moves = Tracked::copies = 0;

    Vec dst(tagged_allocator<Tracked>{2});
    dst = std::move(src);           // egyenlőtlen allokátor + POCMA=false

    std::printf("elem-mozgatas=%d, masolas=%d, dst meret=%zu\n",
                Tracked::moves, Tracked::copies, dst.size());
}

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

g++ -std=c++20 -O2 -Wall -Wextra -pedantic alloc_move.cpp -o alloc_move
# vagy
clang++ -std=c++20 -O2 -Wall -Wextra -pedantic alloc_move.cpp -o alloc_move

A várt kimenet (illusztráció, ezt a szöveg írásakor nem futtattam): a dst = std::move(src) három allocate(4) id=2 típusú sort és három elem-mozgatást mutat, mivel a harmadik ág futott. Ha a POCMA-t std::true_type-ra állítod, az elem-mozgatás eltűnik, és a dst allokátora a forrás id=1 értékét veszi át – a puffer átkerül, a régi pedig a forrás destruktorában szabadul fel. Ez a két futtatás együtt pontosan a fenti cost model két ágát demonstrálja; a mérést a mérési fejezet végzi el, itt a mechanizmus a tanulság.

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

• Az allocate-ot objektum-létrehozásnak tekinteni. A visszakapott területen nincs T; olvasása UB. Javítás: mindig a konstrukció/destrukció fázisát használd, és ne nyúlj a nyers területhez.
• Az allokátor élettartamát összekeverni az erőforrás élettartamával. Az arena előbb megszűnik, mint a tároló → UB a destruktorban. Javítás: az erőforrás legyen kimondottan hosszabb életű (pl. a main-ben vagy a szolgáltatás-szintű kontextusban).
• Azt hinni, hogy a move assignment mindig O(1). Állapotos, nem propagáló allokátornál O(n) plusz allokáció. Javítás: a szerződés részeként dokumentáld az allokátor tulajdonságait.
• Egyenlőtlen, nem propagáló allokátorú tárolókat swap-elni. Ez nem lassabb, hanem UB. Javítás: POCS bekapcsolása, vagy az allokátorok egyenlővé tétele.
• Az allocator_traits megkerülése. A közvetlen a.allocate/a.construct hívás kihagyja az alapértelmezéseket és a testreszabási pontokat. Javítás: mindig a traits:: utat használd.
• Azt hinni, hogy a std::allocator „zero-cost” garancia. Ez legfeljebb egy adott implementáció és optimalizálási szint megfigyelése, nem szerződés.

37.1.8 Összefoglaló

Az allokátor modell két dolgot választ el, amit a legtöbb magas szintű nyelv összemos: a tárolóterület megszerzését és az objektum élettartamának elindítását. Az allocator_traits adja azt a kompatibilitási réteget, amely miatt egy minimális allokátor is elég, a rebind pedig azt, hogy a tároló a belső típusaira is ugyanazt a rezsimet használja. Az egyenlőség szemantikai fogalom (felszabadítható-e a tároló a másikkal), a propagation trait-ek pedig azt döntik el, hogy az allokátor vándorol-e a tárolóműveletekkel. Ennek közvetlen következménye a move assignment három ága és a swap érvényességi feltétele. Végül: az allokátorpéldány fogantyú; a mögötte lévő memóriarezsim élettartama a felhasználóé.

37.1.9 Feladatok

1. (Magyarázó) Egy std::vector<T, A>-n végrehajtod a push_back sorozatot, amely egy reallokációt okoz. Nevezd meg, mely lépésekben történik allocate, construct, destroy és deallocate, és indokold, miért ebben a sorrendben.
2. (Kódolási) Módosítsd a kidolgozott példa allokátorát úgy, hogy POCMA std::true_type legyen. Add meg a várható kimenet alakját, és fogalmazd meg az ellenőrzési feltételt, amivel a laborban igazolod, hogy a harmadik ág helyett az első futott.
3. (Diagnosztikai) Egy kollégád kódjában két std::vector-t swap-elnek, amelyek allokátora különböző id-jű, POCS pedig hamis. A program „néha összeomlik”. Azonosítsd a hibát, és adj két különböző javítást, megnevezve mindkettő mellékhatását.

37.1.10 Megoldások

1. A push_back új kapacitást igényel: a tároló allocate(new_cap)-pal új területet szerez (ekkor még nulla elem él rajta), majd a meglévő elemeket construct-tal átmozgatja az új területre, ezután a régieket destroy-jal lezárja, végül deallocate(old_ptr, old_cap)-pal visszaadja a régi területet. Azért ez a sorrend, mert a régi pufferre a másolás/mozgatás befejezéséig szükség van, a felszabadítás pedig csak akkor érvényes, ha már egyetlen objektum élettartama sem függ tőle. Ellenőrzési feltétel: a naplóban az új allokáció sorszáma megelőzi a régi felszabadításét, és allocate/deallocate száma páronként egyezik.

2. A propagate_on_container_move_assignment típust std::true_type-ra állítva a move assignment első ága fut: a puffer átkerül, a dst allokátora a forrás allokátorává válik, elem-mozgatás nem történik. Várható kimenet: a három allocate sor helyett legfeljebb a src.reserve(4) allokációja jelenik meg, elem-mozgatas=0. Ellenőrzési feltétel: a Tracked::moves nulla, és a dst.get_allocator().id == 1 (a forrás azonosítója). Megjegyzés: a dst destruktora ekkor már id=1-gyel szabadít fel, ami összhangban van azzal, hogy a puffert is az az allokátor adta.

3. A hiba az, hogy a swap előfeltétele nem teljesül: POCS hamis és az allokátorok nem egyenlők, ezért a viselkedés nem definiált – innen a látszólag véletlenszerű összeomlás. Javítás A: állítsd a POCS-t std::true_type-ra, ekkor a swap legálisan kicseréli az allokátorokat is; mellékhatása, hogy a tárolók allokátora a művelet után megváltozik, amit a további kódnak tolerálnia kell. Javítás B: tedd egyenlővé az allokátorokat (azonos rezsim), ekkor POCS hamis mellett is definiált a művelet; mellékhatása, hogy a két tároló ugyanarra a memóriarezsimre kerül, így elveszik a szigetelés, amiért eredetileg külön allokátort használtál. Mindkét javításnál ellenőrzési feltétel, hogy a swap után bármelyik tároló destruktora a saját (vagy a propagált) allokátorával szabadít fel, és a felszabadítások száma páros.