28.1 std::array, std::vector és folytonos tárolás

A C dinamikus tömb mintáját——T *buf, size_t len, size_t cap és a hozzá tartozó kézi free——a Dinamikus tömb és string builder részben már felépítettük. A standard tárolók ugyanezt a hármast kínálják, de a mérethatárokat, az elemek élettartamát és a hibakezelést típusba kódolják. Ez a rész azt tanítja meg, hogyan válasszunk std::array és std::vector között, és hogyan döntsük el minden mutáció előtt, hogy mely pointer, referencia és iterator marad érvényes. A folytonos tárolás nem esztétikai kérdés: ez teszi lehetővé, hogy egy std::vector tartalmát változtatás nélkül adjuk át C API-nak, read/write rendszerhívásnak vagy egy bináris protokoll szerializálójának. A szerződés másik oldala viszont az, hogy a folytonosság és az újraelosztás együtt mozog: amint a vektor kinő egy allokációt, a korábbi data() pointer nem követi a tulajdonost.

28.1.1 std::array: fix méret és értékszemantika

A std::array<T, N> pontosan N darab T típusú elemet tartalmazó aggregate. Az N fordítási idejű konstans, a méret a típus része, és az objektum nem konvertálódik pointerré, ahogyan a C tömb függvényparaméterként elsöprűnik pointerré. Az std::array értékszemantikát ad: másoláskor minden elem másolódik, értékadáskor minden elem felülíródik. Ez a C tömbbel szemben a legfontosabb különbség, mert így a fix méretű puffer átadható érték szerint, visszaadható függvényből, és beágyazható más struktúrába anélkül, hogy elveszne a hossz.

A méretgarancia azonban nem jelent bitre pontos layout-garanciát. A sizeof(std::array<T, N>) tipikusan N * sizeof(T), de a szabvány ezt nem írja elő; padding és belső elrendezés implementációfüggő lehet. A data() pointert ad az első elemre, a size() pedig fordítási idejű konstans, így az std::array kitűnő választás fix protokollfejlécekhez, hardverregiszter-tükrökhöz és olyan bufferokhoz, amelyek mérete a típusban él. Az N = 0 megengedett speciális eset: ilyenkor size() == 0, begin() == end(), és a data() értéke nem használható dereferálásra.

Egy inicializálási csapda rendszeresen visszatér. A std::array<int, 3> a; default-inicializálja az aggregate-et, de az int elemek így indeterminált értékűek lesznek; olvasásuk nem definiált viselkedés. A std::array<int, 3> a{}; value-initializál, tehát minden elem nulla lesz. Ugyanez a különbség a std::vector-nál is megjelenik, csak ott a resize és a push_back teszi láthatóvá. Ha a fix méretű tömböt függvénynek adjuk át, referenciát használjunk, különben a teljes tömb másolódik:

#include <array>
#include <cstddef>
#include <cstdint>
#include <cstdio>

void dump(const std::array<std::uint8_t, 4>& magic) {
    for (std::uint8_t b : magic) {
        std::printf("%02x ", static_cast<unsigned>(b));
    }
}

int main() {
    std::array<std::uint8_t, 4> magic{0x7f, 'E', 'L', 'F'};
    dump(magic);
    std::printf("size=%zu\n", magic.size());
}

A magic.size() típusa std::size_t, értéke fordítási idejű konstans, és a dump belsejében a magic.size() ugyanúgy 4, mint a hívó oldalon. Ez az a tulajdonság, amit a C tömb elveszít, amikor paraméterként pointerré alakul.

28.1.2 std::vector: méret, kapacitás és konstruált elemek

