Aká je zložitosť operácií pre kontajnery std::vector a std::list v C++?

std::vector

• Prístup cez index: O(1)
• Pridanie na koniec (push_back): amortizované O(1)
• Vloženie alebo odstránenie uprostred: O(n), pretože je potrebné posunúť prvky
• Iterácia: O(n)

std::list (dvojitý spojený zoznam)

• Prístup cez index: O(n), pretože je potrebné sekvenčné prechádzanie
• Vloženie a odstránenie kdekoľvek (ak je k dispozícii iterátor): O(1)
• Iterácia: O(n)

Preto je vector efektívny pre rýchly prístup a pridanie na koniec, zatiaľ čo list je vhodný pre časté vkladanie a mazanie uprostred bez potreby posúvania prvkov.