Na czym polega różnica między kontenerami vector i list w C++?

std::vector reprezentuje dynamiczną tablicę. Dane są przechowywane w ciągłym bloku pamięci.

Zalety vector:

• Szybki dostęp po indeksie (O(1)).
• Dobra lokalność danych, co jest korzystne dla pamięci podręcznej procesora.
• Szybkie dodawanie/usuwanie na końcu (średnio O(1)).

Wady vector:

• Złożoność dodawania/usuwania w dowolnym miejscu (O(n)).
• Rezerwacja pamięci przy wzroście rozmiaru, wymaga kopiowania elementów.

std::list jest listą dwukierunkową. Każdy element przechowuje wskaźniki na poprzedni i następny element.

Zalety list:

• Złożoność dodawania/usuwania w dowolnym miejscu (O(1)) po znalezieniu pozycji (która może być O(n)).
• Nie wymaga ciągłego bloku pamięci.

Wady list:

• Wolny dostęp po indeksie (O(n)).
• Zajmuje więcej pamięci na element (ze względu na wskaźniki).
• Zła lokalność danych.

Główna różnica:

Cecha	std::vector	std::list
Struktura danych	Dynamiczna tablica	Lista dwukierunkowa
Przechowywanie danych	Pamięć ciągła	Węzły z wskaźnikami
Dostęp po indeksie	O(1)	O(n)
Wstawianie/usuwanie	O(n) (z wyjątkiem końca)	O(1) (po iteratorze)
Lokalność	Dobra	Zła
Zużycie pamięci	Elementy	Elementy + wskaźniki

Wybór między vector a list zależy od typowych operacji na kontenerze. Jeśli częste jest losowe dostęp i dodawanie/usuwanie na końcu, preferowany jest vector. Jeśli ważne są częste wstawienia/usunięcia w środku listy, preferowany jest list.