A std::vector<T> három számot tart nyilván, és a programozási hibák nagy része abból fakad, hogy ezeket összekeverjük. A size() a konstruált elemek száma: a [0, size()) indexű elemek léteznek, és mindegyikre lefutott a konstruktor. A capacity() a jelenlegi allokációban elférő elemek száma; a capacity() >= size() mindig teljesül, és a size() és capacity() közötti tartomány nyers tároló, ahol nem él T objektum. A max_size() elméleti felső korlát, a data() pedig az első elemre mutató pointer, amely üres vektornál lehet null is, de semmiképpen nem dereferálható. A folytonosság garantálja, hogy &v[i] == v.data() + i, és C++20-ban a vector::iterator contiguous iterator kategóriát modellez.

A C-s buf/len/cap hármashoz képest a döntő különbség a len és cap közötti rész státusza. C-ben a lefoglalt byte-ok mindegyike használható tároló, csak a len-en túli rész tartalma definiálatlan. C++-ban a size() és capacity() közötti memória nem tartalmaz T objektumot, ezért ott T-t olvasni vagy írni nem lehet. Ezért nem helyes a v.capacity()-t „kihasználható elemek számaként” kezelni, és ezért nem lehet a reserve után indexelni.

A reserve(n) csak a kapacitást érinti: ha n > capacity(), új tárolót foglal legalább n elemre, áthelyezi a meglévő elemeket, és minden pointert, referenciát és iterátort invalidál. Ha n <= capacity(), nem csökkent, nem konstruál elemeket, és a size() változatlan. A reserve tehát nem ad elemeket; a v.reserve(8); v[0] = 1; nem definiált viselkedés, mert a size() még nulla. A resize(n) ezzel szemben tényleg elemeket hoz létre vagy szüntet meg: növeléskor value-initializált (vagy megadott értékű) elemekkel bővül a vektor, csökkentéskor a végső elemek destruálódnak. A resize kisebbre állítás után sem csökken a capacity(); a shrink_to_fit() erre tesz kísérletet, de nem kötelező, hogy ténylegesen csökkentsen.

A push_back és az emplace_back a size()-t növeli. A push_back(const T&) másol, a push_back(T&&) mozgat, az emplace_back(args...) pedig helyben konstruálja az új elemet. Az emplace_back nem automatikusan jobb: ha már van egy T objektumunk, a push_back gyakran ugyanannyiba kerül, az emplace_back viszont nem tudja kiváltani a {}- inicializáló listát. A std::vector<std::vector<int>> v; v.emplace_back(3, 4); egy háromelemű belső vektort hoz létre, amelynek minden eleme 4, mert a (3, 4) konstruktorargumentumnak számít; a v.push_back({3, 4}) ezzel szemben két elemet ad. Ez a különbség gyakori félreértés forrása.

Ha a size() == capacity(), a push_back újraeloszt: új tárolót foglal, az elemeket mozgatással vagy másolással áthelyezi, a régi elemeket destruálja, a régi tárolót felszabadítja. A mozgatás akkor választandó, ha a T move konstruktora noexcept, vagy ha a másolás nem elérhető; ezt a noexcept, swap és container-reallocation részben tárgyaltuk részletesen, és a type trait-ek (Type traits, tag dispatch és if constexpr) teszik hozzáférhetővé a döntést. A push_back erős kivételgaranciát ad, ha a T másolása vagy a nem dobó mozgatása rendelkezésre áll: kivétel esetén a vektor állapota változatlan marad.

A geometriai növekedés amortizált konstans költséget ad. Ha a növekedési faktor k > 1 (a konkrét érték implementációfüggő, tipikusan 1,5 vagy 2), akkor n egymást követő push_back után az áthelyezett elemek száma legfeljebb 1 + k + k^2 + ... + n < n * k / (k - 1), ami k = 2 esetén 2n. Egyetlen push_back worst-case költsége tehát O(n), de n műveletre átlagosan O(1). Ez a különbség a Big-O-s táblázatokban elvész, és éppen ezért nem elegendő a tárolóválasztást csak aszimptotikára alapozni.

28.1.3 Invalidáció: melyik művelet mit tesz érvénytelenné

