Сравнение скорости операций вставки, удаления, поиска для актуальных контейнеров в с++?

Question

[Mark_Aizek]

Ищу таблицу, в которой через O(f(n)) произведено сравнение для операций над контейнерами(vector, list, deque, map, multimap, set,multiset, stack,queue) для лучшего понимания. В книжках, к сожалению в виде таблицы не нашел, может кто подскажет где достать. Спасибо

Answer 1

[#алгоптимизируй #отботизируй]

https://www.google.ru/search?q=stl+time+of+operati...

Comments

[maaGames]

Вижу, что табличка не совсем корректна. remove head для vector имеет сложность O(n).
Опять же, есть разница между формальным определением и реализацией. Например, std::deque в плане использования не сильно отличается от std::vector, если пользоваться итераторами или индексами. А вот указателями уже нельзя в deque пользоваться. std::queue вообще реализован в виде фасада над std::deque, поэтому у них все показатели должны быть одинаковы (в пределах свойств интерфейса класса). Но это не к вам претензия, а к составителю таблички.)

В книжках сравнений нет, потому что многое зависит от реализации. Стандарт описывает только интерфейс, а реализовать можно по разному и сложность операций может отличаться. Например Find имеет сложность O(log n) только для отсортированного массива, причём с тем же предикатом, с которым осуществляется поиск.

[AtomKrieg]

unordered_map нет

Answer 2

[Антон Жилин]

Отличная полная таблица. Можно кликнуть на любой функции, чтобы узнать сложность.