C ++中的高效链表？

Question

这个document说std::list效率低下：

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

评论：这让我感到惊讶。 std::list是一个双向链表，因此尽管它在元素构造方面效率低，但它支持O（1）时间复杂度的插入/删除，但在这个引用的段落中完全忽略了这个特性。

我的问题：我需要一个用于小型同类元素的顺序容器，这个容器应该支持O（1）复杂度中的元素插入/删除，并且不需要随机访问（虽然支持随机访问很好，但它不是必须的这里）。我也不希望堆分配为每个元素的构造引入高常量因子，至少当元素的数量很小时。最后，只有在删除相应的元素时，迭代器才会失效。显然我需要一个自定义容器类，它可能（或可能不）是双向链表的变体。我该如何设计这个容器？

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

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

编辑2：据我所知，O（1）复杂度的两种算法由于其常数因子的不同而具有完全不同的性能。

Answer 1

我看到满足您所有要求的最简单方式：

恒定时间插入/移除（希望摊销的常数时间可以插入）。
每个元素没有堆分配/释放。
删除时没有迭代器失效。

......会是这样的，只是利用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方法从跨越10k或更多元素的向量中间移除元素时，erase的IMO总是如此轻微过度，尽管我认为这仍然优于人们天真地使用链接列表到处都是节点是针对通用分配器单独分配的，同时导致缓存未命中。

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

空间位置退化

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

替代方案：免费列表分配器

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

索引链接列表

我把这种东西称为“索引链表”，因为链表实际上不是一个容器，而是将已存储在数组中的东西链接在一起的方式。我发现这些索引链接列表指数级更有用，因为您不必深入内存池以避免每个节点的堆分配/解除分配，并且仍然可以保持合理的引用位置（如果您能负担得起，则可以获得很好的LOR）处理事物以及恢复空间局部性。

如果向节点迭代器添加一个更多的整数来存储前一个节点索引（在64位时没有内存费用，假设int为32位对齐要求，指针为64位），也可以单独链接。但是，您失去了添加反向迭代器并使所有迭代器双向的能力。

基准

我掀起了上面的快速版本，因为你似乎对它们感兴趣：发布版本，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线性时间erase方法来获得非常重要的输入大小，其中vector需要大约86倍（以指数方式）更糟糕的是输入大小越大 - 我最初尝试了200万个元素但是在等待了将近10分钟之后就放弃了）以及为什么我认为vector对于这种用途来说有点过于夸张。也就是说，我们可以将中间删除转换为一个非常快速的恒定时间操作，而不会改变元素的顺序，而不会使索引和迭代器存储它们失效，同时仍然使用vector ...我们所要做的就是简单地制作它存储带有prev/next索引的链接节点，以允许跳过已删除的元素。

为了删除，我使用了随机改组的偶数索引源向量来确定要删除的元素以及以什么顺序删除。这有点模仿一个真实世界的用例，你通过之前获得的索引/迭代器从这些容器的中间移除，比如删除用户以前用删除按钮后用选框工具选择的元素（再次，你真的不应该使用标量vector::erase这个非平凡的大小;建立一组索引以删除和使用remove_if甚至更好 - 仍然比vector::erase一次要求一个迭代器更好。

请注意，链接节点的迭代确实变得稍微慢一些，这与迭代逻辑没有关系，因为向量中的每个条目都随着链接的添加而变大（顺序处理的内存越多，等同于更多缓存）遗漏和页面错误）。然而，如果你正在做一些事情，比如从非常大的输入中删除元素，那么线性时间和恒定时间去除之间的大容器的性能偏差是如此的史诗般的，这往往是值得交换的。

Answer 2

我只想对你的选择做一个小评论。我是矢量的忠实粉丝，因为它具有读取速度，你可以直接访问任何元素，并在需要时进行排序。（例如，类/结构的向量）。

但无论如何我离题了，我想透露两个漂亮的提示。使用矢量插入可能是昂贵的，所以一个巧妙的技巧，如果你可以逃避不做，不要插入。做一个正常的push_back（放在最后），然后用你想要的元素交换元素。

与删除相同。它们是昂贵的。所以将它与最后一个元素交换，删除它。

Answer 3

感谢所有的答案。这是一个简单 - 虽然不严谨 - 的基准。

// list.cc
#include <list>
using namespace std;

int main() {
    for (size_t k = 0; k < 1e5; k++) {
        list<size_t> ln;
        for (size_t i = 0; i < 200; i++) {
            ln.insert(ln.begin(), i);
            if (i != 0 && i % 20 == 0) {
                ln.erase(++++++++++ln.begin());
            }
        }
    }
}

和

// vector.cc
#include <vector>
using namespace std;

int main() {
    for (size_t k = 0; k < 1e5; k++) {
        vector<size_t> vn;
        for (size_t i = 0; i < 200; i++) {
            vn.insert(vn.begin(), i);
            if (i != 0 && i % 20 == 0) {
                vn.erase(++++++++++vn.begin());
            }
        }
    }
}

这个测试旨在测试std::list声称擅长什么 - O（1）插入和擦除。并且，由于我要求插入/删除的位置，这个种族严重偏向于std::vector，因为它必须移动所有以下元素（因此O（n）），而std::list不需要这样做。

