Intrusive singly linked list: slist

Intrusive singly linked list: slist 介入式單鏈表：slist

slist hooks slist 鉤子
slist container slist 容器
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.
slist 是最簡單的 Boost.Intrusive 介入式容器：單鏈表。它所帶來的內存開銷是每節點一個指針。一個空的、不帶常量時間 size 的 slist 的大小為一個指針。不過，這種輕量級的內存代價帶來了一些缺點：很多操作具有線性時間複雜度，但也有一些是常量時間的，如 swap。slist 只提供前向迭代器。

For most cases, a doubly linked list is preferrable 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 slist 鉤子

Like the rest of Boost.Intrusive containers, slist has two hook types:
和其它 Boost.Intrusive 容器一樣，slist 有兩種鉤子：

template <class ...Options>
class slist_base_hook;

slist_base_hook: the user class derives publicly from slist_base_hook to make it slist-compatible.
slist_base_hook: 用戶類公有派生自 slist_base_hook 以兼容於 slist。

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_member_hook: 用戶類包含一個公有的 slist_member_hook 以兼容於 slist。

slist_base_hook and slist_member_hook receive the same options explained in the section How to use Boost.Intrusive:slist_base_hook 和 slist_member_hook 接受相同的選項，在如何使用 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>.
tag<class Tag> (只用於基類鉤子)：該參數作為一個標記，你可以派生自多個 slist 鉤子。缺省值：tag<default_tag>.
link_mode<link_mode_type LinkMode>: The linking policy. Default: link_mode<safe_link>.
link_mode<link_mode_type LinkMode>: 鏈接策略。缺省值：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*>.
void_pointer<class VoidPointer>: 在鉤子內部使用並被傳遞給容器的指針類型。缺省值：void_pointer<void*>.

slist container slist 容器

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

slist receives the options explained in the section How to use Boost.Intrusive:
slist 接受以下選項，具體解釋在如何使用 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.)
base_hook<class Hook> / member_hook<class T, class Hook, Hook T::* PtrToMember> / value_traits<class ValueTraits>: 指定用於配置容器的鉤子類型或 value traits。(要學習有關 value traits 的知識，請見帶定制化 ValueTraits 的容器)
constant_time_size<bool Enabled>: To activate the constant-time size() operation. Default: constant_time_size<true>
constant_time_size<bool Enabled>: 激活常量時間的 size() 操作。缺省值：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>.
size_type<bool Enabled>: 指定用於保存容器大小的類型。缺省值：size_type<std::size_t>.

slist can receive additional options:
slist 還可以接受其它選項：

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.
linear<bool Enable>: 將單鏈表實現為以 null 結尾的鏈表，而不是循環鏈表。這樣可以進行 O(1) 的 swap，但就失去了一些如 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.
cache_last<bool Enable>: 單鏈表保存一個指針指向鏈表的最後一個元素。這樣可以進行 O(1) swap, splice_after(iterator, slist &)，並可提供象 push_back(reference) 和 back() 這些新函數。邏輯上，空鏈表的大小要增加 sizeof(void_pointer)，且必須在每次操作中更新緩存的最後節點指針，這可能會導致輕微的性能影響。

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.
如果使用了 linear<true> 和/或 cache_last<true> 選項，則不能使用 auto_unlink 鉤子。如果使用了 auto_unlink 鉤子並指定以上選項，將引發一個靜態斷言。

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
//定義一個使用公有基類鉤子保存 MyClass 的 slist
typedef slist<MyClass> BaseList;

//Define an slist that will store MyClass using the public member hook
//定義一個使用公有成員鉤子保存 MyClass 的 slist
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 創建幾個 MyClass 對象，每個的值不同
   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;
}