C++中的高效链表？

Question

该文件说std::list效率低下:

std :: list是一个非常低效的类,很少有用.它为插入其中的每个元素执行堆分配,因此具有极高的常数因子,特别是对于小数据类型.

评论:这让我感到惊讶.std::list是一个双向链表,所以尽管它的元件结构效率低下,它支持插入/删除在O(1)的时间复杂度,但这种功能在此引用的段落完全忽略.

我的问题:说我需要一个连续的小尺寸均匀元素的容器,这种容器应支持元素插入/为O删除(1)复杂性和不并不需要随机存取(虽然支持随机访问是好的,它不是必须的这里).我也不希望堆分配为每个元素的构造引入高常量因子,至少当元素的数量很小时.最后,只有在删除相应的元素时,迭代器才会失效.显然我需要一个自定义容器类,它可能(或可能不)是双向链表的变体.我该如何设计这个容器？

如果无法实现上述规范,那么也许我应该有一个自定义内存分配器,比如说,指针分配器？我知道std::list将分配器作为其第二个模板参数.

编辑:我知道从工程的角度来看,我不应该太关心这个问题 - 足够快就足够了.这只是一个假设的问题,所以我没有更详细的用例.随意放松一些要求!

编辑2:据我所知,O(1)复杂度的两种算法由于其常数因子的不同而具有完全不同的性能.

Answer 1

你的要求是准确的那些std::list,但你决定你不喜欢基于节点分配的开销.

理智的方法是从顶部开始,只做你真正需要的事情:

1. 只是用std::list.

   基准测试:默认的分配器对你的目的来说真的太慢了​​吗？

   • 不,你做完了.

   • 是的:转到2

2. std::list与现有的自定义分配器一起使用,例如Boost池分配器

   基准测试:Boost池分配器真的太慢了​​吗？

   • 不,你做完了.

   • 是的:转到3

3. 使用std::list与手卷自定义分配器微调到您的独特需求的基础上,所有的分析,你在步骤1和2一样

   基准与以前一样等.

4. 考虑做一些更奇特的事情作为最后的手段.

   如果你到了这个阶段,你应该有一个非常明确的SO问题,有很多关于你需要的详细信息(例如"我需要将n个节点压缩到一个缓存行"而不是"这个doc说这个东西是慢,听起来很糟糕").

PS.以上做了两个假设,但都值得研究:

1. 正如Baum mit Augen指出的那样,做简单的端到端计时是不够的,因为你需要确定你的时间在哪里.它可能是分配器本身,或者由于内存布局而导致的高速缓存未命中等.如果事情变得缓慢,你仍然需要确定为什么在你知道什么应该改变之前.

2. 您的要求是作为一个给定的,但找到削弱要求的方法往往是使事情更快的最简单方法.

   • 你真的需要在任何地方进行恒定时间的插入和删除,或者只在前面,后面,或两者都插入和删除,而不是在中间？
   • 你真的需要那些迭代器失效约束,还是可以放松？
   • 你有可以利用的访问模式吗？如果您经常从前面删除元素然后用新元素替换它,您是否可以就地更新它？

Answer 2

作为替代方案,您可以使用可增长的数组并显式处理链接,作为数组的索引.

未使用的数组元素使用其中一个链接放入链接列表中.删除元素时,会将其返回到空闲列表.当空闲列表用完时,增长数组并使用下一个元素.

对于新的免费元素,您有两种选择:

• 将它们立即附加到免费列表中,
• 根据空闲列表中的元素数量与数组大小,按需添加它们.

Answer 3

除了正在删除的节点上的迭代器之外,不要使迭代器无效的要求是禁止每个不分配单个节点的容器,并且与例如list或者有很大不同map.
但是,我发现在几乎每一种情况下,当我认为这是必要的时候,结果却是一点点的纪律我也可以不用.您可能想验证是否可以,您将受益匪浅.

虽然std::list确实是"正确"的东西,如果你需要像列表这样的东西(主要是CS类),那么它几乎总是错误的选择的说法,不幸的是,完全正确.虽然O(1)声明完全正确,但它与实际计算机硬件的工作方式相比仍然很糟糕,这给它一个巨大的常数因素.请注意,不仅是您随机放置的对象,而且您维护的节点也是(是的,您可以通过分配器以某种方式解决这个问题,但这不是重点).平均而言,对于您执行的任何操作,您都有两个保证的缓存未命中,加上最多两个用于变异操作的动态分配(一个用于对象,另一个用于节点).

