Какова временная сложность итерации через std::set/std::map? Я считаю, что он линейный по размеру набора/карты, но не настолько уверен. Это указано в стандарте языка?Какова временная сложность итерации через std :: set/std :: map?
В draft C++11 standard N3337 ответ можно найти в § пункт 24.2.1 8:
Все категории итераторов требуют только те функции, которые реализуема для данной категории в постоянное время (амортизируется).
Поскольку каждая операция на итераторе должна быть постоянная время, перебором n элементов должен быть O(n).
Если map/set реализован как двоичное дерево с родительскими указателями, итерация через все элементы будет посещать каждый узел дерева не более 3 раз. Если реализация представляет собой b-дерево с родительскими указателями, каждый узел будет посещать не более 2 * n + 1 раз, n число элементов в узле. В обоих случаях это означает постоянную среднюю временную сложность для каждого шага итерации. Я не знаю каких-либо других совместимых способов реализации map/set. – WaltK
Я считаю, что он линейный по размеру набора/карты, но не так уверен.
Это верно. Перебор весь набор или карты является O(N)
Итерация всего контейнера всегда будет 'O (n)' _at наименьшей (я полагаю, что действительно глупые реализации могут сделать это _worse_) – Chad
Когда вы говорите «итерацию», что именно вы имеете в виду? Вы пишете цикл while/for с использованием стандартного итератора? Используете ли вы один из стандартных алгоритмов? –