排序数据结构--迭代器快速迭代、插入、删除

Question

我正在寻找具有以下属性的数据结构：

• 排序(除非排序顺序迭代不需要这一点)
• O(1)按排序顺序迭代。
• 快速插入。我认为O(lg(n))是可行的。
• 快速删除using an iterator。我希望至少有同样的速度插入。我将永远不需要删除一个项目的价值，并将始终有迭代器可用。这意味着插入和迭代永远不会使迭代器失效，除非按值删除的速度与迭代器的删除速度相同。

任何其他的东西都是不相关的，永远不会被使用。

在搜索了一段时间之后，我无法找到遵循这些属性的数据结构。堆允许快速插入和移除(虽然迭代器本身不允许)，但不容易以所需的方式迭代。

我也看过一个排序向量。这具有快速的插入和正确的迭代，但是删除在那里是相当困难的。

我想说这是一个非常常见的数据结构，尽管我无法找到一个匹配的结构。此外，我认为在删除时总是有迭代器的事实可能会提高性能。

我希望你能在正确的方向上帮助我。

Answer 1

std::set或std::multiset被指定为insert()的对数复杂度，以及通过现有迭代器进行删除的摊还常数复杂度。

在集合/多集上迭代将按排序顺序迭代。