因为:
转发列表是一个容器,支持从容器的任何位置快速插入和删除元素
但是没有*std :: forward_list :: push_back*实现.
是否有一种高性能的方法来增加对一个或没有理由的支持？
我是C++的新手,并且阅读了"The C++ Programming Language(4th edition)"一书.阅读"STL容器"一章时,本书介绍了forward_list:
forward_list(单链表)基本上是针对空列表和非常短列表优化的列表.空的forward_list只占用一个单词.令人惊讶的是,大多数都是空的列表有很多用途(其余的都很短).
我想知道一份清单有多短暂考虑？谁能举一个简单的例子来利用forward_list？
我一直在使用C++ 11 forward_list作为快速插入的容器,没有太多的内存开销,因为它是一个单链表.
在意识到forward_list没有size()方法之后,我对这背后的推理感到有点困惑.它是否只能维护一个私有字段来跟踪插入和删除的节点,从而实现O(1)size()操作？
将一个范围从一个列表拼接到另一个列表可以在恒定的时间内完成,但代价是使size()线性变得复杂.
C++ 11已经改变了,在std::list需要size()恒定时间的情况下.这打破了,例如,gcc的实现,参见[C++ 0x] std :: list :: size complexity.
除了范围之外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 不会留在源列表中.码:
#include <algorithm>
#include <iostream>
#include <forward_list>
using namespace std;
void dump_list(const forward_list<char>& l) {
for(char c : l)
cout << c << ' ';
cout << '\n';
}
int main() …嗯,我认为这个问题几乎总结了一下.我有一个独特项目的forward_list,并希望从中删除一个项目:
std::forward_list<T> mylist;
// fill with stuff
mylist.remove_if([](T const& value)
{
return value == condition;
});
我的意思是,这种方法工作正常但效率低,因为一旦找到并删除了项目,它就会继续搜索.有更好的方法还是我需要手动完成？
我想拼接范围[first, last],包括两个端点.我之前 first和之前都有元素的迭代器last.我能做到splice_after()但只能在线性时间内完成.
我相信这种拼接可以在恒定的时间内完成.我怎么能这样做std::forward_list？
如果问题不明确,这里显示我的问题的示例代码:
实时工作空间代码
#include <algorithm>
#include <forward_list>
#include <iostream>
#include <iterator>
using namespace std;
int main() {
forward_list<char> trg{'a','b','c'};
forward_list<char> src{'1','2','3','4'};
auto before_first = src.begin();
auto last = find(src.begin(), src.end(), '4');
cout << "before_first = " << *before_first << ", last = " << *last << "\n";
// trg.splice(trg.begin(), src, before_first, last); // no such splice
auto end = last;
++end; // Ouch! …我理解为什么std::forward_list 没有size()成员函数,因为O(1)版本会破坏某些splice()重载的复杂性,并且因为O(N)版本会与标准库的所有其他容器不一致.
这也是事实,双方std::list并std::forward_list已经拥有相同的语义从他们的堂兄弟其他几个成员函数<algorithm>的标准库(的角落merge(),reverse(),remove(),remove_if(),unique(),sort()).
那么为什么不提供复杂性的count() 成员函数具有返回的语义？O(N)std::forward_liststd::distance(std::begin(some_list), std::end(some_list))
与c ++ 11一样,我们有两种类型的列表:
std::list<int> lst = { 1, 2, 3, 4, 5 };
std::forward_list<int> flst = { 5, 4, 3, 2, 1};
我们知道该列表基于双向链表,而forward_list基于单链表.
我们该如何决定使用哪一个？其他列表中是否有任何性能优势？
我知道std::forward_list<T>::iterator没有复合赋值运算符(operator+=).但那是为什么呢？
我问这个有三个原因:
operator++()吗？std::advance()做同样的事情？operator+=().假设在某个时间点,您有一组N数字并知道中间元素:M.现在,您将获得一个新值,X因此您可能需要更新M.(或者更确切地说,您需要,假设您正在处理的数字都是唯一的.此外,所有样本都是连续接收的,因此并发性没有问题.)
计算新均值很简单:采用旧均值,加X,乘N,除N + 1.(通过检查N元素的平均值是如何定义的,这一点很清楚.目前我并不太担心数字.)
我的问题是:任何人都可以提出更新中位数的创意/小说(或者可能是可证明最优的)方法吗？我将在下面提供一个示例(我自己设计的简单概念),并进行一些分析:
在这个例子中,我将使用a std::forward_list,因为C++ 11是我最近遇到过的.在不失一般性的情况下,我将假设你以正确的方式进行此操作:维护到目前为止遇到的元素(类型T)的有序列表,std::forward_list<T> sorted;当 T x;出现时,只需使用以下方法将其折叠到位:
sorted.merge(std::forward_list<T> {{ x }});
顺便说一句,我很好奇是否有人有更好的(更有效/更优雅)的方法.欢迎Gripes.
所以,X现在是一部分sorted,简而言之,这就是我的想法:
auto it = sorted.begin(), itend = sorted.end();
typename std::forward_list<T>::size_type count = std::distance(it, itend);
for (const auto &e : sorted) {
if (it == itend || ++it == itend) {
M = (count % 2) ? e : (e + M) / …