我剛剛實現了我自己的類來高效地從數組中刪除，但是我想要查看是否有類似的東西已經存在。我想要的是類似列表的訪問效率，但使用數組。我想使用一個數組，因爲緩存一致性，所以我不必一直調用內存分配器（因爲在分配節點時使用std :: list）。一個索引集（用於向量中的高效去除）
我想要做的是創建一個有兩個數組的類。第一個是一組元素，第二個數組是一組整數，其中每個整數是第一個數組中的空閒時隙。所以我可以相當容易地添加/刪除數組中的元素，而無需爲它們分配新的內存，只需從空閒列表中獲取索引並將其用於新元素即可。
這樣的事情是否已經存在？如果我自己做，我也必須製作自己的迭代器，所以你可以迭代集合，避免陣列中的任何空插槽，我不會很喜歡這個。
謝謝。
注：實物操作我想在集執行是：
std::list<T>實際上聽起來完全像你工作的理論上正確的數據結構，因爲它支持您所列出的四次運算，所有具有最佳的空間和時間複雜度。 std::list<T>::iterator即使向列表中添加/刪除其他項目，該句柄仍然有效。
這可能是因爲有一個自定義分配器（即不std::allocator<T>），您可以用std::list<T, Allocator>用它來得到你想要的性能（內部池節點，然後不做運行分配每次您添加或刪除節點）。但是這可能是矯枉過正。
我會開始只使用std::list<T>與默認分配器，然後只查看自定義分配器或其他數據結構，如果您發現性能對您的應用程序太糟糕。
Tim可能是個好主意。 – Robinson
任何地方
當創建一個新節點時，std :: map將最終使用operator new（malloc），意味着互斥體。似乎相當重量級給我。 – Robinson
ohhhh好..我忘了 –
如果維護元素的順序是不相關的，請使用swap-and-pop。
將最後一個元素複製/移動到要移除的元素上，然後彈出後退元素。超級簡單而高效。如果您使用標準的C++向量和操作，您甚至不需要爲刪除元素而進行特殊檢查，因爲它只會工作（tm）。
*iter = std::move(container.back());
container.pop_back();
我不記得是否pop_back（）在矢量上無效的迭代器，但我不認爲它確實如此。如果是這樣，直接使用索引或重新計算新的有效迭代器。
auto delta = iter - container.begin();
// mutate container
iter = container.begin() + delta;
這種方法的問題是它不支持OP列表中的操作＃2。什麼是對象的持久索引/句柄？也許我錯過了你的意思。 –
啊，是的，你可以用一個額外的圖層來處理映射索引到那個特定用例的元素。我通常稱之爲「插槽地圖」，在線文章。通常情況下，如果他們完全需要這個功能，他們應該真的很難想象;這可能看起來像一個要求，但可能不是一些工作。 –
您可以通過在空插槽空間中存儲有關「空」插槽的信息來使用單個陣列。
對於空槽您的陣列A在一個連續的塊，說的在位置A[n]（其中n'是自由索引下一個塊的索引）從索引n，存儲(k, n')開始k槽。如果您的數組正在存儲字大小的對象，則可能必須將兩個整數打包爲一個單詞。
你實際上正在存儲一個空閒塊鏈接列表，就像內存管理器可能做的那樣。
編碼有點痛苦，但是這可以讓你在O（1）時間分配一個自由索引，並且在O（n）時間內遍歷分配的索引，其中n是數字的分配插槽。儘管在最壞的情況下釋放索引將是O（n）時間：這與分段內存相同。
對於第一個空閒塊，可以單獨存儲索引，也可以使用永不分配的約定A[0]，以便始終可以從此處開始進行自由索引搜索。
['std :: deque']（http://en.cppreference.com/w/cpp/container/deque）怎麼樣？ –
想到這一點，但德克是快速插入/刪除任何一端，但不是在中間？在一般情況下，我總體上預計隨機訪問類型的使用模式。 – Robinson
添加了關於該筆記的註釋。 – Robinson