首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >列表和forward_list性能的差异?

问列表和forward_list性能的差异?
EN

Stack Overflow用户
提问于 2018-08-25 09:39:24
回答 2查看 4K关注 0票数 8

与c++11一样,我们有两种类型的列表:

代码语言:javascript
复制
std::list<int> lst = { 1, 2, 3, 4, 5 };

std::forward_list<int> flst = { 5, 4, 3, 2, 1};

如我们所知,列表基于双链接列表,forward_list基于单链接列表。

我们该如何决定使用哪一种呢?以上列表是否有任何性能好处?

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2018-08-25 10:10:18

我们该如何决定使用哪一种呢?

决定是否需要双向迭代。如果前向迭代足够好,那么使用std::forward_list,除非您需要支持比C++11更早的C++版本,后者可能只有std::list。

以上列表是否有任何性能好处?

std::forward_list消除了每个节点的指针(与数据缓存和内存子系统相关的所有好处),而std::list则提供恒定时间的迭代器减量。

但在实践中,这两个容器都没有人们在上计算机科学学校时所相信的那样广泛使用。std::vector的实际性能在许多应用程序中都是优越的,而且它的内存使用量总是较少。要求更高的应用程序需要列表,最好考虑入侵列表,而标准C++不提供这些列表。

票数 14
EN

Stack Overflow用户

发布于 2021-11-21 16:44:18

除了john-zwinck所说的,如果您必须使用链接列表,在作出决定时请记住以下几点:

由于std::forward_list的性质,它没有在末尾运行的修饰符函数:

push_back,pop_back,emplace_back

此外,std::forward_list不提供一个size成员函数来提高效率,根据std::list。size函数给出了std::list在恒定时间内由C++11提供的元素数,另一方面,它需要为内部计数器增加一些存储空间,这使得插入和删除效率略低。为了达到std::forward_list的大小,距离算法可以与begin()和end()函数结合使用,但这种运算需要线性时间。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/52015936

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档