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

Question

除非我遗漏了什么，否则SGIslist和 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

So put simply, sgi::slist and forward_list are very similar.

The differences being that forward_list lacks a size() member function which is included in sgi::slist and forward_list includes an emplace_after member function which isn't included in sgi::slist. Also, forward_list doesn't provide insert and erase member functions like sgi::slist does.

If you know of any other differences, please don't hesitate to mention them.

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。