编辑:正如下面@ratchetfreak所指出的那样,std::list通常将对象和节点分配的实现作为优化(类似于例如make_shared)进行折叠,这使得平均情况有点不那么灾难性(每个突变一个分配,一个保证)缓存未命中而不是两个).
在这种情况下,一个新的,不同的考虑可能是这样做也可能不是完全无故障.使用两个指针对对象进行后缀处理意味着在取消引用时反转方向,这可能会干扰自动预取.
另一方面,使用指针对对象进行前缀意味着将对象推回两个指针的大小,这意味着64位系统上的16个字节(可能会在缓存行上分割中型对象)每次都是边界).此外,还要考虑std::list不能单独破坏例如SSE代码,因为它增加了一个秘密偏移作为特殊意外(例如,xor-trick可能不适用于减少双指针足迹).可能必须有一些"安全"填充,以确保添加到列表中的对象仍然按照应有的方式工作.
我无法判断这些是实际的性能问题,还是仅仅是对我的不信任和恐惧,但我相信可以说,草中可能有更多的蛇藏在人们的预期之中.

高调的C++专家(Stroustrup,特别是)推荐使用它是不可取的,std::vector除非你有充分的理由不这样做.

和以前的很多人一样,我试图聪明地使用(或发明)一些比std::vector一个或另一个特殊的专业问题更好的东西,它看起来你可以做得更好,但事实证明,简单地使用std::vector仍然几乎总是最好的,或第二好的选择(如果std::vector碰巧不是最好的,std::deque通常是你需要的).
与其他任何方法相比,您的分配更少,内存碎片更少,间接更少,内存访问模式更有利.猜猜看,它是现成的,只是有效.
事实上,每一个插件都需要所有元素的副本(通常)是完全无问题.你认为是,但事实并非如此.它很少发生,它是一个线性内存块的副本,这正是处理器擅长的(与许多双间接和内存随机跳转相反).

如果不要使迭代器无效的要求实际上是绝对必须的,你可以例如将一个std::vector对象与动态bitset 配对,或者由于缺少更好的东西,a std::vector<bool>.然后reserve()适当使用,这样就不会发生重新分配.删除元素时,不要删除它,只是在位图中将其标记为已删除(手动调用析构函数).在适当的时候,当您知道使迭代器无效时,可以调用"真空吸尘器"功能来压缩位向量和对象向量.在那里,所有不可预见的迭代器失效都消失了.

是的,这需要保留一个额外的"元素被删除"位,这很烦人.但是std::list必须保持两个指针,除了实际对象之外,还必须进行分配.使用向量(或两个向量),访问仍然非常有效,因为它以缓存友好的方式发生.即使在检查已删除的节点时,迭代仍然意味着您在内存上线性或几乎线性移动.

Answer 4

std::list是一个双向链表,所以尽管它在元素构造方面效率低,但它支持O(1)时间复杂度的插入/删除,但在这个引用的段落中完全忽略了这个特性.

它被忽略了,因为它是谎言.

算法复杂性的问题在于它通常测量一件事.例如,当我们说a中的插入std::map是O(log N)时,我们的意思是它执行O(log N)比较.不考虑迭代,从内存中提取缓存行等的成本.

当然,这极大地简化了分析,但遗憾的是,它并不一定能够清晰地映射到现实世界的实施复杂性.特别是,一个令人震惊的假设是内存分配是恒定时间.而且,这是一个大胆的谎言.

通用内存分配器(malloc和co)对内存分配的最坏情况复杂性没有任何保证.最糟糕的情况通常是依赖于操作系统,在Linux的情况下,它可能涉及OOM杀手(筛选正在进行的进程并杀死一个以回收其内存).

特殊用途的存储器分配器可以在特定的分配数量范围内(或最大分配大小)保持恒定的时间.由于Big-O表示法在无限远处是极限,因此不能称为O(1).

因此,在橡胶遇到道路的地方,实施std::list通常不具有O(1)插入/删除,因为实现依赖于真实的内存分配器,而不是理想的内存分配器.

这非常令人沮丧,但你不必失去所有的希望.

最值得注意的是,如果你可以找出元素数量的上限并且可以预先分配那么多内存,那么你可以制作一个内存分配器,它将执行恒定时间内存分配,给你一种O的错觉( 1).

