18

我想使用std::forward_list

因为：

前向列表是一个容器，它支持从容器的任何位置快速插入和删除元素

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

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

4

5 回答 5

31

我建议反对std::forward_list，就像我std::list在几乎所有情况下都反对一样。就个人而言，我从未在我的代码中发现链表是最好的数据结构的情况。

在 C++ 中，您的默认首选数据集合应该是std::vector. push_back如果那是您真正需要的，它可以为您提供高效。如果您只查看该操作的抽象 big-O 复杂性测量，它在技术上不会为您提供从中间有效的删除和插入。然而，在现实世界中，即使在中间插入和删除std::vector，仍然会获胜。

例如，Bjarne Stroustrup 创建了一个 100,000 个元素std::list与std::vector. 他会搜索每个元素并删除它。然后他会找一个插入点插入到中间。他本可以在 上使用二分搜索std::vector，但没有使比较“更公平”。

结果显示，即使在本应强大std::vector的情况下， 也取得了很大的胜利。由于所有对象在内存中相距多远，因此std::list简单地遍历需要更长的时间。不是缓存友好的，这可能是现代处理器最重要的事情。std::liststd::list

Bjarne Stroustrup 的完整演讲

对效果的透彻解释，具有多种尺寸的基准

请注意，此处的第二个链接提供了一些您可能想要使用 a 的情况std::list，例如当元素的大小很大时。但是，我遇到过许多元素按特定顺序排列并且需要删除一些的情况。

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

我的第一个实现是一种简单的std::vector方法，我在遍历时删除了无效元素。这适用于小型测试数据集，但是当我尝试做真实的事情时，它太慢而无用。我切换到 astd::list作为容器，但使用了相同的算法，并且我看到了显着的性能改进。但是，它仍然太慢而无法使用。成功的改变是切换回 a std::vector，但我没有删除坏的元素，而是创建了一个新的std::vector，并且我发现的任何好的元素都放入了std::vector，然后在函数结束时我会简单地丢弃旧的并使用新的，这给了我与原版一样std::vector多的速度std::liststd::liststd::vector实施，这已经足够快了。

于 2012-07-07T14:51:32.727 回答
22

std::forward_list支持快速插入和移除，但不支持遍历到底。要实现.push_back，您首先需要到达列表的末尾，即 O(N) 并且一点也不快，这可能就是它没有实现的原因。

 

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

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

然后使用.insert_afteror.emplace_after插入元素：

slist.insert_after(before_end, 1234);
于 2012-01-05T12:32:15.413 回答
6

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);
于 2012-07-07T13:17:16.993 回答
5

没有push_back，因为列表不跟踪列表的后面，只有前面。

您可以在列表周围编写一个包装器，该包装器维护一个指向最后一个元素的迭代器，并push_back根据列表insert_after是否push_front为空来实现。如果您想支持更复杂的操作（例如sortand splice_after），这将变得相当复杂。

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

除非内存非常紧张，否则最好的解决方案是使用list. 这具有与 相同的性能特征forward_list，并且是双向的，支持push_back以及push_front; 成本是每个元素的额外指针。

于 2012-01-05T12:35:46.917 回答
3

不幸的是，我无法添加评论（声誉低下），但我只想提一下 forward_list 和 list 的优点之一是插入删除操作不会使迭代器无效。我有一个应用程序，其中元素集合在迭代和处理单个元素时不断增长。没有迭代器失效允许我实现段扫描（列表的开头作为段的开始，最后一个段的开始作为结束）。

于 2016-09-21T21:22:55.803 回答