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 that 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 its 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 preferrable because it offers more constant-time functions with a slightly bigger overhead. However, for some applications like constructing more elaborated 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 same 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 know about value traits go to the section titled Containers with custom ValueTraits.
constant_time_size<bool Enabled>: To activate the constant-time size() operation. Default: constant_time_size<true>
size_type<bool Enabled>: To specify the type that will be used to store the size of the container. Default: size_type<std::size_t>

Example

Now let's see an 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()), bitend(baselist.end());
      MemberList::iterator mit(memberlist.begin()), mitend(memberlist.end());
      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;
}

Boost C++ Libraries