c++ - 根据大 O，明确函数的时间复杂度是 std::map 是多少？

Question

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

Answer 1

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

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

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

---

编辑：总结各种位。

要删除节点，amap执行两个操作：

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

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

不幸的是，即使通过内联优化器可以完全删除destroyanddeallocate节点，恐怕它也无法意识到树遍历现在是无用的，也无法对其进行优化。因此，您最终会在树的 Θ(N) 遍历中结束，并且每一步都没有做任何事情......

Answer 2

因为它是一个模板，所以在编译时可能会知道该类型（例如std::map<int>）在无操作中的销毁，因此销毁成员的需要并不是推断必要的最坏情况性能的良好基础。尽管如此，编译器必须访问二叉树的每个节点，释放堆内存，并且节点的数量与元素的数量呈线性关系（erase()只会使指向已擦除元素的迭代器/引用/指针无效，insert()不会使任何等无效） . 都证明了 1:1 的关系）。

所以，它是线性的，但是因为即使不需要元素析构函数也需要清理堆的使用......

（有趣的是，这意味着如果所有内存都是从一个专用内存池分配的，那么对于具有琐碎的无操作析构函数的元素，一个类似std::map<>的关联容器 - 或者可能std::map<>它本身带有一个聪明的自定义分配器 - 可以是 O(1)在 O(1) 中“扔掉”。）

Answer 3

cplusplus 参考站点声称它在容器大小方面具有线性复杂性，因为必须调用每个元素的析构函数。

Answer 4

据我所知，所有清理操作的复杂性都是 O(n)，因为您需要一一销毁这些对象。