What is the difference between SGI slist and C ++ 11 forward_list?

Question

Both SGI slistand C ++ 11 std::forward_listseem identical to me if I haven't missed something; both implement a singly linked list.

I assume that there is a difference, because C ++ Standard Commitee did not use the name slider and instead chose the new name forward_list when they added the container to the standard library for C ++ 0x.

Answer 1

One significant difference is that it std::forward_listdoes not have a member function size(), where sgi::slistthere is no quality . The motivation for this is that the O (N) size()problem was problematic. N2543 contains more detailed design information for forward_list.

Update:

Recently, I had a good reason to take a closer look at this topic. slistalso has other member functions that one might think of are O (1), but they really are 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 are not very careful, you may run into significant performance issues using slist. Using std::forward_listinstead ensures that you get the expected O (1) performance from your separate list.

Answer 2

, : sgi:: slist forward_list .

, forward_list - size(), sgi:: slist forward_list, - emplace_after, sgi:: slist. , 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 );

SLIST:

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

.

2) Specifically for the overload mentioned above: the last iterator is interpreted differently! When slist moves the range [before_first + 1, before_last + 1>, forward_list moves the range. Thus, when converting code (for example, slist is deprecated in GCC), be sure to use: last = before_last + 1.