5
我在尋找一個像std::vector索引的C++容器類，但它具有快速插入，刪除和索引功能。例如，使用底層平衡樹實現的接口將具有O（logN）插入/刪除和O（logN）索引。快速插入和索引的容器？
要清楚：我不是在尋找std::map<int, T>。在索引N處插入元素應該增加數組中所有後續元素的索引，這與std::map<int, T>不一樣。
我發現AVL Array這正是我正在尋找的。它有正確的界面，但我想看看是否有其他選擇。
你知道任何其他（生產質量）實現嗎？也許更受歡迎的東西（確實有助於提高某種程度的東西？）。內存佔用更小的東西？ （在AVL陣列中保存指針的節點在我的機器上是64字節。）
可以解釋爲何你需要隨機訪問？ – BeyelerStudios 2014-09-03 16:01:44
這似乎是脫離主題 - 尋找軟件/庫建議。 – 2014-09-03 16:04:53
我不認爲有一個簡單的（在數據結構方面）做你想做的事情，所以它需要2 ptrs爲next/prev和3 ptrs爲父/左/右加上原始指針。對於64位環境，總共有6個指針= 48個字節。就內存佔用而言，這是至少可以達到的（我認爲）。 – mostruash 2014-09-03 17:19:40