排序的数据结构快速迭代，插入，通过迭代

Question

我寻找具有以下属性的数据结构删除：

• 排序（除非这不需要用于排序的顺序迭代）
• O（ 1）按排序顺序迭代。
• 快速插入。我会认为O（LG（N））是要走的路。
• 快速删除using an iterator。我希望至少与插入速度相同。我将永远不必按值删除一个项目，并且始终有可用的迭代器。这个需求意味着插入和迭代不会使迭代器失效，除非值的删除发生的速度与迭代器删除的速度相同。

其他不相关，将永远不会使用。

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

我也看了一个排序的向量。这有快速插入和正确的迭代，但删除在那里很难。

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

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

Answer 1

std::set或std::multiset被指定为具有insert（）的对数复杂度，并且通过现有的迭代器进行删除的分期恒定复杂性。

对集合/多集合的迭代将按排序顺序迭代。