SGI slist和C ++ 11 forward_list有什么区别? [英] What is the difference between SGI slist and 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屋!