根据大 O，清晰函数是 std::map 的时间复杂度是多少？

Question

clear 函数是 std::map 的时间复杂度是多少？
我说它是 O(1) 对吗？

Answer 1

该标准在[associative.reqmts]/8 表 102 中说：

a.clear()<=>a.erase(a.begin(), a.end()) 线性输入a.size()

所以它实际上被要求为 O(N)。

编辑：总结各种位。

要删除一个节点，a 会map执行两个操作：

1. 调用分配器destroy方法销毁元素
2. 调用allocatordeallocate方法释放节点占用的内存

前者可以在代码中省略（检查is_trivially_destructible），实际上它通常在vector例如中完成。不幸的是，后者更棘手，并且不存在任何特征，因此我们必须依赖优化器。

不幸的是，即使通过内联优化可以完全删除destroy和deallocate节点，恐怕将无法认识到树遍历现在是无用和优化该走了。因此，你最终会在树的 ?(N) 遍历中结束，并且每一步都没有做任何事情......