A következő táblázat a std::vector mutációinak hatását foglalja össze. A „mind” azt jelenti, hogy a korábbi data() pointer, referencia és iterator érvénytelenné válik; az „end()” a past-the-end iterátorra utal, amely nem dereferálható, de összehasonlítható.

A swap különleges: az elemek nem mozdulnak el a memóriában, ezért a rájuk mutató pointer és referencia érvényben marad, csak most a másik vektor elemeire mutat. Az end() iterator ezt nem éli túl, és az iterátorok is a másik konténerhez tartoznak. A std::array esetében nincs újraelosztás, ezért nincs invalidáció sem; de ha az egész std::array-t értékül adjuk át vagy értékadással felülírjuk, a korábbi referenciák továbbra is az eredeti objektumra mutatnak, amelynek tartalma közben megváltozott.

28.1.4 std::vector<bool>: proxy és eltérő tárolási szerződés

A std::vector<bool> a standard könyvtár egyetlen olyan tárolója, amely nem adja ugyanazt a szerződést, mint a többi vector. A szabvány specializációt enged meg, és a tipikus implementáció bitenként tárolja az értékeket. Emiatt a data() tagfüggvény nem létezik, a &v[0] nem ad bool*-t, és a v[i] típusa nem bool&, hanem egy proxy osztály (std::vector<bool>::reference), amely bool-lá konvertálható. A bool& r = v[0]; nem fordul le, az auto x = v[0]; pedig a proxyt másolja, nem bool-t. A vector<bool> tartalma nem adható át C API-nak bool*-ként; ha erre szükség van, std::vector<char>, std::vector<std::uint8_t> vagy fix méretre std::bitset<N> a megfelelő választás. A tömör tárolás előnye valós, de a folytonosság és a data() elvesztése tudatos döntést igényel.

28.1.5 Kidolgozott példa: fix fejléc és dinamikus payload

A következő példa egy protokollüzenetet modellez: a fejléc fix négy bájtos mágikus száma std::array, a változó hosszú tartalom std::vector. A C API-határ csak pointert és hosszt fogad, ezért a vektor data()-ját használjuk, de minden mutáció után újra lekérjük.

// cont_demo.cpp
#include <array>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <vector>

struct Header {
    std::array<std::uint8_t, 4> magic{0x7f, 'E', 'L', 'F'};
    std::uint16_t version{1};
};

void write_bytes(const std::uint8_t* p, std::size_t n) {
    for (std::size_t i = 0; i < n; ++i) {
        std::printf("%02x", static_cast<unsigned>(p[i]));
        std::printf(i + 1 == n ? "\n" : " ");
    }
}

void show(const char* what, const std::vector<std::uint8_t>& v) {
    std::printf("%-14s size=%zu capacity=%zu\n", what, v.size(), v.capacity());
}

int main() {
    Header h;
    write_bytes(h.magic.data(), h.magic.size());

    std::vector<std::uint8_t> payload;
    payload.reserve(4);                  // capacity >= 4 (lehet több is)
    for (std::uint8_t b : {0xde, 0xad, 0xbe, 0xef}) {
        payload.push_back(b);            // size <= capacity: nincs újraallokálás
    }
    show("4 push_back:", payload);

    const std::uint8_t* raw = payload.data();
    write_bytes(raw, payload.size());    // érvényes: közben nincs mutáció

    // Feltöltés a MÉRT kapacitásig: az új méret nem lépi túl a kapacitást,
    // ezért ez még nem allokál újra, a raw érvényes marad.
    payload.resize(payload.capacity(), 0x00);
    show("resize(cap):", payload);

    payload.push_back(0x00);             // size == capacity volt: a szabvány szerint
    show("push_back:", payload);         // biztosan újraallokál
    // write_bytes(raw, payload.size()); // HIBA: raw dangling pointer
    write_bytes(payload.data(), payload.size()); // helyes: friss data()

    payload.erase(payload.begin());      // erase sosem allokál újra
    show("erase:", payload);
    write_bytes(payload.data(), payload.size());
}

