问题标签 [forward-list]

我想使用std::forward_list

因为：

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

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

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

其中forward_list有一个函数splice_after（供参考），具体来说，给出的链接中的函数#3。list考虑到单个链接，将如何实施。

作为一个练习，当我实现它时，我必须迭代列表直到我到达之前的节点first（以便我可以连接first到last），然后再次直到我到达之前的节点last（以便我可以将当​​前列表的节点连接到节点之前last）。这对我来说似乎效率不高，并且想知道是否有更好的方法可以在没有迭代的情况下做到这一点？

我将为 C++11 的节点创建一个内存池forward_list。

是否可以使用 BOOST 池内存std::forward_list？

我正在阅读对这个函数应该如何工作的不同解释。

cplusplus.com说这个函数应该“直接在 i 之后移动元素”。
然而cppreference.com说它拼接了元素 AT i。
MSvisual studio 同意 cplusplus.com。然而，实际上正确的行为是什么？我倾向于认为移动“在 i 之后”更合乎逻辑（& 不需要 N 时间来找到前一个节点）。

（PS：没有转发列表标签？）

可以在恒定时间内完成从一个列表到另一个列表的拼接，但代价是使size()' 的复杂性呈线性。

C++11std::list通过要求size()恒定时间改变了这一点。例如，这破坏了 gcc 的实现，请参阅[C++0x] std::list::size complex。

除了 range 之外splice()，还有什么其他原因 size() 不能在早期的符合 C++03 的 std::list 实现中设为恒定时间吗？

为什么拼接整个列表或范围是线性的 std::forward_list？

参见splice_after()案例 (1) 和 (3)。另见标准草案 N3485中的 23.3.4.6 forward_list 操作 [forwardlist.ops] 。std::forward_list甚至没有size()实现。

我知道 forward_list 是一个单链表，但我不明白为什么不能splice_after()在恒定时间内完成该范围。我可能在这里遗漏了一些微不足道的东西......

编辑：好的，至少部分是我的误解，我预计 4不会保留在源列表中。代码：

输出：

我想拼接 range [first, last]，包括两个端点。我对元素before first和 to有迭代器last。我可以做到这一点，splice_after()但只能在线性时间内。

我相信这个拼接可以在恒定时间内完成。我该怎么做std::forward_list？

如果问题不清楚，这里是显示我的问题的示例代码：

实时工作空间代码

输出：

假设在某个时间点，您有一组N数字并且知道中间元素：M。现在，您获得了一个新值 ，X因此您可能需要更新M。（或者更确切地说，假设您处理的数字都是唯一的，您将需要这样做。此外，所有样本都是连续接收的，因此并发性没有问题。）

计算新均值很简单：取旧均值、加X、乘N、除N + 1。（通过检查 N 个元素的平均值是如何定义的，这一点很清楚。目前我不太担心数字。）

我的问题是：任何人都可以建议一种创造性的/新颖的（或者可能是可证明的最佳）方法来解决更新中位数的问题吗？我将在下面提供一个示例（我自己设计的简单想法），并进行一些分析：

在这个示例中，我将使用std::forward_list，因为 C++11 是我最近遇到的地方。在不失一般性的情况下，我将假设您以正确的方式进行此操作：维护迄今为止遇到的元素（类型 T）的有序列表，std::forward_list<T> sorted;当 T x;出现时，只需使用以下命令将其折叠到位：

顺便说一句，我很好奇是否有人对此有更好（更有效/优雅）的方法。欢迎抱怨。

所以，X现在是 的一部分sorted，简而言之，这是我的想法：

这里发生的一件好事（如果不是很难看的话）是：因为您将迭代器向前移动两次（并且安全地，我可能会添加，尽管以两次比较为代价），当end()达到时，我们'将处于适当的（中值）值。如果有奇数个元素，M只是那个样本，如果没有，它只是这个元素的平均值和旧的（推出的）中位数。因为奇数和偶数交替出现，所以旧的或新的M实际上都会在集合中。这个推理是合理的，是吗？

如果您认为它是垃圾/您的方法要好得多，则无需评论我的 O(3n) 方法；我只是建议它作为一个起点。

我需要实现一个请求列表，一次发送一个（节流）并等待答案（始终按顺序）。因此操作是：

• 插入（最后）
• 删除（开始时）
• 向前一步（“发送”指针）

我刚刚发现std::forward_list，并正在考虑使用它。但是为了让它工作，我需要跟踪一个用于发送指针的迭代器和一个用于插入的迭代器，当我插入和删除对象时它们不会中断。

直觉上我会说链表迭代器对于插入和删除来说是稳定的，但有人可以证实这一点。另外，如果我清空列表，我是否需要做一个特殊情况，插入迭代器应该重置到before_begin哪里？

我正在将我的代码移植到 xlC。
想知道 xlC 是否支持 forward_list？
我试过测试程序

它在 g++ 上编译良好，但在 xlC 上给出错误。
尝试以下编译行：
xlC forward_list_test.cpp
xlC -D __IBMCPP_TR1__ forward_list_test.cpp
但错误相同：
“forward_list_test.cpp”，第 1.10 行：1540-0836 (S) 找不到#include 文件。

如果它支持我们是否需要添加一些额外的东西来编译它？
注意：使用 xlC 11