存儲反轉數據的向量

Question

我使用通過索引引用列表中的事物的協議。存儲這些東西的自然方式是在一個向量中，所以我可以隨時訪問。但就本質而言，在矢量的開始處有很多擺弄，包括插入和刪除。指數越低，就越麻煩。 結果是很多複製向量的其餘部分。

我想以相反的方式存儲事物，在更高的向量索引處（即更高的地址）降低協議索引，儘量減少內容移動，但仍然能夠通過協議透明地隨機訪問元素，指數。除了指針算術和相似之外，理想的容器將是std :: vector的一個簡單替換。我仍然想要指針算術，但可以自己處理相反的順序。

周圍有這樣的課嗎？

也許一些推動容器我找不到或一些晦澀的政策？

編輯：實際上，行程我，我可以用一種載體，以前指數0以及指數length-1後保留空間。 Deque不是像我想的那樣構建的，而是使用大塊內存來防止指針算術。

Answer 1

從您的描述中，聽起來好像項目在矢量的前面插入和刪除，導致矢量的其餘部分被移位。如果這意味着你不依賴於停留在特定指數的項目。這就提出了爲什麼插入和刪除位於矢量的前端 - 維護排序順序的問題？

C++標準庫中有許多容器保持排序順序，包括對數時間插入和刪除，例如， std::multi_set。

當插入和刪除非常侷限，因爲它聽起來像（但your're真不明白），你也許可以使用光標差距結構，也被稱爲gap buffer，以減少插入和刪除到恆定的時間，保持恆定的時間索引。一個代價是索引涉及額外的間接。但是這可能是不成熟的優化，所以如果性能是重要的，那麼MEASURE。