Kuo skiriasi C++-e esantys konteineriai vector ir list?

std::vector yra dinaminis masyvas. Duomenys saugomi nuosekliame atminties bloke.

vector privalumai:

• Greitas prieiga pagal indeksą (O(1)).
• Geras duomenų lokalumas, kas naudinga procesoriaus talpykloje.
• Greitas pridėjimas/pašalinimas pabaigoje (vidutiniškai O(1)).

vector trūkumai:

• Sudėtingas pridėjimas/pašalinimas bet kurioje vietoje (O(n)).
• Atminties perskirstymas didėjant dydžiui, reikalaujantis elementų kopijavimo.

std::list yra dvipusis sąrašas. Kiekvienas elementas saugo nuorodas į ankstesnį ir kitą elementą.

list privalumai:

• Sudėtingas elementų pridėjimas/pašalinimas bet kurioje vietoje (O(1)), po pozicijos nustatymo (kuri gali būti O(n)).
• Nereikalauja nuoseklaus atminties bloko.

list trūkumai:

• Lėta prieiga pagal indeksą (O(n)).
• Daugiau atminties elemento atžvilgiu (dėl nuorodų).
• Blogas duomenų lokalumas.

Pagrindinis skirtumas:

Savybė	std::vector	std::list
Duomenų struktūra	Dinaminis masyvas	Dvipusis sąrašas
Duomenų saugojimas	Nuosekli atmintis	Mazgai su nuorodomis
Prieiga pagal indeksas	O(1)	O(n)
Įterpimas/pašalinimas	O(n) (išskyrus pabaigą)	O(1) (po iteratoriaus)
Lokalumas	Geras	Blogas
Atminties sąnaudos	Elementai	Elementai + nuorodos

Pasirinkimas tarp vector ir list priklauso nuo dažniausiai atliekamų operacijų su konteineriu. Jei dažnai reikalinga atsitiktinė prieiga ir pridėjimas/pašalinimas pabaigoje, geriau naudoti vector. Jei svarbios dažnos įterpimo/pašalinimo operacijos viduje, geriau naudoti list.