Care este diferența dintre containerele vector și list în C++?

std::vector reprezintă un array dinamic. Datele sunt stocate într-un bloc de memorie contiguu.

Avantajele vector:

• Acces rapid după index (O(1)).
• Localitate bună a datelor, utilă pentru cache-ul procesorului.
• Adăugare/ștergere rapidă la sfârșit (în medie O(1)).

Dezavantajele vector:

• Complexitate la inserarea/ștergerea în poziții arbitrare (O(n)).
• Realocarea memoriei la creștere, necesită copierea elementelor.

std::list este o listă dublu legată. Fiecare element stochează pointeri către elementul anterior și următor.

Avantajele list:

• Complexitate la inserare/ștergere oriunde (O(1)) după găsirea poziției (care poate fi O(n)).
• Nu necesită un bloc de memorie contiguu.

Dezavantajele list:

• Acces lent după index (O(n)).
• Ocupă mai multă memorie pe element (din cauza pointerilor).
• Localitate slabă a datelor.

Diferența principală:

Caracteristică	std::vector	std::list
Structura datelor	Array dinamic	Listă dublu legată
Stocarea datelor	Memorie contiguă	Nodi cu pointeri
Acces după index	O(1)	O(n)
Inserare/ștergere	O(n) (cu excepția la final)	O(1) (după iterator)
Localitate	Bună	Slab
Consumul de memorie	Elemente	Elemente + pointeri

Alegerea între vector și list depinde de operațiile tipice cu containerul. Dacă accesul aleatoriu și adăugarea/ștergerea la final sunt frecvente, preferați vector. Dacă inserțiile/ștergerile frecvente în mijlocul listei sunt importante, preferați list.