C ++中有效的链表
这个文件说std::list是低效率的：
std :: list是一个非常低效的类，很less有用。 它为插入到其中的每个元素执行堆分配，因此具有非常高的常数因子，特别是对于小数据types。
评论：这是令我惊讶的。 std::list是一个双向链表，所以尽pipe在元素构造方面效率低下，它支持O（1）时间复杂度的插入/删除，但是在这个引用的段落中完全忽略了这个特性。
我的问题：假设我需要一个用于小尺寸齐次元素的顺序容器，并且这个容器应该支持O（1）复杂的元素插入/删除，并且不需要随机访问（虽然支持随机访问是好事，但这不是必须的这里）。 至less在元素个数很less的时候，我也不希望堆分配给每个元素的构造带来高的恒定因子。 最后，只有当相应的元素被删除时， 迭代器才会失效。 显然，我需要一个自定义容器类，它可能（或可能不）是双向链表的变体。 我应该如何devise这个容器？
如果上述规范不能实现，那么也许我应该有一个自定义的内存分配器，比如说，指针分配器？ 我知道std::list将分配器作为其第二个模板参数。
编辑：我知道我不应该太关心这个问题，从工程的angular度来看 – 足够快就足够了。 这只是一个假设的问题，所以我没有更详细的用例。 随意放松一些要求！
Edit2：我知道O （1）复杂性的两种algorithm由于其常数因素的不同而可能具有完全不同的性能。
除了被删除的节点上的迭代器之外，不要使迭代器无效的要求是禁止每个没有分配单独节点的容器，并且与例如list或map有很大不同。
但是，我发现在几乎所有的情况下，当我认为这是必要的时候，事实certificate，我可以做一点点的训练。 你可能想validation一下，你会大大受益。
虽然std::list确实是“正确”的东西，如果你需要类似于列表的东西（大部分是CS类），那么几乎总是错误的select是不幸的，完全正确的。 虽然O（1）声明是完全正确的，但与计算机硬件的实际工作方式相比，却是一个巨大的不确定因素。 请注意，不仅是您随机放置的对象，而且您维护的节点也是（是的，您可以用分配器解决这个问题，但这不是重点）。 平均而言，对于任何事情，您都有两个保证caching未命中的时间，另外还有两个dynamic分配用于变异操作（一个用于对象，另一个用于节点）。
编辑：正如下面的@ratchetfreak所指出的， std::list通常将对象和节点分配合并到一个内存块中，作为一个优化（类似于make_shared那样），这使得平均情况稍微不是灾难性的每个突变和一个保证caching未命中而不是两个）。
在这种情况下，一个新的，不同的考虑可能是这样做也可能不是完全没有问题的。 使用两个指针后缀对象意味着反转方向，而取消引用可能会干扰自动预取。
另一方面，使用指针前缀对象意味着您将对象推回两个指针的大小，这意味着在64位系统上可能多达16个字节（这可能会将中等大小的对象拆分为高速caching行边界每次）。 另外，还有一个考虑是std::list不能单独打破例如SSE代码，因为它增加了一个秘密偏移量作为特别的惊喜（所以例如异或技术可能不适用于减less双指针占用量）。 可能需要一定量的“安全”填充以确保添加到列表中的对象仍然按照他们应该的方式工作。
我无法分辨这些是真正的性能问题，还是仅仅是对我的怀疑和恐惧，但我相信可以公平地说，藏在草地里的蛇比预期的要多。
除非你有一个非常好的理由，否则高调的C ++专家（Stroustrup，特别是）推荐使用std::vector并不是没有道理的。
像以前的许多人一样，我试图聪明地使用（或发明）比std::vector更好的东西来处理一个或另一个特殊的，专门的问题，看起来你可以做得更好，但事实certificate，只需使用std::vector仍然几乎总是最好的，或第二个最好的select（如果std::vector碰巧不是最好的， std::deque通常是你需要的）。
与其他方法相比，您的分配方式更less，内存碎片减less，间接方式更less，内存访问模式更有利。 猜猜看，它是现成的，只是工作。
事实上，每隔一段时间插入需要一个所有元素的副本（通常）是一个完全没有问题的事实。 你以为是，但事实并非如此。 它很less发生，它是一个线性内存块的副本，这正是处理器擅长的（相对于许多双重间接和随机跳转内存）。
如果不要求使迭代器无效，那么你可以将一个std::vector对象与一个dynamic的bitset配对，或者为了缺less更好的东西，可以使用std::vector<bool> 。 然后适当地使用reserve()所以重新分配不会发生。 当删除一个元素时，不要删除它，而只在位图中标记为删除（手动调用析构函数）。 在适当的时候，当你知道可以使迭代器无效时，调用一个“真空吸尘器”function来压缩位向量和对象向量。 在那里，所有无法预见的迭代器失效消失了。
是的，这需要保持一个额外的“元素被删除”位，这是烦人的。 但是std::list必须保持两个指针，加上实际的对象，它必须做分配。 使用向量（或两个向量），访问仍然非常高效，因为它以caching友好的方式进行。 迭代，即使在检查已删除的节点时，仍然意味着您在内存上线性移动或几乎线性移动。
你的要求正是那些std::list ，除了你已经决定你不喜欢基于节点的分配的开销。
理性的做法是从顶端开始，只做你真正需要的东西：
-
只要使用
std::list。基准testing：默认的分配器是否真的太慢了你的目的？
-
不，你完成了。
-
是：转到2
-
-
将
std::list与现有的自定义分配程序（如Boost池分配程序）一起使用基准testing：Boost池分配器是否真的太慢了你的目的？
-
不，你完成了。
-
是的：转到3
-
-
根据您在步骤1和2中执行的所有分析，使用
std::list与自定义分配器进行精细调整，以满足您的独特需求基准像以前等等
-
考虑做一些更奇特的事情作为最后的手段。
如果你到了这个阶段，你应该有一个非常明确的SO问题，有很多关于你需要什么的详细信息（例如，“我需要把n个节点挤进一个caching行”而不是“这个文档说这个东西是慢，这听起来不好“）。
PS。 以上做了两个假设，但都值得调查：
- 正如Baum mit Augen所指出的，做简单的端到端时间是不够的，因为你需要确定你的时间在哪里。 它可能是分配器本身，或由于内存布局导致的caching未命中，或其他。 如果事情很慢，你仍然需要确定为什么在你知道什么应该改变之前。
-
你的要求是作为一个给定的，但find削弱需求的方法往往是使事情更快的最简单的方法。
- 你是否真的需要随时随地插入和删除，或者只是在前面，后面，或两者，而不是在中间？
- 你真的需要那些迭代器失效约束，还是可以放松？
- 有没有可以利用的访问模式？ 如果你经常从前面删除一个元素，然后用新的元素replace，你可以在原地更新它吗？
作为替代，您可以使用可增长的数组并显式处理链接，作为数组中的索引。
未使用的数组元素使用其中一个链接放入链接列表中。 当一个元素被删除时，它被返回到空闲列表。 空闲列表耗尽时，增长数组并使用下一个元素。
对于新的免费元素，你有两个select：
- 将它们一次追加到空闲列表中，
- 基于空闲列表中元素的数量与数组大小，按需追加它们。
std::list是一个双向链表，所以尽pipe在元素构造方面效率低下，它支持O（1）时间复杂度的插入/删除 ，但是在这个引用的段落中完全忽略了这个特性。
它被忽略， 因为这是一个谎言 。
algorithm复杂性的问题是它通常测量一件事情 。 例如，当我们说std::map中的插入是O（log N）时，我们的意思是它执行O（log N） 比较 。 迭代的成本， 从内存中获取caching行等等都没有考虑在内。
当然，这大大简化了分析过程，但不幸的是，这并不一定完全映射到实际的实现复杂性。 特别是，一个令人震惊的假设是内存分配是恒定的 。 那是一个大胆的谎言。
通用内存分配器（malloc和co）对内存分配的最坏情况的复杂性没有任何保证。 最糟糕的情况通常是依赖于操作系统的，在Linux的情况下，可能会涉及OOM杀手（筛选正在进行的进程并杀死一个进程来回收内存）。
特殊用途的内存分配器可能会在特定的分配范围（或最大分配大小）内保持一定的时间。 由于Big-O符号约为无限极限，因此不能称为O（1）。
因此， 在橡胶符合道路的地方 ， std::list的实现通常不具有O（1）插入/删除特性，因为实现依赖于真实的内存分配器，而不是理想的内存分配器。
这是相当令人沮丧，但是你不必失去所有的希望。
最值得注意的是，如果你可以找出元素数量的上限，并且可以预先分配那么多的内存，那么你可以创build一个内存分配器，它将执行恒定的内存分配，给你一个错觉O（ 1）。
使用两个std::list s：一个“free-list”在启动时预先分配了大量的节点，而另一个“活动”列表则从free-list中splice节点。 这是恒定的时间，不需要分配节点。
新的slot_map提议声明O（1）用于插入和删除。
还有一个链接到一个video与build议的实施和一些以前的工作。
如果我们更了解元素的实际结构，可能会有一些专门的关联容器好得多。
我会build议做什么@ Yves Daoust说，除了使用自由列表链接列表，使用一个向量。 推入并popupvector背面的自由索引。 这是分期O（1）插入，查找和删除，并不涉及任何指针追逐。 它也不需要任何恼人的分配器业务。
我第二@不用“的答复，特别是关于修改要求的PS第2项。 如果你放松了迭代器失效约束，那么使用std::vector<>就是Stroustrup对小数目容器的标准build议 （原因已经在注释中提到）。 有关 SO的相关 问题 。
从C ++ 11开始，还有std::forward_list 。
另外，如果添加到容器的元素的标准堆分配不够好，那么我会说你需要非常仔细地看待你的确切需求，并为它们进行微调。
我只是想对你的select做一个小小的评论。 我是vector的一个巨大的粉丝，因为它的读取速度，你可以直接访问任何元素，并根据需要进行sorting。 （例如类/结构的向量）。
但是无论如何我会离题，我想透露两个漂亮的提示。 使用向量插入可能是昂贵的，所以一个整洁的伎俩，不要插入，如果你可以逃脱不这样做。 做一个正常的push_back（放在最后），然后交换一个你想要的元素。
与删除相同。 它们是昂贵的。 所以把它与最后一个元素交换，删除它。
感谢所有的答案。 这是一个简单但不严格的基准。
// 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()); } } } }
这个testing旨在testing哪些std::list声明在-O （1）插入和擦除方面performance突出。 而且，由于我要求插入/删除的位置，这个种族严重偏向于std::vector ，因为它必须移动所有以下元素（因此O （n）），而std::list不需要要做到这一点。
现在我编译它们。
clang++ list.cc -o list clang++ vector.cc -o vector
并testing运行时间。 结果是：
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有更高的常量因子，尽pipe是O （1）。
难怪这个文件说
std::vector是深受喜爱和尊重。
编辑 ： std::deque在某些情况下甚至更好， 至less对于这个任务 。
// 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
