Odpowiedź

std::vector i std::list to różne pojemniki STL z różniącymi się realizacjami i zachowaniem.

• std::vector implementuje dynamiczną tablicę, elementy są rozmieszczone ciągłe w pamięci. Szybki dostęp po indeksie (O(1)), szybkie dodawanie na koniec (amortyzowane O(1)), kosztowne wstawienia i usunięcia w środku (O(n)), ponieważ elementy muszą być przesuwane.
• std::list to lista dwukierunkowa. Wolny dostęp losowy (O(n)), szybkie wstawienia i usunięcia w dowolnym miejscu listy (O(1)), większe koszty pamięci (dwa wskaźniki na element) i częste alokacje/dealokacje.

Kiedy wybierać:

• Używaj std::vector prawie zawsze, jeżeli nie potrzebujesz częstych wstawień/usunięć w środku.
• std::list jest uzasadniona tylko w przypadku potrzeby wstawień/usunięć w dowolnym miejscu przy dużej ilości danych, kiedy przesuwanie elementów w wektorze jest zbyt kosztowne.
• Dla małych zbiorów, nawet jeśli potrzebne są wstawienia w środku, std::vector często jest szybszy z powodu lokalności danych.

Przykład:

std::vector<int> v;
v.push_back(1);
v[0] = 2; // szybki dostęp po indeksie

std::list<int> l;
l.push_back(1);
// l[0] = 2; // Błąd: std::list nie ma dostępu po indeksie!

Pytanie z podstępem

"Dlaczego std::list jest rzadko używana w nowoczesnych projektach C++, mimo teoretycznej przewagi przy częstych wstawieniach do środka kolekcji?"

Odpowiedź: Ponieważ w praktyce z powodu licznych małych alokacji, utraty lokalności danych (kash-friendly), złożoności struktury oraz złej wydajności niektórych operacji (std::list jest nieefektywna nawet dla dużych list z powodu strat czasu na alokację i dealokację, a spowolnienie z powodu przestojów w cache często przeważa nad zyskiem asymptotycznym). Ponadto nowoczesne procesory są bardzo wrażliwe na lokalność cache, więc nawet przy dużych ilościach danych std::vector często działa szybciej w rzeczywistych warunkach.

Przykłady rzeczywistych błędów z powodu nieznajomości szczegółów tematu

---

Historia

W systemach czasu rzeczywistego do przechowywania kolejki zdarzeń wybrano std::list ze względu na częste usunięcia z dowolnych pozycji. W rezultacie system stał się 10 razy wolniejszy z powodu częstych odwołań do heap i złej lokalizacji danych w pamięci.

---

Historia

W procesorze graficznym przechowywano tablice sąsiadów w postaci std::list ze względu na wstawki. To doprowadziło do dramatycznego wzrostu użycia pamięci oraz degradacji pamięci podręcznej L1/L2, mimo że rzeczywiste korzyści w szybkości nie zostały uzyskane.

---

Historia

W serwisie tworzenia raportów każdy raport był zbierany z obiektów Linked List. W testach obciążeniowych serwis zaczął "zwalniać", a profilowanie pokazało wąskie gardła w wydatkach na alokację przy pracy z listami. Przeszliśmy na wektor — wynik poprawił się kilkakrotnie.