遍历 a std::set/ std::multiset/ std::map/的时间复杂度是std::multimap多少？我相信它在集合/地图的大小上是线性的，但不太确定。语言标准中有规定吗？
问问题
23944 次
2 回答
61
在C++11 标准草案 N3337中，答案可以在 § 24.2.1 第 8 段中找到：
迭代器的所有类别只需要在恒定时间内（摊销）对给定类别可实现的那些函数。
n由于迭代器上的每个操作都必须是常数时间，因此对元素的迭代必须是O(n).
于 2012-08-02T14:55:45.353 回答
17
我相信它在集合/地图的大小上是线性的，但不太确定。
那是对的。遍历整个集合或地图是O(N)
于 2012-08-02T14:41:37.603 回答