我正在处理一组 [0， m] 间隔的 n 个整数，我需要以下操作：
- 找到
- 删除
- 插入
- 枚举(获取所有条目)
- 清除(删除所有条目)
目前我正在使用二叉树/堆，但想知道是否有更有效的数据结构。 我可以使用未初始化的 RAM，据我所知，需要 O(1) 用于查找/删除/插入，O(n) 用于枚举/清除，同时需要 O(m) 空间。(例如见 https://research.swtch.com/sparse)
是否有任何数据结构需要小于 O(m) 的空间，同时仍然保持(摊销)最坏情况复杂性 O(1) 用于查找/删除/插入和 O(n) 用于枚举/清除？
请注意：摊销如下："给定 n 个操作，我们总共有常数 * n 个操作，因此摊销的最坏情况为 O(1)"。不是："给定这个概率分布和给定的假设X，Y，Z，平均最坏情况很可能在O(1)中。 所以我不是在寻找基于哈希表的解决方案，这些解决方案"可能大部分时间"都可以在 O(1) 中工作。
不，没有这种已知的数据结构。参见米克尔·索鲁普(Mikkel Thorup)的"Mihai Pǎtraşcu：讣告和开放问题"，第1节，问题1。"如果我们想要一个用于查找和更新的联合绑定，最著名的绑定是 O(sqrt(log n/log log n))">