В c ++ стандарты STL определяются характеристиками алгоритмов Big-O, а также требованиями к пространству. Таким образом, вы можете переключаться между конкурирующими реализациями STL и при этом знать, что ваша программа имеет одинаковые характеристики времени выполнения.
Особенно хорошие реализации STL могут даже списки особых случаев определенных типов быть лучше, чем стандартные требования.
Это позволило легко выбрать правильный итератор или тип списка для конкретной задачи, потому что вы могли легко взвесить между потреблением места и скоростью.
Ofcourse Big-O - это только направляющая линия, так как все константы удалены. Если алгоритм работает в k * O (n), он будет классифицирован как O (n), но если k достаточно высокий, он может быть хуже, чем O (n ^ 2) для некоторых значений n и m.