V čom spočíva rozdiel medzi kontajnermi vector a list v C++?

std::vector predstavuje dynamický poľ. Dáta sa ukladajú v súvislom bloku pamäte.

Výhody vector:

• Rýchly prístup podľa indexu (O(1)).
• Dobrá lokalita dát, čo je užitočné pre cache procesora.
• Rýchle pridanie/odstránenie na konci (priemerne O(1)).

Nevýhody vector:

• Zložitosť pri vkladaní/mazaní na ľubovoľnom mieste (O(n)).
• Realokácia pamäte pri raste, čo vyžaduje kopírovanie prvkov.

std::list je dvojzávitovo spojený zoznam. Každý prvok obsahuje ukazovatele na predchádzajúci a nasledujúci prvok.

Výhody list:

• Zložitosť pri vkladaní/mazaní kdekoľvek (O(1)) po nájdení pozície (ktorá môže byť O(n)).
• Nevyžaduje súvislý blok pamäte.

Nevýhody list:

• Pomalý prístup podľa indexu (O(n)).
• Zaberá viac pamäte na prvok (kvôli ukazovateľom).
• Zlá lokalita dát.

Hlavný rozdiel:

Vlastnosť	std::vector	std::list
Dátová štruktúra	Dynamický poľ	Dvojzávitovo spojený zoznam
Uloženie dát	Kontinuálna pamäť	Uzly s ukazovateľmi
Prístup podľa index	O(1)	O(n)
Vkladanie/odstraňovanie	O(n) (okrem na konci)	O(1) (po iterátore)
Lokalita	Dobrá	Zlá
Pamäťová náročnosť	Elementy	Elementy + ukazovatele

Voľba medzi vector a list závisí od typických operácií s kontajnerom. Ak sú časté náhodné prístupy a pridávanie/odstraňovanie na konci, preferuje sa vector. Ak sú dôležité časté vkladania/odstraňovania uprostred zoznamu, preferuje sa list.