这个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) 时间复杂度的插入/删除，但在这段引用的段落中完全忽略了该功能。
我的问题:假设我需要一个顺序容器来容纳小型同质元素，并且该容器应该支持元素在 O(1) 中插入/删除复杂性并且不需要需要随机访问(虽然支持随机访问很好，但这里不是必须的)。我也不希望为每个元素的构造堆分配引入高常数因子，至少当元素数量很小时。最后，只有当相应元素被删除时，迭代器才应该失效。显然我需要一个自定义容器类，它可能(也可能不是)双向链表的变体。我应该如何设计这个容器？</p>
如果无法实现上述规范，那么也许我应该有一个自定义内存分配器，例如凹凸指针分配器？我知道 std::list 将分配器作为其第二个模板参数。
编辑:我知道从工程的角度来看我不应该太关心这个问题 - 足够快就足够好了。这只是一个假设问题，所以我没有更详细的用例。随意放宽一些要求!
Edit2:我理解两种 O(1) 复杂度的算法由于常数因子的不同可能具有完全不同的性能。
最佳答案
您的要求完全是std::list的要求，只是您决定不喜欢基于节点的分配的开销。
明智的方法是从顶部开始，只做你真正需要的事情:
只需使用
std::list。对其进行基准测试:默认分配器对于您的目的来说真的太慢了吗？
不:你已经完成了。
是:转到 2
将
std::list与现有的自定义分配器(例如 Boost 池分配器)结合使用对其进行基准测试:Boost 池分配器对于您的目的来说真的太慢了吗？
不:你已经完成了。
是:转到 3
将
std::list与手动自定义分配器结合使用，该分配器根据您在步骤 1 和 2 中进行的所有分析，根据您的独特需求进行微调像以前一样进行基准测试等
考虑做一些更具异国情调的事情作为最后的手段。
如果你到了这个阶段，你应该有一个真正明确的问题，其中有很多关于你到底需要什么的细节(例如“我需要挤压n 节点进入缓存行”而不是“这个文档说这个东西很慢而且听起来很糟糕”)。
- 正如 Baum mit Augen 指出的那样，仅仅进行简单的端到端计时是不够的，因为您需要确定您的时间都花在了哪里。它可能是分配器本身，或者由于内存布局导致的缓存未命中，或者其他原因。如果某些事情很慢，您仍然需要先确定原因，然后才能知道应该改变什么。
您的要求被视为给定的，但找到削弱要求的方法通常是加快速度的最简单方法。
- 你真的需要在任何地方进行恒定时间的插入和删除，还是只在前面，或后面，或两者都需要，但不需要在中间？
- 你真的需要这些迭代器失效约束吗？或者可以放宽它们吗？
- 有可以利用的访问模式吗？如果您经常从前面删除一个元素，然后用新元素替换它，您可以就地更新它吗？
关于c++ - C++中的高效链表？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45717938/