A buildparancs rögzített nyelvi módot használ; a -fsanitize=address,undefined kapcsoló a tanuló laborjában opcionális, és a példa helyességét nem helyettesíti:

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

Buildjegyzőkönyv (lab-gcc profil). A kimenet:

7f 45 4c 46
4 push_back:   size=4 capacity=4
de ad be ef
resize(cap):   size=4 capacity=4
push_back:     size=5 capacity=8
de ad be ef 00
erase:         size=4 capacity=8
ad be ef 00

A kapacitásértékek a lab-gcc profil libstdc++-ának mért értékei, nem szabványos garanciák. A példa tanulsága nem a kimenet, hanem a raw élettartama. A reserve(4) csak capacity() >= 4-et garantál, pontosan 4-et nem; ezért a demonstráció nem erre a számra épít, hanem a mért kapacitásig tölti fel a vektort (resize(capacity()) — ez nem lépi túl a kapacitást, tehát nem allokál újra). Ezután a size() == capacity() állapotban a push_back a szabvány szerint biztosan újraallokál, és a raw a régi tárolóra mutat. Az erase soha nem allokál újra, a kapacitás megmarad. Ha a raw-t használnánk, a viselkedés nem definiált; a helyes minta az, hogy a mutáció után a data()-t újra lekérjük. Ugyanez a szabály érvényes akkor is, ha a vektort mozgatjuk vagy másoljuk: a korábbi pointer nem követi az új tulajdonost.

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

A leggyakoribb hiba a reserve és a resize összekeverése: a reserve után a size() még nulla, ezért az indexelés nem definiált. A második a data() pointer megőrzése olyan művelet után, amely újraelosztást okozhat; a javítás az, hogy a pointer élettartamát a mutációhoz kötjük, vagy a mutációt a pointer használata utánra tesszük. A harmadik az erase ciklusban: a for (auto it = v.begin(); it != v.end(); ++it) v.erase(it); a törlés után érvénytelen iterátort léptet; helyes az it = v.erase(it) vagy az erase–remove minta. A negyedik a vector<bool> bool*-ként való átadása; itt a proxy és a hiányzó data() a hiba forrása. Az ötödik a std::array default-inicializálása és az elemek olvasása; a {} használata value-initializál. A hatodik a capacity() mint „használható elemek száma”; a capacity() felső korlát, nem hossz. Végül a std::array méretének sizeof-ból való visszafejtése: a size() a mértékadó, a sizeof paddingot is tartalmazhat.

28.1.7 Összefoglaló

A std::array fix méretű, értékszemantikájú aggregate, amely megőrzi a hosszát, nem csúszik pointerré, és nem invalidálódik újraelosztás miatt. A std::vector folytonos tároló, amelynek size()-a a konstruált elemek száma, capacity()-a az allokált hely, és a kettő között nem élnek T objektumok. A reserve csak kapacitást ad, a resize elemeket hoz létre vagy szüntet meg. A push_back és az emplace_back újraelosztáskor minden pointert, referenciát és iterátort invalidál; az erase a törölt elemektől kezdve invalidál; a clear mindent invalidál, de a capacity-t megtartja. A vector<bool> speciális, proxy alapú tárolás, amely nem ad folytonos bool tömböt. A tárolóválasztás tehát nem Big-O-táblázat, hanem élettartam-, invalidációs és ownership-szerződés kérdése.

28.1.8 Feladatok

1. feladat (diagnosztikai). Az alábbi kódrészletben jelölje meg, mely pontokon nem definiált a viselkedés, és magyarázza el, miért nem lehet a későbbi sorokra „visszamenőleg” következtetni. Tegyük fel, hogy a reserve(8) ténylegesen legalább 8 elemre foglal.

std::vector<int> v;
v.reserve(8);
v[0] = 42;                 // (1)
int* p = v.data();
v.push_back(1);            // (2)
std::printf("%d\n", *p);   // (3)

