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

Question

SGI slist和C++11 std::forward_list在我看来都是一样的，除非我遗漏了什么；它们都实现了一个单链表。

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

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

Answer 2

所以简单地说，sgi::slist和forward_list非常相似。

不同之处在于forward_list缺少sgi::slist中包含的size()成员函数，而forward_list包含sgi::slist中没有的emplace_after成员函数。此外，forward_list不像sgi::slist那样提供插入和擦除成员函数。

如果您知道任何其他不同之处，请不要犹豫地提出来。

Answer 3

我最近遇到了另一个不同之处。方法splice_after具有不同的接口和不同的行为。

1) forward_list要求您将从中移动的容器作为第二个参数进行传递：

void splice_after( const_iterator pos, forward_list& other,
                   const_iterator first, const_iterator last );

列表：

void splice_after(iterator pos, iterator before_first, iterator before_last)

这与重载类似。

2)特定于上面提到的重载:最后一个迭代器有不同的解释！其中slist移动范围[ before_first + 1，before_last +1 >，forward_list移动范围< first，last >。因此，在转换代码时(例如，因为在GCC中不推荐使用slist )，请确保使用: last = before_last + 1。