Kāda ir operāciju sarežģītība C++ std::vector un std::list konteineriem?

std::vector

• Pieejamība pēc indeksa: O(1)
• Pievienošana beigās (push_back): amortizēts O(1)
• Ievietošana vai dzēšana vidū: O(n), jo nepieciešama elementu pārvietošana
• Iterācija: O(n)

std::list (divvirzienu saistīts saraksts)

• Pieejamība pēc indeksa: O(n), jo nepieciešama secīga pāreja
• Ievietošana un dzēšana jebkurā vietā (ja ir iterators): O(1)
• Iterācija: O(n)

Tādēļ, vector ir efektīvs ātrai piekļuvei un pievienošanai beigās, bet list ir piemērots biežām ievietošanām un dzēšanām vidū bez elementu pārvietošanas nepieciešamības.