Answer 5

使用双std::listS:一个"空闲列表"这是在启动时大藏匿节点的预分配,并为您的其他"活动"列表splice从自由列表中的节点.这是恒定时间,不需要分配节点.

Answer 6

新的slot_map提议声明O(1)用于插入和删除.

还有一个视频链接,其中包含建议的实施和一些以前的工作.

如果我们对元素的实际结构有更多了解,可能会有一些特殊的关联容器更好.

Answer 7

我认为满足您所有要求的最简单方法：

1. 恒定时间插入/删除（希望摊销恒定时间对于插入来说是可以的）。
2. 每个元素没有堆分配/释放。
3. 删除时迭代器不会失效。

...会是这样的，只需利用std::vector：

template <class T>
struct Node
{
    // Stores the memory for an instance of 'T'.
    // Use placement new to construct the object and
    // manually invoke its dtor as necessary.
    typename std::aligned_storage<sizeof(T), alignof(T)>::type element;

    // Points to the next element or the next free
    // element if this node has been removed.
    int next;

    // Points to the previous element.
    int prev;
};

template <class T>
class NodeIterator
{
public:
    ...
private:
    std::vector<Node<T>>* nodes;
    int index;
};

template <class T>
class Nodes
{
public:
    ...
private:
    // Stores all the nodes.
    std::vector<Node> nodes;

    // Points to the first free node or -1 if the free list
    // is empty. Initially this starts out as -1.
    int free_head;
};

...希望有一个更好的名字Nodes（我有点醉了，现在不太擅长想名字）。我将把实现留给你，但这就是总体思路。当您删除一个元素时，只需使用索引进行双向链表删除并将其推送到空闲头即可。迭代器不会失效，因为它存储了向量的索引。插入时检查自由头是否为-1。如果没有，则覆盖该位置的节点并弹出。否则push_back为向量。

插图

图（节点连续存储在内部std::vector，我们只需使用索引链接即可以无分支方式跳过元素，并在任何地方进行恒定时间删除和插入）：

假设我们要删除一个节点。这是标准的双向链表删除，除了我们使用索引而不是指针，并且您还将节点推送到空闲列表（仅涉及操作整数）：

链接的删除调整：

将删除的节点推送到空闲列表：

现在假设您插入到此列表中。在这种情况下，您可以弹出空闲头并覆盖该位置的节点。

插入后：

在恒定时间内插入到中间也应该很容易弄清楚。基本上，如果空闲堆栈为空，您只需插入到空闲头或push_back向量。然后进行标准的双链表插入。空闲列表的逻辑（虽然我为其他人制作了这个图并且它涉及 SLL，但您应该明白这个想法）：

确保在插入/删除时使用新的放置和手动调用 dtor 来正确构造和销毁元素。如果你真的想概括它，你还需要考虑异常安全，我们还需要一个只读 const 迭代器。

优点和缺点

这种结构的好处是，它确实允许从列表中的任何位置非常快速地插入/删除（即使对于一个巨大的列表），保留插入顺序以供遍历，并且它永远不会使未直接删除的元素的迭代器无效（尽管它会使指向它们的指针无效；deque如果您不希望指针无效，请使用）。就我个人而言，我发现它比std::list（我几乎从未使用过）有更多用处。

对于足够大的列表（例如，大于整个 L3 缓存，在这种情况下，您肯定应该期望有一个巨大的边缘），这应该远远优于std::vector中间和前面的删除和插入。对于较小的向量，从向量中删除元素可能相当快，但尝试从向量中从前面开始向后删除一百万个元素。那里的事情会开始爬行，而这一件事将在一眨眼的时间内完成。std::vector在我看来，当人们开始使用它的erase方法从跨越 10k 元素或更多元素的向量中间删除元素时，它有点被夸大了，尽管我认为这仍然比人们天真地在每个节点都使用链表的方式中使用链表更可取。针对通用分配器单独分配，同时导致大量缓存未命中。

缺点是它只支持顺序访问，每个元素需要两个整数的开销，正如您在上图中看到的，如果您不断地偶尔删除东西，它的空间局部性就会降低。

空间局部性退化

