Intrusive doubly linked list: list

| Home | Libraries | People | FAQ | More

## Intrusive doubly linked list: list

`list` is a doubly linked list. The memory overhead that imposes is 2 pointers per node. An empty, non constant-time size `list` has also the size of 2 pointers. `list` has many more constant-time operations than `slist` and provides bidirectional iterator. It's recommendable to use use `list` instead of `slist` if the size overhead is acceptable:

### list hooks

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

    template <class ...Options>
    class list_base_hook;

- `list_base_hook`: the user class derives publicly from `list_base_hook` to make it `list`-compatible.

    template <class ...Options>
    class list_member_hook;

- `list_member_hook`: the user class contains a public `list_member_hook` to make it `list`-compatible.

`list_base_hook` and `list_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 list 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*>`.

### list container

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

`list` 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/list.hpp>
    #include <vector>

    using namespace boost::intrusive;

    class MyClass : public list_base_hook<>   //This is a derivation hook
    {
       int int_;

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

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

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

    //Define a list that will store MyClass using the public member hook
    typedef list< MyClass
                , member_hook< MyClass, list_member_hook<>, &MyClass::member_hook_>
                > 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(VectIt it(values.begin()), itend(values.end()); it != itend; ++it)
          memberlist.push_back(*it);

       //Now test lists
       {
          BaseList::reverse_iterator rbit(baselist.rbegin()), rbitend(baselist.rend());
          MemberList::iterator mit(memberlist.begin()), mitend(memberlist.end());
          VectIt  it(values.begin()), itend(values.end());

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

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

       return 0;
    }