Jaká je složitost operací pro kontejnery std::vector a std::list v C++?

std::vector

• Přístup podle indexu: O(1)
• Přidání na konec (push_back): amortizované O(1)
• Vložení nebo odstranění uprostřed: O(n), protože je třeba posunout prvky
• Iterace: O(n)

std::list (dvojitě vázaný seznam)

• Přístup podle indexu: O(n), protože je třeba sekvenční průchod
• Vložení a odstranění kdekoli (pokud je k dispozici iterátor): O(1)
• Iterace: O(n)

Proto je vector efektivní pro rychlý přístup a přidávání na konec, zatímco list je vhodný pro časté vkládání a mazání uprostřed bez nutnosti posunu prvků.