Какова временная сложность итерации через std::set/std::multiset/std::map/std::multimap? Я считаю, что он линейный по размеру набора/карты, но не уверен. Это указано в стандарте языка?
В черновик С++ 11 standard N3337 ответ можно найти в § 24.2.1, пункт 8:
Все категории итераторов требуют только те функции, которые реализуется для данной категории в постоянное время (амортизируется).
Поскольку каждая операция на итераторе должна быть постоянной, итерация через элементы n должна быть O(n).
Я считаю, что он линейный по размеру набора/карты, но не так уверен.
Это правильно. Итерация через весь набор или карту составляет O(N)