C++ 中的高效链表？
Efficient linked list in C++?
这个document说std::list是低效的：
std::list is an extremely inefficient class that is rarely useful. It performs a heap allocation for every element inserted into it, thus having an extremely high constant factor, particularly for small data types.
评论：这让我很惊讶。 std::list 是一个双向链表，所以尽管它在元素构造方面效率低下，但它在 O(1) 时间复杂度上支持 insert/delete，但是这个特性在引用的段落中完全被忽略了。
我的问题：假设我需要一个sequential容器用于小型同质元素，这个容器应该支持元素insert/delete 复杂度为 O(1) 并且 not 需要随机访问（虽然支持随机访问很好，但这里不是必须的）。我也不希望堆分配为 每个元素的构造 引入高常数因子，至少在元素数量较少时。最后，只有当对应的元素被删除时，iterators才会失效。显然我需要一个自定义容器 class，它可能（也可能不是）双向链表的变体。我该如何设计这个容器？
如果无法实现上述规范，那么也许我应该有一个自定义内存分配器，比如说，bump pointer allocator？我知道 std::list 将分配器作为其第二个模板参数。
编辑：我知道我不应该太关心这个问题，从工程的角度来看——足够快就足够了。这只是一个 假设性问题 所以我没有更详细的用例。随意放宽一些要求！
Edit2：我理解 O(1) 复杂度的两种算法由于常数因子的不同可能具有完全不同的性能。
使用两个 std::lists：一个 "free-list" 在启动时预分配了大量节点，另一个 "active" 列表，您 splice 节点来自自由列表。这是常数时间，不需要分配节点。
您的要求完全 std::list 的要求，只是您决定不喜欢基于节点的分配开销。
理智的方法是从头开始，只做你真正需要的：
只需使用std::list。
对其进行基准测试：默认分配器对您的目的来说真的太慢了吗？
否：你完成了。
是：转到 2
将 std::list 与现有的自定义分配器（例如 Boost 池分配器）一起使用
对其进行基准测试：Boost 池分配器对于您的目的来说真的太慢了吗？
否：你完成了。
是：转到 3
根据您在第 1 步和第 2 步中所做的所有分析
，将 std::list 与根据您的独特需求进行微调的手动自定义分配器结合使用
基准如前等等等等
作为最后的手段，考虑做一些更具异国情调的事情。
如果你到了这个阶段，你应该有一个 真正 明确的 SO 问题，其中有很多关于你需要什么的细节（例如 "I need to squeeze n nodes into a cacheline"而不是 "this doc said this thing is slow and that sounds bad").
PS。上面做了两个假设，但都值得研究：
- 正如 Baum mit Augen 指出的那样，进行简单的端到端计时是不够的，因为您需要确定您的时间流向了哪里。它可能是分配器本身，或由于内存布局或其他原因导致的缓存未命中。如果某些东西很慢，您仍然需要先确定 原因，然后才能知道应该更改什么。
您的要求被认为是给定的，但找到削弱要求的方法通常是使事情变得更快的最简单方法。
- 你真的需要在任何地方进行恒定时间的插入和删除，或者只在前面，或者后面，或者两者都需要，而不是在中间？
- 您真的需要那些迭代器失效约束吗？或者它们可以放宽吗？
- 是否有可以利用的访问模式？如果您经常从前面删除一个元素，然后用一个新元素替换它，您可以就地更新它吗？
作为替代方案，您可以使用可增长数组并显式处理链接，作为数组的索引。
未使用的数组元素使用其中一个链接放入链表中。当一个元素被删除时，它被返回到空闲列表。当空闲列表用完时，增长数组并使用下一个元素。
对于新的免费元素，您有两种选择：
- 立即将它们添加到空闲列表中，
- 根据空闲列表中的元素数量与数组大小按需附加它们。
我支持@Useless 的回答，特别是 PS 关于修订要求的第 2 项。如果放宽迭代器失效约束，那么在 SO 上使用 std::vector<> 就是 Stroustrup's standard suggestion for a small-number-of-items container (for reasons already mentioned in the comments). Related questions。
从C++11开始还有std::forward_list.
此外，如果添加到容器中的元素的标准堆分配不够好，那么我会说您需要非常仔细地查看您的确切要求 并针对它们进行微调。
新的 slot_map 提案要求插入和删除的复杂度为 O(1)。
还有一个 link 到 video，其中包含建议的实现和一些先前的工作。
如果我们对元素的实际结构了解得更多，可能会有一些更好的专用关联容器。
std::list is a doubly linked list, so despite its inefficiency in element construction, it supports insert/delete in O(1) time complexity, but this feature is completely ignored in this quoted paragraph.
它被忽略了因为它是一个谎言。
算法复杂度的问题在于它通常衡量一件事情。例如，当我们说 std::map 中的插入是 O(log N) 时，我们的意思是它执行 O(log N) 比较 。 迭代、从内存中获取缓存行等的成本未考虑在内。
当然，这大大简化了分析，但不幸的是，它不一定能清楚地映射到现实世界的实施复杂性。特别是，一个令人震惊的假设是 内存分配是恒定时间 。而且，这是一个大胆的谎言。
通用内存分配器（malloc 和 co）对内存分配的最坏情况复杂度没有任何保证。最坏的情况通常是 OS 相关的，在 Linux 的情况下，它可能涉及 OOM 杀手（筛选正在进行的进程并杀死一个以回收其内存）。
特殊用途的内存分配器可能会成为恒定时间...在特定的分配数量范围内（或最大分配大小）。由于Big-O符号是关于无穷大的极限，因此不能称为O(1)。
因此，where the rubber meets the road，std::list 的实现通常不具有 O(1) insertion/deletion，因为实现依赖于真正的内存分配器，而不是理想的内存分配器。
这很令人沮丧，但是您不必失去所有希望。
最值得注意的是，如果您可以计算出元素数量的上限并且可以预先分配那么多内存，那么您可以设计一个内存分配器，它将执行恒定时间内存分配，给你 O(1) 的错觉。
我建议完全按照@Yves Daoust 所说的去做，除了不使用链表作为自由列表，而是使用向量。推动并弹出向量背面的自由索引。这是分摊的 O(1) 插入、查找和删除，并且不涉及任何指针追踪。它也不需要任何烦人的分配器业务。
除了被删除的节点上的迭代器之外，不使迭代器无效的要求禁止不分配单个节点的每个容器，并且与例如有很大不同。 list 或 map.
然而，我发现在几乎所有情况下，当我 认为 这是必要的时，结果证明只要稍微遵守纪律我也可以不这样做。您可能想验证一下，如果可以，您将受益匪浅。
虽然 std::list 确实是 "correct" 如果你需要像列表这样的东西（对于 CS class，主要是），声明它几乎总是错误的选择是，不幸的是，完全正确。虽然 O(1) 的说法是完全正确的，但与实际计算机硬件的工作方式相比，它仍然很糟糕，这给了它一个巨大的常数因子。请注意，不仅您迭代的对象是随机放置的，而且您维护的节点也是随机放置的（是的，您可以使用分配器以某种方式解决这个问题，但这不是重点）。平均而言，您所做的任何事情都有 两次 一次保证缓存未命中，加上 最多两次 一次用于变异操作的动态分配（一次用于对象，另一个用于节点）。
编辑： 正如下面的@ratchetfreak 所指出的，std::list 的实现通常将对象和节点分配折叠到一个内存块中作为一种优化（类似于什么例如 make_shared 确实如此），这使得平均情况的灾难性有所降低（每个突变分配一个 并且保证缓存未命中一次而不是两次）。
在这种情况下，一个新的、不同的考虑可能是这样做可能也不是完全没有问题的。用两个指针后缀对象意味着在取消引用时反转方向，这可能会干扰自动预取。
另一方面，用指针为对象添加前缀意味着将对象推回两个指针的大小，这意味着在 64 位系统上多达 16 个字节（这可能会在缓存行上拆分一个中等大小的对象每次都有边界）。此外，还要考虑到 std::list 不能承受损坏，例如SSE 代码仅仅是因为它添加了一个秘密偏移量作为特别惊喜（因此，例如异或技巧可能不适用于减少两指针足迹）。可能必须有一定数量的 "safe" 填充以确保添加到列表中的对象仍然按应有的方式工作。
我无法判断这些是实际的性能问题还是我这边的不信任和恐惧，但我相信可以公平地说，草丛中隐藏的蛇可能比人们预期的要多。
著名的 C++ 专家（尤其是 Stroustrup）推荐使用 std::vector 并非没有理由，除非你有充分的理由不这样做。
像以前的许多人一样，我试图聪明地使用（或发明）比 std::vector 更好的东西来解决一个或另一个看起来你可以做得更好的特定专业问题，但它事实证明，简单地使用 std::vector 仍然几乎总是最好的或第二好的选择（如果 std::vector 碰巧不是最好的， std::deque 通常是你需要的）。
与任何其他方法相比，您拥有更少的分配、更少的内存碎片、更少的间接访问以及更有利的内存访问模式。你猜怎么着，它很容易获得并且可以正常工作。
时不时地插入需要所有元素的副本这一事实（通常）完全不是问题。你认为是，但不是。它很少发生，它是线性内存块的副本，这正是处理器所擅长的（与许多双重间接和随机跳过内存相反）。
如果不使迭代器无效的要求确实是绝对必须的，例如，您可以将 std::vector 个对象与动态位集配对，或者，如果没有更好的东西，std::vector<bool>。然后适当地使用 reserve() 这样就不会发生重新分配。删除元素时，不要删除它，而只是在位图中将其标记为已删除（手动调用析构函数）。在适当的时候，当您知道可以使迭代器无效时，调用一个 "vacuum cleaner" 函数来压缩位向量和对象向量。在那里，所有不可预见的迭代器失效都消失了。
是的，这需要维护一个额外的 "element was deleted" 位，这很烦人。但是 std::list 除了实际对象之外，还必须维护两个指针，并且它必须进行分配。使用向量（或两个向量），访问仍然非常有效，因为它以缓存友好的方式发生。迭代，即使在检查已删除的节点时，仍然意味着您在内存中线性或几乎线性移动。
谢谢大家的回答。
这是一个简单但不严格的基准测试。
// 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声称对excel在-O(1)的插入和擦除。而且，由于我要求 insert/delete 的位置，这场比赛严重偏向 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 的 insert/delete 具有更高的常数因子，尽管它是 O(1).
难怪 this 文档说
std::vector is well loved and respected.
编辑：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
我只是想对您的选择做一个小小的评论。我是 vector 的忠实粉丝，因为它的读取速度，你可以直接访问任何元素，并在需要时进行排序。 （例如 class/struct 的向量）。
但无论如何我离题了，我想透露两个绝妙的技巧。
使用向量插入可能很昂贵，所以一个巧妙的技巧，如果你可以不这样做就不要插入。做一个正常的 push_back （放在最后）然后用你想要的元素交换元素。
与删除相同。它们是昂贵的。所以把它和最后一个元素交换，删除它。
我认为满足您所有要求的最简单方法：
- 恒定时间insertion/removal（希望分摊的恒定时间可以插入）。
- 每个元素没有堆 allocation/deallocation。
- 删除时没有迭代器失效。
... 会是这样的，只是利用 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 到向量。然后你做你的标准双链表插入。 free list的逻辑（虽然这个图是我帮别人画的，涉及到SLL，但是你应该明白了）：
确保使用新的布局和手动调用 insertion/removal 上的 dtor 正确构造和销毁元素。如果你真的想泛化它，你还需要考虑异常安全，我们还需要一个只读的常量迭代器。
优缺点
这种结构的好处是它确实允许从列表中的任何地方非常快速地 insertions/removals （即使对于一个巨大的列表），插入顺序被保留以供遍历，并且它永远不会使迭代器无效未直接删除的元素（尽管它会使指向它们的指针无效；如果您不希望指针无效，请使用 deque）。就我个人而言，我发现它比 std::list（我几乎从不使用）更有用。
对于足够大的列表（比方说，比你的整个 L3 缓存更大的情况，你肯定应该期待一个巨大的边缘），这应该大大优于 std::vector 删除和插入 to/from中间和前面。从 vector 中删除元素对于小元素来说可能非常快，但请尝试从 vector 中从前面开始并向后移动一百万个元素。那里的东西会开始爬行，而这个会在眨眼之间完成。当人们开始使用它的 erase 方法从跨越 10k 或更多元素的向量中间删除元素时，std::vector 在 IMO 中被稍微夸大了，尽管我认为这仍然比天真地使用的人更可取链接列表无处不在，每个节点都针对通用分配器单独分配，同时导致大量缓存未命中。
缺点是它只支持顺序访问，每个元素需要两个整数的开销，正如你在上图中看到的，如果你不断地偶尔删除东西，它的空间局部性会降低。
空间局部性退化
当您开始大量删除和插入时空间局部性的丢失 from/to 中间将导致曲折的内存访问模式，可能会从缓存行中逐出数据，然后返回并重新加载它单个顺序
环形。对于任何允许在恒定时间内从中间移除同时同样允许回收 space 同时保留插入顺序的数据结构，这通常是不可避免的。但是，您可以通过提供一些方法来恢复空间局部性，或者您可以 copy/swap 列表。复制构造函数可以通过循环遍历源列表并插入所有元素的方式复制列表，从而返回一个完美连续、缓存友好且没有空洞的向量（尽管这样做会使迭代器无效）。
备选方案：自由列表分配器
满足您要求的替代方法是实现一个符合 std::allocator 的空闲列表并将其与 std::list 一起使用。我从不喜欢绕过数据结构和乱搞自定义分配器，并且通过使用指针而不是 32 位索引，可以使 64 位链接的内存使用量增加一倍，所以我个人更喜欢上述解决方案使用 std::vector 基本上是你的类比内存分配器和索引而不是指针（如果我们使用 std::vector 它们都会减小大小并成为一个要求，因为当 vector 保留新容量时指针将失效）。
索引链表
我称这种东西为 "indexed linked list"，因为链表并不是真正的容器，而是一种将已存储在数组中的东西链接在一起的方式。而且我发现这些索引链表的用处呈指数级增加，因为您不必深入内存池来避免每个节点堆 allocations/deallocations，并且仍然可以保持合理的引用局部性（如果您负担得起的话，很棒的 LOR post-在这里和那里处理事物以恢复空间局部性）。
如果您向节点迭代器添加一个整数以存储前一个节点索引，您也可以将其设为单链接（假设 [=26= 的 32 位对齐要求，在 64 位上免费提供内存费用） ] 和 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 索引的链接节点，以允许跳过已删除的元素。
对于删除，我使用随机打乱的偶数索引源向量来确定要删除的元素以及删除的顺序。这在某种程度上模仿了一个真实世界的用例，其中您通过 indices/iterators 从这些容器的中间删除您以前获得的，例如删除用户以前在他的删除按钮之后使用选取框工具选择的元素（并再次，你真的不应该使用标量 vector::erase 用于非平凡的大小；构建一组索引以删除和使用 remove_if 甚至更好 - 仍然比 vector::erase 一次调用一个迭代器）。
请注意，链接节点的迭代确实变得稍微慢一些，这与迭代逻辑无关，因为向量中的每个条目随着链接的添加而变大（更多内存顺序进程等同于更多的缓存未命中和页面错误）。然而，如果您正在执行诸如从非常大的输入中删除元素之类的操作，那么线性时间和恒定时间删除之间的大型容器的性能偏差是如此巨大，以至于这往往是值得交换的。
这个document说std::list是低效的：
std::list is an extremely inefficient class that is rarely useful. It performs a heap allocation for every element inserted into it, thus having an extremely high constant factor, particularly for small data types.
评论：这让我很惊讶。 std::list 是一个双向链表，所以尽管它在元素构造方面效率低下，但它在 O(1) 时间复杂度上支持 insert/delete，但是这个特性在引用的段落中完全被忽略了。
我的问题：假设我需要一个sequential容器用于小型同质元素，这个容器应该支持元素insert/delete 复杂度为 O(1) 并且 not 需要随机访问（虽然支持随机访问很好，但这里不是必须的）。我也不希望堆分配为 每个元素的构造 引入高常数因子，至少在元素数量较少时。最后，只有当对应的元素被删除时，iterators才会失效。显然我需要一个自定义容器 class，它可能（也可能不是）双向链表的变体。我该如何设计这个容器？
如果无法实现上述规范，那么也许我应该有一个自定义内存分配器，比如说，bump pointer allocator？我知道 std::list 将分配器作为其第二个模板参数。
编辑：我知道我不应该太关心这个问题，从工程的角度来看——足够快就足够了。这只是一个 假设性问题 所以我没有更详细的用例。随意放宽一些要求！
Edit2：我理解 O(1) 复杂度的两种算法由于常数因子的不同可能具有完全不同的性能。
使用两个 std::lists：一个 "free-list" 在启动时预分配了大量节点，另一个 "active" 列表，您 splice 节点来自自由列表。这是常数时间，不需要分配节点。
您的要求完全 std::list 的要求，只是您决定不喜欢基于节点的分配开销。
理智的方法是从头开始，只做你真正需要的：
只需使用
std::list。对其进行基准测试：默认分配器对您的目的来说真的太慢了吗？
否：你完成了。
是：转到 2
将
std::list与现有的自定义分配器（例如 Boost 池分配器）一起使用对其进行基准测试：Boost 池分配器对于您的目的来说真的太慢了吗？
否：你完成了。
是：转到 3
根据您在第 1 步和第 2 步中所做的所有分析
，将std::list与根据您的独特需求进行微调的手动自定义分配器结合使用基准如前等等等等
作为最后的手段，考虑做一些更具异国情调的事情。
如果你到了这个阶段，你应该有一个 真正 明确的 SO 问题，其中有很多关于你需要什么的细节（例如 "I need to squeeze n nodes into a cacheline"而不是 "this doc said this thing is slow and that sounds bad").
PS。上面做了两个假设，但都值得研究：
- 正如 Baum mit Augen 指出的那样，进行简单的端到端计时是不够的，因为您需要确定您的时间流向了哪里。它可能是分配器本身，或由于内存布局或其他原因导致的缓存未命中。如果某些东西很慢，您仍然需要先确定 原因，然后才能知道应该更改什么。
您的要求被认为是给定的，但找到削弱要求的方法通常是使事情变得更快的最简单方法。
- 你真的需要在任何地方进行恒定时间的插入和删除，或者只在前面，或者后面，或者两者都需要，而不是在中间？
- 您真的需要那些迭代器失效约束吗？或者它们可以放宽吗？
- 是否有可以利用的访问模式？如果您经常从前面删除一个元素，然后用一个新元素替换它，您可以就地更新它吗？
作为替代方案，您可以使用可增长数组并显式处理链接，作为数组的索引。
未使用的数组元素使用其中一个链接放入链表中。当一个元素被删除时，它被返回到空闲列表。当空闲列表用完时，增长数组并使用下一个元素。
对于新的免费元素，您有两种选择：
- 立即将它们添加到空闲列表中，
- 根据空闲列表中的元素数量与数组大小按需附加它们。
我支持@Useless 的回答，特别是 PS 关于修订要求的第 2 项。如果放宽迭代器失效约束，那么在 SO 上使用 std::vector<> 就是 Stroustrup's standard suggestion for a small-number-of-items container (for reasons already mentioned in the comments). Related questions。
从C++11开始还有std::forward_list.
此外，如果添加到容器中的元素的标准堆分配不够好，那么我会说您需要非常仔细地查看您的确切要求 并针对它们进行微调。
新的 slot_map 提案要求插入和删除的复杂度为 O(1)。
还有一个 link 到 video，其中包含建议的实现和一些先前的工作。
如果我们对元素的实际结构了解得更多，可能会有一些更好的专用关联容器。
std::listis a doubly linked list, so despite its inefficiency in element construction, it supports insert/delete in O(1) time complexity, but this feature is completely ignored in this quoted paragraph.
它被忽略了因为它是一个谎言。
算法复杂度的问题在于它通常衡量一件事情。例如，当我们说 std::map 中的插入是 O(log N) 时，我们的意思是它执行 O(log N) 比较 。 迭代、从内存中获取缓存行等的成本未考虑在内。
当然，这大大简化了分析，但不幸的是，它不一定能清楚地映射到现实世界的实施复杂性。特别是，一个令人震惊的假设是 内存分配是恒定时间 。而且，这是一个大胆的谎言。
通用内存分配器（malloc 和 co）对内存分配的最坏情况复杂度没有任何保证。最坏的情况通常是 OS 相关的，在 Linux 的情况下，它可能涉及 OOM 杀手（筛选正在进行的进程并杀死一个以回收其内存）。
特殊用途的内存分配器可能会成为恒定时间...在特定的分配数量范围内（或最大分配大小）。由于Big-O符号是关于无穷大的极限，因此不能称为O(1)。
因此，where the rubber meets the road，std::list 的实现通常不具有 O(1) insertion/deletion，因为实现依赖于真正的内存分配器，而不是理想的内存分配器。
这很令人沮丧，但是您不必失去所有希望。
最值得注意的是，如果您可以计算出元素数量的上限并且可以预先分配那么多内存，那么您可以设计一个内存分配器，它将执行恒定时间内存分配，给你 O(1) 的错觉。
我建议完全按照@Yves Daoust 所说的去做，除了不使用链表作为自由列表，而是使用向量。推动并弹出向量背面的自由索引。这是分摊的 O(1) 插入、查找和删除，并且不涉及任何指针追踪。它也不需要任何烦人的分配器业务。
除了被删除的节点上的迭代器之外，不使迭代器无效的要求禁止不分配单个节点的每个容器，并且与例如有很大不同。 list 或 map.
然而，我发现在几乎所有情况下，当我 认为 这是必要的时，结果证明只要稍微遵守纪律我也可以不这样做。您可能想验证一下，如果可以，您将受益匪浅。
虽然 std::list 确实是 "correct" 如果你需要像列表这样的东西（对于 CS class，主要是），声明它几乎总是错误的选择是，不幸的是，完全正确。虽然 O(1) 的说法是完全正确的，但与实际计算机硬件的工作方式相比，它仍然很糟糕，这给了它一个巨大的常数因子。请注意，不仅您迭代的对象是随机放置的，而且您维护的节点也是随机放置的（是的，您可以使用分配器以某种方式解决这个问题，但这不是重点）。平均而言，您所做的任何事情都有 两次 一次保证缓存未命中，加上 最多两次 一次用于变异操作的动态分配（一次用于对象，另一个用于节点）。
编辑： 正如下面的@ratchetfreak 所指出的，std::list 的实现通常将对象和节点分配折叠到一个内存块中作为一种优化（类似于什么例如 make_shared 确实如此），这使得平均情况的灾难性有所降低（每个突变分配一个 并且保证缓存未命中一次而不是两次）。
在这种情况下，一个新的、不同的考虑可能是这样做可能也不是完全没有问题的。用两个指针后缀对象意味着在取消引用时反转方向，这可能会干扰自动预取。
另一方面，用指针为对象添加前缀意味着将对象推回两个指针的大小，这意味着在 64 位系统上多达 16 个字节（这可能会在缓存行上拆分一个中等大小的对象每次都有边界）。此外，还要考虑到 std::list 不能承受损坏，例如SSE 代码仅仅是因为它添加了一个秘密偏移量作为特别惊喜（因此，例如异或技巧可能不适用于减少两指针足迹）。可能必须有一定数量的 "safe" 填充以确保添加到列表中的对象仍然按应有的方式工作。
我无法判断这些是实际的性能问题还是我这边的不信任和恐惧，但我相信可以公平地说，草丛中隐藏的蛇可能比人们预期的要多。
著名的 C++ 专家（尤其是 Stroustrup）推荐使用 std::vector 并非没有理由，除非你有充分的理由不这样做。
像以前的许多人一样，我试图聪明地使用（或发明）比 std::vector 更好的东西来解决一个或另一个看起来你可以做得更好的特定专业问题，但它事实证明，简单地使用 std::vector 仍然几乎总是最好的或第二好的选择（如果 std::vector 碰巧不是最好的， std::deque 通常是你需要的）。
与任何其他方法相比，您拥有更少的分配、更少的内存碎片、更少的间接访问以及更有利的内存访问模式。你猜怎么着，它很容易获得并且可以正常工作。
时不时地插入需要所有元素的副本这一事实（通常）完全不是问题。你认为是，但不是。它很少发生，它是线性内存块的副本，这正是处理器所擅长的（与许多双重间接和随机跳过内存相反）。
如果不使迭代器无效的要求确实是绝对必须的，例如，您可以将 std::vector 个对象与动态位集配对，或者，如果没有更好的东西，std::vector<bool>。然后适当地使用 reserve() 这样就不会发生重新分配。删除元素时，不要删除它，而只是在位图中将其标记为已删除（手动调用析构函数）。在适当的时候，当您知道可以使迭代器无效时，调用一个 "vacuum cleaner" 函数来压缩位向量和对象向量。在那里，所有不可预见的迭代器失效都消失了。
是的，这需要维护一个额外的 "element was deleted" 位，这很烦人。但是 std::list 除了实际对象之外，还必须维护两个指针，并且它必须进行分配。使用向量（或两个向量），访问仍然非常有效，因为它以缓存友好的方式发生。迭代，即使在检查已删除的节点时，仍然意味着您在内存中线性或几乎线性移动。
谢谢大家的回答。 这是一个简单但不严格的基准测试。
// 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声称对excel在-O(1)的插入和擦除。而且，由于我要求 insert/delete 的位置，这场比赛严重偏向 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 的 insert/delete 具有更高的常数因子，尽管它是 O(1).
难怪 this 文档说
std::vectoris well loved and respected.
编辑：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
我只是想对您的选择做一个小小的评论。我是 vector 的忠实粉丝，因为它的读取速度，你可以直接访问任何元素，并在需要时进行排序。 （例如 class/struct 的向量）。
但无论如何我离题了，我想透露两个绝妙的技巧。 使用向量插入可能很昂贵，所以一个巧妙的技巧，如果你可以不这样做就不要插入。做一个正常的 push_back （放在最后）然后用你想要的元素交换元素。
与删除相同。它们是昂贵的。所以把它和最后一个元素交换，删除它。
我认为满足您所有要求的最简单方法：
- 恒定时间insertion/removal（希望分摊的恒定时间可以插入）。
- 每个元素没有堆 allocation/deallocation。
- 删除时没有迭代器失效。
... 会是这样的，只是利用 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 到向量。然后你做你的标准双链表插入。 free list的逻辑（虽然这个图是我帮别人画的，涉及到SLL，但是你应该明白了）：
确保使用新的布局和手动调用 insertion/removal 上的 dtor 正确构造和销毁元素。如果你真的想泛化它，你还需要考虑异常安全，我们还需要一个只读的常量迭代器。
优缺点
这种结构的好处是它确实允许从列表中的任何地方非常快速地 insertions/removals （即使对于一个巨大的列表），插入顺序被保留以供遍历，并且它永远不会使迭代器无效未直接删除的元素（尽管它会使指向它们的指针无效；如果您不希望指针无效，请使用 deque）。就我个人而言，我发现它比 std::list（我几乎从不使用）更有用。
对于足够大的列表（比方说，比你的整个 L3 缓存更大的情况，你肯定应该期待一个巨大的边缘），这应该大大优于 std::vector 删除和插入 to/from中间和前面。从 vector 中删除元素对于小元素来说可能非常快，但请尝试从 vector 中从前面开始并向后移动一百万个元素。那里的东西会开始爬行，而这个会在眨眼之间完成。当人们开始使用它的 erase 方法从跨越 10k 或更多元素的向量中间删除元素时，std::vector 在 IMO 中被稍微夸大了，尽管我认为这仍然比天真地使用的人更可取链接列表无处不在，每个节点都针对通用分配器单独分配，同时导致大量缓存未命中。
缺点是它只支持顺序访问，每个元素需要两个整数的开销，正如你在上图中看到的，如果你不断地偶尔删除东西，它的空间局部性会降低。
空间局部性退化
当您开始大量删除和插入时空间局部性的丢失 from/to 中间将导致曲折的内存访问模式，可能会从缓存行中逐出数据，然后返回并重新加载它单个顺序 环形。对于任何允许在恒定时间内从中间移除同时同样允许回收 space 同时保留插入顺序的数据结构，这通常是不可避免的。但是，您可以通过提供一些方法来恢复空间局部性，或者您可以 copy/swap 列表。复制构造函数可以通过循环遍历源列表并插入所有元素的方式复制列表，从而返回一个完美连续、缓存友好且没有空洞的向量（尽管这样做会使迭代器无效）。
备选方案：自由列表分配器
满足您要求的替代方法是实现一个符合 std::allocator 的空闲列表并将其与 std::list 一起使用。我从不喜欢绕过数据结构和乱搞自定义分配器，并且通过使用指针而不是 32 位索引，可以使 64 位链接的内存使用量增加一倍，所以我个人更喜欢上述解决方案使用 std::vector 基本上是你的类比内存分配器和索引而不是指针（如果我们使用 std::vector 它们都会减小大小并成为一个要求，因为当 vector 保留新容量时指针将失效）。
索引链表
我称这种东西为 "indexed linked list"，因为链表并不是真正的容器，而是一种将已存储在数组中的东西链接在一起的方式。而且我发现这些索引链表的用处呈指数级增加，因为您不必深入内存池来避免每个节点堆 allocations/deallocations，并且仍然可以保持合理的引用局部性（如果您负担得起的话，很棒的 LOR post-在这里和那里处理事物以恢复空间局部性）。
如果您向节点迭代器添加一个整数以存储前一个节点索引，您也可以将其设为单链接（假设 [=26= 的 32 位对齐要求，在 64 位上免费提供内存费用） ] 和 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 索引的链接节点，以允许跳过已删除的元素。
对于删除，我使用随机打乱的偶数索引源向量来确定要删除的元素以及删除的顺序。这在某种程度上模仿了一个真实世界的用例，其中您通过 indices/iterators 从这些容器的中间删除您以前获得的，例如删除用户以前在他的删除按钮之后使用选取框工具选择的元素（并再次，你真的不应该使用标量 vector::erase 用于非平凡的大小；构建一组索引以删除和使用 remove_if 甚至更好 - 仍然比 vector::erase 一次调用一个迭代器）。
请注意，链接节点的迭代确实变得稍微慢一些，这与迭代逻辑无关，因为向量中的每个条目随着链接的添加而变大（更多内存顺序进程等同于更多的缓存未命中和页面错误）。然而，如果您正在执行诸如从非常大的输入中删除元素之类的操作，那么线性时间和恒定时间删除之间的大型容器的性能偏差是如此巨大，以至于这往往是值得交换的。