SGI slist 和 C++11 forward_list 有什么区别? [英] What is the difference between SGI slist and C++11 forward_list?

查看:15
本文介绍了SGI slist 和 C++11 forward_list 有什么区别?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

SGI slist 和 C++11 std::forward_list 对我来说都是一样的,除非我错过了什么;两者都实现了单链表.

Both SGI slist and C++11 std::forward_list appear identical to me unless I have missed something; both implement a singly-linked list.

我认为这是有区别的,因为 C++ 标准委员会在将容器添加到 C++0x 标准库时并没有采用名称 slist,而是选择了一个新名称 forward_list.

I assume there is a difference though as the C++ Standard Commitee didn't adopt the name slist and instead chose a new name, forward_list, when they added the container into the Standard Library for C++0x.

推荐答案

一个主要区别是 std::forward_list 缺少一个 size() 成员函数,其中sgi::slist 没有.这样做的动机是 O(N) size() 存在问题.N2543 有更多关于设计的细节forward_list 的决定.

One major difference is that std::forward_list lacks a size() member function, where as the sgi::slist doesn't. The motivation for this is that an O(N) size() has been problematic. N2543 has more details on the design decisions for forward_list.

更新:

我最近有一个很好的借口来仔细研究这个主题.slist 还有其他的成员函数,人们可能会认为它们是 O(1),但实际上是 O(N).其中包括:

I recently had a good excuse to look closer at this subject. slist also has other member functions that one would be tempted to think are O(1), but are really O(N). These include:

iterator previous(iterator pos);
const_iterator previous(const_iterator pos) const;
iterator insert(iterator pos, const value_type& x);
iterator erase(iterator pos);
void splice(iterator position, slist& x);
void splice(iterator position, slist& x, iterator i);

简而言之,如果您不非常小心,则使用 slist 可能会导致严重的性能问题.使用 std::forward_list 可确保您从单链表中获得预期的 O(1) 性能.

In short, if you're not very careful, you can end up with significant performance problems by using slist. Use of std::forward_list instead ensures that you'll get the expected O(1) performance out of your singly linked list.

这篇关于SGI slist 和 C++11 forward_list 有什么区别?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