c++ - std::forward_list 和 std::forward_list::push_back

Question

我想使用 std::forward_list

因为:

Forward list is a container which supports fast insertion and removal of elements from anywhere from the container

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

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

Answer 1

我建议反对 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::list 需要更长的时间，因为所有对象在内存中相距多远。 std::list 对缓存不友好，这可能是现代处理器最重要的事情。

The complete talk by Bjarne Stroustrup

Thorough explanation of the effects, with benchmarks at multiple sizes

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

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

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