从连续内存中的对象创建链表

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。这种结构的主要好处是保持从列表中的任何位置的恒定时间移除，将恒定时间插入到列表中的任何位置，同时允许您以原始的插入顺序遍历，并且以合理的缓存友好的方式。