std::map 数据结构上操作的摊余复杂度

Question

假设我在存储键、值对的映射上有以下类型的 Q 操作。键可通过运算符 '<'

进行比较

给定 l、r 和值 x。擦除范围 [l, r) 中已存在的所有键并插入对 (r,x)。

我的问题是，仅擦除范围内的键然后插入的幼稚策略是否具有良好的摊销复杂度（可能是 O(log n) 或其他）。因为我有一个直观的感觉，如果一个操作做了很多删除，那么由于尺寸减小，未来的操作的时间复杂度将会降低。任何想法表示赞赏。

“朴素”算法的更详细描述：您只需二分搜索即可找到最小的 keyl >= l 和最大的 keyr < r and delete all the keys in the range [keyl, keyr] (overall this is O(log n + n log n) worst case)

Answer 1

您描述的算法没有达到您想要的复杂性。

问题是，当您删除一个范围然后插入新数据时，您最终可能会得到比开始时更多或更少的数据。如果这种情况发生在向量的中间，则最多需要移动一半的数据。

移动大数据块是您可以对其执行的最快的操作之一。但移动

O(n)

数据仍然需要

O(n)

时间 - 只要有良好的常数即可。

我们有很多更好的解决方案。完全解决这个问题的数据结构包括红黑树、btree、skiplists 和 leveldb。有许多微妙的权衡。但所有这些都将被摊销到这个操作的时间

O(log(n))

。