Kokia yra operacijų sudėtingumas C++ std::vector ir std::list konteineriams?

std::vector

• Prieiga per indeksą: O(1)
• Pridėjimas į pabaigą (push_back): amortizuotas O(1)
• Įdėjimas ar ištrynimas viduryje: O(n), nes reikia perkelti elementus
• Iteracija: O(n)

std::list (dvigubai susietas sąrašas)

• Prieiga per indeksą: O(n), nes reikia sekos perėjimo
• Įdėjimas ir ištrynimas bet kur (jei yra iteratorius): O(1)
• Iteracija: O(n)

Todėl, vector yra efektyvus greitam prieigai ir pridėjimui pabaigoje, o list tinka dažniems įdėjimams ir ištrynimams viduryje be elementų perkėlimo.