Intrusive singly linked list: slist

slist hooks
slist container
Example

slist is the simplest intrusive container of Boost.Intrusive: a singly linked list. The memory overhead it imposes is 1 pointer per node. The size of an empty, non constant-time size slist is the size of 1 pointer. This lightweight memory overhead comes with drawbacks, though: many operations have linear time complexity, even some that usually are constant time, like swap. slist only provides forward iterators.

For most cases, a doubly linked list is preferable because it offers more constant-time functions with a slightly bigger size overhead. However, for some applications like constructing more elaborate containers, singly linked lists are essential because of their low size overhead.

slist hooks

Like the rest of Boost.Intrusive containers, slist has two hook types:

template <class ...Options>
class slist_base_hook;

slist_base_hook: the user class derives publicly from slist_base_hook to make it slist-compatible.

template <class ...Options>
class slist_member_hook;

slist_member_hook: the user class contains a public slist_member_hook to make it slist-compatible.

slist_base_hook and slist_member_hook receive the same options explained in the section How to use Boost.Intrusive:

tag<class Tag> (for base hooks only): This argument serves as a tag, so you can derive from more than one slist hook. Default: tag<default_tag>.
link_mode<link_mode_type LinkMode>: The linking policy. Default: link_mode<safe_link>.
void_pointer<class VoidPointer>: The pointer type to be used internally in the hook and propagated to the container. Default: void_pointer<void*>.

slist container

template <class T, class ...Options>
class slist;

slist receives the options explained in the section How to use Boost.Intrusive:

base_hook<class Hook> / member_hook<class T, class Hook, Hook T::* PtrToMember> / value_traits<class ValueTraits>: To specify the hook type or value traits used to configure the container. (To learn about value traits go to the section Containers with custom ValueTraits.)
constant_time_size<bool Enabled>: To activate the constant-time size() operation. Default: constant_time_size<true>
size_type<typename SizeType>: To specify the type that will be used to store the size of the container. Default: size_type<std::size_t>.

slist can receive additional options:

linear<bool Enable>: the singly linked list is implemented as a null-terminated list instead of a circular list. This allows O(1) swap, but losses some operations like container_from_end_iterator.
cache_last<bool Enable>: slist also stores a pointer to the last element of the singly linked list. This allows O(1) swap, splice_after(iterator, slist &) and makes the list offer new functions like push_back(reference) and back(). Logically, the size an empty list is increased in sizeof(void_pointer) and the cached last node pointer must be updated in every operation, and that might incur in a slight performance impact.

auto_unlink hooks are not usable if linear<true> and/or cache_last<true> options are used. If auto_unlink hooks are used and those options are specified, a static assertion will be raised.

Example

Now let's see a small example using both hooks:

#include <boost/intrusive/slist.hpp>
#include <vector>

using namespace boost::intrusive;

                  //This is a base hook
class MyClass : public slist_base_hook<>
{
   int int_;

   public:
   //This is a member hook
   slist_member_hook<> member_hook_;

   MyClass(int i)
      :  int_(i)
   {}
};

//Define an slist that will store MyClass using the public base hook
typedef slist<MyClass> BaseList;

//Define an slist that will store MyClass using the public member hook
typedef member_hook<MyClass, slist_member_hook<>, &MyClass::member_hook_> MemberOption;
typedef slist<MyClass, MemberOption> MemberList;

int main()
{
   typedef std::vector<MyClass>::iterator VectIt;
   typedef std::vector<MyClass>::reverse_iterator VectRit;

   //Create several MyClass objects, each one with a different value
   std::vector<MyClass> values;
   for(int i = 0; i < 100; ++i)  values.push_back(MyClass(i));

   BaseList baselist;
   MemberList memberlist;

   //Now insert them in the reverse order in the base hook list
   for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it)
      baselist.push_front(*it);

   //Now insert them in the same order as in vector in the member hook list
   for(BaseList::iterator it(baselist.begin()), itend(baselist.end())
      ; it != itend; ++it){
      memberlist.push_front(*it);
   }

   //Now test lists
   {
      BaseList::iterator bit(baselist.begin());
      MemberList::iterator mit(memberlist.begin());
      VectRit rit(values.rbegin()), ritend(values.rend());
      VectIt  it(values.begin()), itend(values.end());

      //Test the objects inserted in the base hook list
      for(; rit != ritend; ++rit, ++bit)
         if(&*bit != &*rit)   return 1;

      //Test the objects inserted in the member hook list
      for(; it != itend; ++it, ++mit)
         if(&*mit != &*it)    return 1;
   }

   return 0;
}