2. feladat (kódolási). Írjon függvényt, amely egy std::vector<int>-ből eltávolítja a negatív elemeket, megtartja a többi elem sorrendjét, és a végén a vektort C API-nak adja át. A megoldás ne okozzon invalidációs hibát, és ne növelje feleslegesen a capacity-t. Adja meg a buildparancsot is.

3. feladat (tervezési). Tervezze meg egy protokollüzenet adattagjait úgy, hogy a négybájtos mágikus fejléc std::array, a változó hosszú tartalom std::vector legyen. Írjon függvényt, amely a fejlécet és a tartalmat egy C API-nak adja át, és sorolja fel, mely műveletek után kell a pointereket újra lekérni. Térjen ki arra is, mi történik, ha az üzenetet mozgatjuk.

28.1.9 Megoldások

1. megoldás. Az (1) pont nem definiált viselkedés: a reserve(8) nem növelte a size()-t, az érték nulla, ezért a v[0] olyan elemre hivatkozik, amely nem létezik. A (2) pont önmagában nem okoz újraelosztást, mert a size() 0-ról 1-re nő, és a capacity legalább 8; a p tehát érvényes marad. A (3) pont ebben a konkrét végrehajtásban az 1-es értéket olvasná, de a program már az (1) pontnál nem definiált, ezért a további viselkedésére nincs garancia. Az ellenőrzési feltétel: a válasz nevezze meg a size() és a capacity() különbségét, és ne állítsa, hogy a (3) önmagában UB, ha a (2) nem osztott újra.

2. megoldás. C++20-ban a legegyszerűbb helyes megoldás a std::erase_if, amely az erase–remove mintát csomagolja:

#include <cstddef>
#include <cstdio>
#include <vector>

void write_ints(const int* p, std::size_t n) {
    for (std::size_t i = 0; i < n; ++i) {
        std::printf("%d%c", p[i], i + 1 == n ? '\n' : ' ');
    }
}

void remove_negatives(std::vector<int>& v) {
    std::erase_if(v, [](int x) { return x < 0; });
}

int main() {
    std::vector<int> v{3, -1, 4, -1, 5};
    remove_negatives(v);
    write_ints(v.data(), v.size());
}

A std::erase_if az erase-et használja, amely nem oszt újra, csak a törölt elemektől kezdve invalidál; a v.data()-t a törlés után kérjük le, ezért a C API-hívás érvényes. A capacity változatlan marad, a sorrend megmarad. Ellenőrzési feltétel: a függvény után a vektor csak nem negatív elemeket tartalmaz, a size() csökkent, a capacity() nem nőtt, és a data() pointer csak a törlés után kerül felhasználásra. C++20 előtti fallback: v.erase(std::remove_if(v.begin(), v.end(), [](int x){ return x < 0; }), v.end());.

3. megoldás. Az üzenet típusa:

struct Message {
    std::array<std::uint8_t, 4> magic{0x7f, 'E', 'L', 'F'};
    std::vector<std::uint8_t> payload;
};

A fejléc fix méretű, ezért magic.data() és magic.size() stabil; a payload data() pointere viszont minden olyan művelet után újra lekérdezendő, amely újraelosztást okozhat: push_back, emplace_back, insert, reserve (ha a capacity-t növeli), resize (növeléskor), valamint shrink_to_fit. Az erase és a clear szintén invalidál, de nem oszt újra. Ha a Message-t mozgatjuk, a payload belső puffere tipikusan átkerül az új objektumba, de a korábbi payload.data() pointer a forrás objektum tárolójára mutat, amely moved-from állapotba került; a pointer nem követi a tulajdonost. Ezért a C API-hívást mindig a mozgatás után, az új objektumon kell elvégezni. Ellenőrzési feltétel: a válasz nevezze meg a tulajdonost (a Message és a benne lévő vector), a borrowed pointert (data()), az invalidáló műveletet és a mozgatás utáni új lekérdezést.