std :: forward_list和std :: forward_list :: push_back

Question

我想使用std :: forward_list

因为:

转发列表是一个容器,支持从容器的任何位置快速插入和删除元素

但是没有*std :: forward_list :: push_back*实现.

是否有一种高性能的方法来增加对一个或没有理由的支持？

Answer 1

我推荐反对std::forward_list,就像我std::list几乎在所有情况下推荐的那样.就个人而言,我从未在代码中发现链接列表是最佳数据结构的情况.

在C++中,您的默认定位数据集应该是std::vector.push_back如果这是你真正需要的,它会为你提供高效率.如果您只查看该操作的抽象大O复杂度测量,从技术上讲,它不能从中间有效地删除和插入.然而,在现实世界中,即使在中间插入和删除也std::vector仍然获胜.

作为一个例子,Bjarne的Stroustrup的创建100000元件的测试std::list对std::vector.他会搜索每个元素并删除它.然后他会找到一个插入点并插入中间.他本可以使用二进制搜索std::vector,但没有让比较"更公平".

结果显示了强大的胜利std::vector,即使在这种std::list应该强大的情况下也是如此.std::list由于所有对象在内存中的距离太远,因此简单地遍历所需的时间更长.std::list不是缓存友好的,这可能是现代处理器最重要的事情.

Bjarne Stroustrup的完整演讲

通过多种尺寸的基准测试对效果进行彻底解释

请注意,此处的第二个链接提供了一些您可能想要使用a的情况std::list,例如元素的大小很大时.但是,我一直处于这样一种情况:我按特定顺序拥有许多元素,需要删除一些元素.

这些元素比任何内置类型都要大,但不是很大,在32位计算机上可能各占20-30个字节.元素的数量足够大,因此我的整个数据结构只有几百MiB.数据收集是一组基于当前已知信息理论上可以有效的值.该算法迭代所有元素,并根据新信息删除不再有效的元素,每次传递可能会删除大约80%的剩余元素.

我的第一个实现是一个简单的std::vector方法,我在遍历时删除了无效元素.这适用于小型测试数据集,但是当我尝试做真实的事情时,它太慢而无法使用.我切换到a std::list作为容器,但使用相同的算法,我看到了显着的性能改进.但是,它仍然太慢而无法使用.获胜的变化是切换回a std::vector,但是我没有删除那些不好的元素,而是创建了一个新的std::vector元素,并且我找到的任何元素都很好std::vector,然后在函数结束时我会简单地摒弃旧的std::vector,并使用新的,这给了我大约相当于一个加速过的std::list作为std::list让我在我原来的std::vector执行,而这只是速度不够快是有益的.

Answer 2

std::forward_list支持快速插入和删除,但不支持遍历结束.要实现.push_back,您首先需要到达列表的末尾,即O(N)并且根本不快,这可能是它未实现的原因.

 

您可以通过递增.before_beginN次找到最后一个元素的迭代器

auto before_end = slist.before_begin();
for (auto& _ : slist)
  ++ before_end;

然后使用.insert_after或.emplace_after插入元素:

slist.insert_after(before_end, 1234);

Answer 3

std :: forward_list的要点是std :: list的超精简版本,因此它不会将迭代器存储到最后一个元素.如果你需要一个,你必须自己维护,如下:

forward_list<int> a;

auto it = a.before_begin();

for(int i = 0; i < 10; ++i)
    it = a.insert_after(it, i);

Answer 4

没有,push_back因为列表不跟踪列表的后面,只跟踪前面.

您可以在列表周围编写一个包装器来维护最后一个元素的迭代器,并push_back使用insert_after或者push_front根据列表是否为空来实现.如果您想支持更复杂的操作(例如sort和splice_after),这将变得相当复杂.

或者,如果您不需要push_back快速,则可以直接在线性时间内完成.

除非内存非常严格,否则最好的解决方案是使用list.此具有相同的性能特性forward_list,并且是双向的,支撑push_back以及push_front; 成本是每个元素的额外指针.