У чему се разликују контејнери vector и list у C++?

std::vector predstavlja dinamički niz. Podaci se čuvaju u kontinuiranom bloku memorije.

Prednosti vector:

• Brz pristup po indeksu (O(1)).
• Dobra lokalnost podataka, korisno za keš procesora.
• Brzo dodavanje/brisanje na kraj (prosečno O(1)).

Nedostaci vector:

• Složenost pri dodavanju/brisanju na bilo kojoj poziciji (O(n)).
• Reallociranje memorije pri rastu, što zahteva kopiranje elemenata.

std::list je dvostruko povezani spisak. Svaki element čuva pokazivače na prethodni i sledeći element.

Prednosti list:

• Složenost pri dodavanju/brisanju bilo gde (O(1)) nakon pronalaska pozicije (koja može biti O(n)).
• Ne zahteva kontinuirani blok memorije.

Nedostaci list:

• Sporo pristup po indeksu (O(n)).
• Zauzima više memorije po elementu (zbog pokazivača).
• Loša lokalnost podataka.

Glavna razlika:

Osobina	std::vector	std::list
Struktura podataka	Dinamički niz	Dvostruko povezani spisak
Čuvanje podataka	Kontinuirana memorija	Čvorovi sa pokazivačima
Pristup po indeksu	O(1)	O(n)
Umetanje/brisanje	O(n) (osim na kraju)	O(1) (posle iteratora)
Lokalnost	Dobra	Loša
Potrošnja memorije	Elementi	Elementi + pokazivači

Izbor između vector i list zavisi od tipičnih operacija sa kontejnerom. Ako su česti slučajni pristup i dodavanje/brisanje na kraju, preferira se vector. Ako su važne česte umetanja/brisanja u sredini liste, preferira se list.