...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
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.
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*>
.
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.
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; }