What is the difference between SGI slist and C++11 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.

I assume there is a difference though as the C++ Standard Commitee didn't adopt the name slist a开发者_Python百科nd instead chose a new name, forward_list, when they added the container into the Standard Library for C++0x.

---

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.

Update:

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);

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.

---

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.

---

I've recently run into another difference. The method splice_after has a different interface and different behaviour.

1) forward_list Requires you to pass the container you're moving from as a second argument:

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

slist:

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

This is similar for the overloads.

2) Specific for the overload mentioned above: the last iterator is interpreted differently! Where slist moves the range [ before_first + 1, before_last + 1 >, forward_list moves the range < first, last >. So, when converting code (since slist is deprecated in GCC, for instance), make sure to use: last = before_last + 1.