SGI slist和C++ 11 forward_list有什么区别？

Question

除非我遗漏了某些内容,否则SGI slist和C++ 11 std::forward_list看起来都与我完全相同; 两者都实现了单链表.

我假设有一点不同,因为C++标准委员会没有采用名称slist而是选择了一个新名称forward_list,当他们将容器添加到C++ 0x的标准库中时.

Answer 1

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

更新:

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

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)性能.