现在我编译它们。

clang++ list.cc -o list
clang++ vector.cc -o vector

并测试运行时。结果是：

  time ./list
  ./list  4.01s user 0.05s system 91% cpu 4.455 total
  time ./vector
  ./vector  1.93s user 0.04s system 78% cpu 2.506 total

std::vector赢了。

编译与优化O3，std::vector仍然获胜。

  time ./list
  ./list  2.36s user 0.01s system 91% cpu 2.598 total
  time ./vector
  ./vector  0.58s user 0.00s system 50% cpu 1.168 total

std::list必须为每个元素调用堆分配，而std::vector可以批量分配堆内存（尽管它可能依赖于实现），因此std::list的插入/删除具有更高的常量因子，尽管它是O（1）。

难怪this文件说

std::vector深受喜爱和尊重。

编辑：std::deque在某些情况下甚至更好，至少对于这项任务。

// deque.cc
#include <deque>
using namespace std;

int main() {
    for (size_t k = 0; k < 1e5; k++) {
        deque<size_t> dn;
        for (size_t i = 0; i < 200; i++) {
            dn.insert(dn.begin(), i);
            if (i != 0 && i % 20 == 0) {
                dn.erase(++++++++++dn.begin());
            }
        }
    }
}

没有优化：

./deque  2.13s user 0.01s system 86% cpu 2.470 total

使用O3优化：

./deque  0.27s user 0.00s system 50% cpu 0.551 total

Answer 4

您的要求正是std::list的要求，除了您已经决定不喜欢基于节点的分配的开销。

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

只需使用std::list。基准测试：默认的分配器对你的目的来说真的太慢了吗？不，你做完了。是的：转到2
将std::list与现有的自定义分配器（如Boost池分配器）一起使用基准测试：Boost池分配器真的太慢了吗？不，你做完了。是的：转到3
根据您在步骤1和步骤2中执行的所有分析，将std::list与手动定制分配器精确调整以满足您的独特需求基准与以前一样等。
考虑做一些更奇特的事情作为最后的手段。如果你到了这个阶段，你应该有一个非常明确的SO问题，有很多关于你需要的详细信息（例如“我需要将n个节点压缩到一个缓存行”而不是“这个文件说这个东西是慢，听起来很糟糕“）。

PS。以上做了两个假设，但都值得研究：

正如Baum mit Augen指出的那样，做简单的端到端计时是不够的，因为你需要确定你的时间在哪里。它可能是分配器本身，或者由于内存布局而导致的高速缓存未命中等。如果事情变得缓慢，你仍然需要确定为什么在你知道什么应该改变之前。
您的要求是作为一个给定的，但找到削弱要求的方法往往是使事情更快的最简单方法。你真的需要在任何地方进行恒定时间的插入和删除，或者只在前面，后面，或两者都插入和删除，而不是在中间？你真的需要那些迭代器失效约束，还是可以放松？你有可以利用的访问模式吗？如果您经常从前面删除元素然后用新元素替换它，您是否可以就地更新它？

Answer 5

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

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

对于新的免费元素，您有两种选择：

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

Answer 6

除了正在删除的节点上的迭代器之外不要使迭代器无效的要求是禁止每个不分配单个节点的容器，并且与例如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配对，或者由于缺少更好的东西，可以使用std::vector<bool>。然后适当地使用reserve()，这样就不会发生重新分配。删除元素时，不要删除它，只是在位图中将其标记为已删除（手动调用析构函数）。在适当的时候，当您知道使迭代器无效时，可以调用“真空吸尘器”功能来压缩位向量和对象向量。在那里，所有不可预见的迭代器失效都消失了。

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

Answer 7

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

它被忽略了，因为它是谎言。

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

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

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

特殊用途的存储器分配器可以在特定的分配数量范围内（或最大分配大小）进行恒定时间。由于Big-O表示法在无限远处是极限，因此不能称为O（1）。

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

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

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

Answer 8

使用两个std::lists：一个“自由列表”，它在启动时预先分配了大量的节点，另一个“活动”列表，你从自由列表中splice节点。这是恒定时间，不需要分配节点。

Answer 9

新的slot_map提案要求插入和删除O（1）。

还有一个链接到video，提议的实施和一些以前的工作。

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

Answer 10

我建议做正确的@Yves Daoust所说的，除了使用自由列表的链表，使用向量。按下并弹出向量背面的自由索引。这是分摊O（1）插入，查找和删除，并且不涉及任何指针追逐。它也不需要任何恼人的分配器业务。

Answer 11

我是第二个@Useless'回答，特别是关于修改要求的PS第2项。如果放宽迭代器失效约束，那么使用std::vector<>是Stroustrup's standard suggestion用于少量项容器（由于注释中已经提到的原因）。 Related questions on SO。

从C ++ 11开始，还有std::forward_list。

此外，如果添加到容器中的元素的标准堆分配不够好，那么我会说您需要仔细查看您的确切要求并对它们进行微调。

C ++中的高效链表？

问题描述投票：42回答：11

11个回答

最新问题

C ++中的高效链表？

问题描述 投票：42回答：11

11个回答

最新问题

问题描述投票：42回答：11