從連續內存中的對象創建鏈表

Question

我想迭代存儲在一起的對象（以減少緩存未命中）。我是否可以做到這一點，我可以通過創建一個矢量來實現這一點，以便我的所有對象連續定位，然後使用對X的引用創建鏈接列表？這樣我就可以很快插入到列表的頭部，並且當我遍歷列表元素時，它們不會彼此離得太遠，因爲它們都來自同一個向量？

Answer 1

簡短的回答是肯定的。由於持續的內存存儲，Vector比鏈表更適合您的需求。迭代一個向量並獲取它的元素通常比鏈表快得多，向量中的項不會太大。

Answer 2

您是否需要隨機訪問存儲中的每個項目或順序訪問。內存容量有多大，有多少元素？最長的元素有多大？

有很多方法來訪問存儲，存儲的

• 原始順序遍歷
• 擴充的指針的下一個元素
• 擴充與每個存儲元件相互抵消存儲元件（跳過計數）到下一個元素
• 創建一個單獨的數組（向量）指針到存儲器中
• 創建一個單獨的數組（向量）帶有偏移量的存儲器

Answer 3

使用std::vector來存儲您的節點的鏈接列表可以在某些情況下非常有用和有效的策略，像一個你需要能夠除去來自固定時間的中間分子，還是回收空空間，插入元素在恆定時間前/中，必須遍歷順序匹配的廣告訂單，保持合理的緩存友好訪問模式和減半64位內存使用環節，比如：

template <class T> 
struct Node 
{ 
    // Stores the memory for the element stored in the node. 
    typename std::aligned_storage<sizeof(T), alignof(T)>::type data; 

    // Points to previous node in the array or previous 
    // free node in the array if the node has been removed. 
    // Stores -1 if there is no previous node. 
    int32_t prev; 

    // Points to next node in the array or next free 
    // node in the array if the node has been removed. 
    // Stores -1 if there is no next node. 
    int32_t next; 
}; 

template <class T> 
struct List 
{ 
    // Stores all the nodes contiguously. 
    std::vector<Node<T>> nodes; 

    // Points to the first node in the list. 
    // Stores -1 if the list is empty. 
    int32_t head; 

    // Points to the first free node in the list. 
    // Stores -1 if the free list is empty. 
    int32_t free_head; 
}; 

std::vector as Memory Allocator

在這種情況下，我們有效地將std::vector轉換爲我們的節點內存分配器，並將64位指針存儲爲32位索引，並將相對索引存儲到一個數組中。

然而，缺點這一解決方案，你可以在我的圖跟上面（對不起，如果這是一個有點混亂，這圖表示擦除並重新插入後會發生什麼）是，如果你開始清除從要素中間並重新插入和回收空閒空間，雖然您可以繼續以原始插入順序遍歷元素，但您會開始導致更多的緩存未命中，因爲遵循鏈接可能讓您開始在內存中來回鋸齒形（不再遍歷數組以完美的順序訪問模式）。插入到中間時也會發生同樣的情況（這可以在常量內完成，但中間的節點可能會分配到數組的後部，從而降低參考的局部性）。這可能會導致加載一個緩存行中的內存區域，以便在它只用於返回到同一個內存區域並重新加載之前將其逐出。

優化通

所以這些類型的「混合」陣列/鏈表的解決方案往往在空間局部性降解的下跌空間越多，你擦除和從/到中間插入元素給他們。緩解這種情況的一種方法是，偶爾會不時地對列表進行「優化複製/交換」，這會恢復空間局部性，並讓您回到每個鏈接指向數組中前一個索引的點，並且每個next鏈接指向下一個。

還是比平時

不過要好得多，即使沒有這些「優化通行證」，它仍傾向於招致很多，少了許多緩存從中間和reinsertions比鏈表其節點衆多清除後，即使錯過是使用通用分配器分配的。在後一種情況下，節點可能會散佈在內存中的所有位置，從而導致您訪問的每個節點都可能導致緩存未命中，這就是當您遇到鏈接列表的惡名在許多用途中效率特別低案例。此外，您還可以在64位機器上使用32位索引（除非實際需要數十億個節點）而不是64位指針，從而減少鏈接的內存使用量。

收錄鏈表

我使用鏈表一大堆但它們總是使用這樣的溶液，儲存在連續陣列（無論是一個連續的緩衝器，用於存儲所有節點，或一系列的節點每個存儲256個節點的連續緩衝區，例如），並且通常使用相對索引而不是絕對指針指向節點。當鏈接列表像這樣使用時，它們在實踐中變得更有效率。

內存池

早在32位的天，我以前只是使用內存池這個像一個空閒列表符合std::allocator爲了這個目的，但是經過64位硬件走紅，大小一個在內存使用中加倍的指針，我發現開始使用隨機訪問數據結構作爲模擬「內存分配器」和相關的32位索引更有用。如果要在列表中存儲的元素僅爲3個單精度浮點數（12個字節），則將指針的大小減半是遠遠不夠的。我發現最大的實際麻煩就是不得不使用索引來處理所有事情，而不能直接獲取指向對象的數據，因爲這會使內存佔用量增加一倍，如果我們使用std::vector作爲我們的模擬內存分配器，將無法工作它會在每次重新分配內存時使指針無效。

交換和-pop_back

請注意，如果你不關心遍歷順序，不關心指數的無效，並不需要能夠在固定時間的任何位置插入，這個數據結構並不是那麼有用。在這種情況下，更有用的方法是使用一個向量，將要刪除的元素與最後一個元素進行交換，然後使用pop_back。這種結構的主要好處是保持從列表中的任何位置的恆定時間移除，將恆定時間插入到列表中的任何位置，同時允許您以原始的插入順序遍歷，並且以合理的緩存友好的方式。