容器，不會使迭代器（和指針）無效

Question

我目前正在尋找提供一些插入（插入或push_back）和一些刪除（擦除，pop_back是不夠的）方法的容器，並且這不會使迭代器或指針無效調用這兩種方法。更清楚地說，我想要一組元素，我可以添加一個元素（我不關心在哪裏），以及在哪裏可以刪除任何元素（所以我在意在哪裏）。另外，我會有指向特定元素的外部指針，並且如果我從集合中添加或刪除元素，我希望它們保持有效。

據我所知，有兩個標準容器可以滿足我的需求：set和list。但是，一般來說，我不喜歡使用這樣的容器來滿足這樣簡單的需求。由於list在內部涉及指針，並不提供隨機訪問其元素，我認爲這不是一個好的選擇。 A set對其元素具有隨機訪問權限，但也涉及指針，並且隨機訪問本身不是在恆定時間內完成的。我認爲set會比list更好的解決方案，但我想過其他的東西。

那麼當一個元素被刪除時，一個簡單的向量不會試圖保持元素是連續的呢？當移除該容器中間的元素時，其位置將是空的，並且不會發生其他情況。這樣，沒有迭代器或指針會失效。此外，添加元素時，容器將搜索空位置，如果沒有這樣的空洞，則使用簡單的push_back。

很明顯，因爲push_back可以使vector無效迭代器，所以我會使用deque作爲實現的基礎。我也會使用某種堆棧來跟蹤刪除元素的洞。通過這種方式，除了滿足我的無效化需求外，還可以在一段時間內添加，刪除和訪問元素。

但是，仍然存在一個問題：在遍歷這個容器或僅僅通過索引訪問元素時，我們需要考慮這些漏洞。這就是問題開始超越優勢的地方。

因此，我的問題是：你怎麼看待我對這個容器的想法？ 更重要的是，你會用我的原始問題，set，list還是其他什麼？ 另外，如果你對最後一個問題有很好的解決方案（遍歷我的容器），請隨時向我展示。

Answer 1

要求1：插入（插入或推回）和一些去除（擦除，而不僅是最後一個元素）

• 符合候選：deque，forward_list，list，map，multi_map，set ，multiset，unordered_map，unordered_multimap，unordered_set，unordered_multiset，和vector

• 淘汰候選：array（無insert或push_back），queue，priority_queue和stack（無erase，僅pop）

要求2：調用這兩種方法時，不會失效的迭代器也不指針

• 符合條件的候選人也符合要求1：forward_list，list,map,multi_map，set，multiset，
• 上擦除被淘汰：deque（擦除第一要素，只有當迭代器仍然有效），並vector（擦除開始後的所有元素）
• 在插入時被淘汰：在大多數情況下dequeue（ ），unordered_map，unordered_multimap，unordered_set和unordered_multiset（以防生長需要刷新）和vector（如果生長需要重新分配）

要求3：外部指針應繼續有效

Approximaletly比要求。然而unordered_map，unordered_multimap，unordered_set和unordered_multiset會因爲元素的引用保持有效satifsy這個要求同樣的結果。

要求4：隨機存取元件

• 符合滿足要求1和2的候選：map和multimap
• 幾乎符合候選：set和multiset不具有隨機訪問，但是能夠滿足它使用成員find()（O（logn））
• 不符合：列表（雖然算法find()可以在O（n）中提供解決方法）。

回答問題1：哪個更好，一set或list？

這取決於你的其他要求。在一個集合中，每個值只能存儲一次。如果您的元素都是唯一的，請選擇該組。如果沒有，你最好選擇列表或multiset。

我不知道你存儲的元素，但是整個元素是搜索參數嗎？還是有鑰匙？在後一種情況下，你真的會去找一張地圖。

回答問題2：什麼替代容器？

我不會選擇deque爲您的替代。

如果你能預見元素的最大數量，你可以簡單地預留足夠的能力，以避免重新分配。 （滿足要求1,3和4）。 如果你有一個「空元素」來表示洞，那麼你也可以滿足要求2.在最壞的情況下，你可以選擇一個向量來存儲你的元素和一個指標，如果它是有效的。

如果這樣的最大值無法確定，我寧願去一個map這被證明是靈活，滿足您的所有需求。