STL slist和C ++ 0x forward_list有什么区别？ [英] What is the difference between STL slist and C++0x forward_list?

问题描述

SGI slist和C ++ 0x forward_list与我一样，除非我错过了一些东西;两者都实现一个单链表。

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

我假设有一个区别，虽然C ++标准委员会没有采用名称slist，而是选择一个新的名称forward_list ，它们将容器添加到C ++ 0x的标准库中。

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 有关<$ c的设计决策的更多详细信息$ c> 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.

这篇关于STL slist和C ++ 0x forward_list有什么区别？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！