C++: A lista hogy foglal helyet a memóriában? Ahány elem annyi felé van szétszórva?

std::vector - egymást követően

std::list - szétszórva

Attól függ az a lista hogyan van implementálva.

Ha tömbként akkor a teljes tömb egyszerre kerül lefoglalásra. Ha láncolt listaként akkor a lista elemek hozzáadáskor kerülnek lefoglalásra, tehát nem szükségszerű hogy egymás mellé kerülnek.

#4 "míg a vector ebben lassabb."

Erre azért ne vegyél mérget. Nagyon sok esetben, sőt, az esetek többségében a vector veri a listát.

iostream:

Arról van szó, ha a vector-ban a 0. elem elé be akarsz szúrni egy elemet, akkor eggyel arrébb másolod az összes utána lévő elemet. Míg a láncolt listánál, csak bekötöd a helyére. Ha végigolvasod a vector-t az gyorsabb mert nincs indirekció(pointer). Használat szerint lesz gyorsabb vagy lassabb.

iostream:

Kimérve is lassabb a vector, legalábbis ebben az esetben. Nem kell GiB-nyi adat hozzá.

[link]

Ebben az esetben? Én azt látom, hogy az oldal engem igazol: a vector tipikusan a leggyorsabb, nagyméretű adatoknál (ahol már sokat kell szüttyögni), ott valóban lelassul a vector. A leggyakoribb vector a vector<int>, ott a list minden szempontból lassabb.

Persze aki 4 kB-os adatot nem pointerrel tárol vectorban, az valamit nagyon eltervezett.