像大量項目上的deque一樣，但小數目內存使用量小？

Question

我有一大堆特定類型的對象，其中每個對象都可以分配一個雙轉移來保存同一類型的其他對象。我使用deque，因爲我需要在兩端快速訪問，並且因爲任何特定對象都可能引用許多其他對象。

但是，許多或甚至大部分對象都指的是其他很少的對象。在這種情況下，deque的內存使用量非常大。我使用的實現是在第一次push_back（）後立即分配4096個字節。 deque中的每個元素只有8個字節。這是浪費了太多空間，尤其是因爲我製作了許多這樣的對象，因此也導致了許多這樣的對象。同時，我非常需要一個deque（或類似的東西），因爲正如我所說，任何特定的對象實際上都可以引用許多其他對象，儘管大多數對象指的是其他對象。

我的第一個想法是使用capacity（）和reserve（）來增加自我deque，但是我的編譯器告訴我在deque上沒有這樣的函數。

所以，我在想也許是寫一個類似deque的接口的類，這個接口是一個向量和一個deque，其中的向量用於存儲16個元素之後，然後這個vector被扔掉，從那裏開始使用deque。

由於只有在只有少量元素時才使用向量，因此push_front（）和pop_front（）在速度方面效率會很低，因爲我可以使用capacity（）和reserve（）來控制向量，當存在更多元素時，deque使用大量內存應該無關緊要。

但是，在滾動我自己的類之前，我想查看是否已經存在這樣的事情。此外，如果有人知道任何原因，我沒有想到爲什麼這樣的事情是一個壞主意，或者如果有人有任何相關的建議，我很樂意聽到它。

在此先感謝。

Answer 1

你沒有提到你是否需要像隨機訪問迭代器那樣的vector或deque的其他功能。如果你不這樣做，實際上聽起來像是使用list的好選擇。它具有良好的性能插入和兩端刪除。

Answer 2

如果您不需要按索引進行隨機訪問，則可以使用（干擾性）列表。列表允許快速O（1）push_front/push_back()和pop_front/pop_back()。

如果對象不共享，即一個對象只能由至多一個其他對象擁有，那麼入侵列表將是最好的。由於你的對象是相同類型的，它們可以從一個內存池（大數組）分配，以避免任何內存開銷。