Сравнение скорости операций вставки, удаления, поиска для актуальных контейнеров в с++?
Ищу таблицу, в которой через O(f(n)) произведено сравнение для операций над контейнерами(vector, list, deque, map, multimap, set,multiset, stack,queue) для лучшего понимания. В книжках, к сожалению в виде таблицы не нашел, может кто подскажет где достать. Спасибо
Вижу, что табличка не совсем корректна. remove head для vector имеет сложность O(n).
Опять же, есть разница между формальным определением и реализацией. Например, std::deque в плане использования не сильно отличается от std::vector, если пользоваться итераторами или индексами. А вот указателями уже нельзя в deque пользоваться. std::queue вообще реализован в виде фасада над std::deque, поэтому у них все показатели должны быть одинаковы (в пределах свойств интерфейса класса). Но это не к вам претензия, а к составителю таблички.)
В книжках сравнений нет, потому что многое зависит от реализации. Стандарт описывает только интерфейс, а реализовать можно по разному и сложность операций может отличаться. Например Find имеет сложность O(log n) только для отсортированного массива, причём с тем же предикатом, с которым осуществляется поиск.
