Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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 and instead chose a new name, forward_list, when they added the container into the Standard Library for C++0x.

like image 629
Ricky65 Avatar asked Jul 30 '11 19:07

Ricky65


People also ask

What is Forward_list?

std::forward_list is a container that supports fast insertion and removal of elements from anywhere in the container. Fast random access is not supported. It is implemented as a singly-linked list.

How do I find the size of my forward list?

To get the size of forward lists, one can use std::distance() function. Approach: Since std::distance() function takes two iterators as arguments and it returns an integer, the std::begin() and std::end() function can be passed which points to the address of the first item and the address just after the last item.


1 Answers

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.

like image 58
Howard Hinnant Avatar answered Sep 19 '22 23:09

Howard Hinnant