| Home | Libraries | People | FAQ | More

## Intrusive singly linked list: slist

`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<bool Enabled>`: 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>`: the singly linked 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 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()), 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;
    }