当您开始从中间删除和插入大量数据时，空间局部性的丢失将导致曲折的内存访问模式，可能会从缓存行中逐出数据，然后在单个顺序循环期间返回并重新加载数据。对于任何允许在恒定时间内从中间删除同时允许回收该空间同时保留插入顺序的数据结构来说，这通常是不可避免的。但是，您可以通过提供某种方法来恢复空间局部性，或者可以复制/交换列表。复制构造函数可以通过迭代源列表并插入所有元素的方式复制列表，从而返回一个完美连续、缓存友好且没有漏洞的向量（尽管这样做会使迭代器无效）。

替代方案：空闲列表分配器

满足您要求的另一种方法是实现一个符合 的空闲列表std::allocator并将其与 一起使用std::list。我从来不喜欢接触数据结构并搞乱自定义分配器，而且通过使用指针而不是 32 位索引，会使 64 位上链接的内存使用量增加一倍，所以我更喜欢将上述解决方案个人使用std::vector为基本上是你的类比内存分配器和索引而不是指针（如果我们使用它们，它们都会减少大小并成为一个要求，std::vector因为当向量保留新容量时指针将失效）。

索引链表

我将这种东西称为“索引链表”，因为链表实际上并不是一个容器，而是一种将已存储在数组中的内容链接在一起的方式。我发现这些索引链表更加有用，因为您不必深入内存池来避免每个节点的堆分配/释放，并且仍然可以保持合理的引用局部性（如果您有能力承担后期处理，那就太棒了，LOR）在这里或那里处理事物以恢复空间局部性）。

如果您向节点迭代器添加一个整数来存储前一个节点索引，您还可以使其成为单链接（假设 32 位对齐要求和 64 位指针对齐要求，int64 位上不会产生内存费用）。但是，您随后将无法添加反向迭代器并使所有迭代器成为双向迭代器。

基准

我制作了上述内容的快速版本，因为您似乎对它们感兴趣：发布版本，MSVC 2012，没有检查迭代器或类似的东西：

--------------------------------------------
- test_vector_linked
--------------------------------------------
Inserting 200000 elements...
time passed for 'inserting': {0.000015 secs}

Erasing half the list...
time passed for 'erasing': {0.000021 secs}
time passed for 'iterating': {0.000002 secs}
time passed for 'copying': {0.000003 secs}

Results (up to 10 elements displayed):
[ 11 13 15 17 19 21 23 25 27 29 ]

finished test_vector_linked: {0.062000 secs}
--------------------------------------------
- test_vector
--------------------------------------------
Inserting 200000 elements...
time passed for 'inserting': {0.000012 secs}

Erasing half the vector...
time passed for 'erasing': {5.320000 secs}
time passed for 'iterating': {0.000000 secs}   
time passed for 'copying': {0.000000 secs}

Results (up to 10 elements displayed):
[ 11 13 15 17 19 21 23 25 27 29 ]

finished test_vector: {5.320000 secs}

太懒了，无法使用高精度计时器，但希望这能说明为什么不应该在重要输入大小的关键路径中使用vector's线性时间方法，上面的时间要长约 86 倍（并且越大，指数越差）输入大小——我最初尝试使用 200 万个元素，但在等待了近 10 分钟后放弃了）以及为什么我认为这种用途有点过分夸大了。也就是说，我们可以将从中间的删除转变为非常快速的恒定时间操作，而无需打乱元素的顺序，无需使存储它们的索引和迭代器无效，并且同时仍然使用...我们所要做的就是简单地做到这一点存储带有索引的链接节点，以允许跳过已删除的元素。erasevectorvectorvectorprev/next

为了删除，我使用偶数索引的随机打乱源向量来确定要删除哪些元素以及以什么顺序删除。这在某种程度上模仿了现实世界的用例，您通过以前获得的索引/迭代器从这些容器的中间删除，例如在用户按下删除按钮后删除用户以前使用选框工具选择的元素（同样，您确实不应该使用标量vector::erase来实现不平凡的大小；最好构建一组索引来删除和使用——仍然比一次调用一个迭代器remove_if更好）。vector::erase

请注意，随着链接节点的增加，迭代确实会变得稍微慢一些，这与迭代逻辑无关，因为向量中的每个条目随着链接的添加而变得更大（更多的内存用于顺序处理相当于更多的缓存）未命中和页面错误）。然而，如果您正在执行从非常大的输入中删除元素之类的操作，那么对于线性时间和恒定时间删除之间的大型容器来说，性能偏差是如此之大，以至于这往往是值得进行的交换。