排序的數據結構快速迭代，插入，通過迭代

Question

我尋找具有以下屬性的數據結構刪除：

• 排序（除非這不需要用於排序的順序迭代）
• O（ 1）按排序順序迭代。
• 快速插入。我會認爲O（LG（N））是要走的路。
• 快速刪除using an iterator。我希望至少與插入速度相同。我將永遠不必按值刪除一個項目，並且始終有可用的迭代器。這個需求意味着插入和迭代不會使迭代器失效，除非值的刪除發生的速度與迭代器刪除的速度相同。

其他不相關，將永遠不會使用。

在搜索了一段時間後，我無法找到遵循這些屬性的數據結構。堆允許快速插入和刪除（儘管不是迭代器本身），但是不容易以所需的方式迭代。

我也看了一個排序的向量。這有快速插入和正確的迭代，但刪除在那裏很難。

我會說這是一個很常見的數據結構，儘管我無法找到匹配的結構。此外，我認爲在刪除時我總是有一個迭代器可以提高性能。

我希望你能幫助我在正確的方向。

Answer 1

std::set或std::multiset被指定爲具有insert（）的對數複雜度，並且通過現有的迭代器進行刪除的分期恆定複雜性。

對集合/多集合的迭代將按排序順序迭代。