Presenting Boost.Intrusive containers

Presenting Boost.Intrusive containers 介紹 Boost.Intrusive 容器

Boost.Intrusive offers a wide range of intrusive containers:
Boost.Intrusive 提供了大量的介入式容器：

slist: An intrusive singly linked list. The size overhead is very small for user classes (usually the size of one pointer) but many operations have linear time complexity, so the user must be careful if he wants to avoid performance problems.
slist: 介入式的單鏈表。對於用戶類的空間開銷非常小(通常只有一個指針的大小)，但多數操作具有線性的時間複雜度，因此，如果用戶想避免性能問題，就要小心使用。
list: A std::list like intrusive linked list. The size overhead is quite small for user classes (usually the size of two pointers). Many operations have constant time complexity.
list: 一個類似於 std::list 的介入式鏈表。對於用戶類的空間開銷非常小(通常只有兩個指針的大小)。多數操作具有線性的時間複雜度。
set/multiset/rbtree: std::set/std::multiset like intrusive associative containers based on red-black trees. The size overhead is moderate for user classes (usually the size of three pointers). Many operations have logarithmic time complexity.
set/multiset/rbtree: 類似於 std::set/std::multiset 的介入式關聯容器，基於紅黑樹。對於用戶類的空間開銷適中(通常為三個指針的大小)。多數操作具有對數時間複雜度。
avl_set/avl_multiset/avltree: A std::set/std::multiset like intrusive associative containers based on AVL trees. The size overhead is moderate for user classes (usually the size of three pointers). Many operations have logarithmic time complexity.
avl_set/avl_multiset/avltree: 類似於 std::set/std::multiset 的介入式關聯容器，基於 AVL 樹。對於用戶類的空間開銷適中(通常為三個指針的大小)。多數操作具有對數時間複雜度。
splay_set/splay_multiset/splaytree: std::set/std::multiset like intrusive associative containers based on splay trees. Splay trees have no constant operations, but they have some interesting caching properties. The size overhead is moderate for user classes (usually the size of three pointers). Many operations have logarithmic time complexity.
splay_set/splay_multiset/splaytree: 類似於 std::set/std::multiset 的介入式關聯容器，基於 splay 樹。splay 樹不具有常量性的操作，不過它有一些有趣的緩存特性。對於用戶類的空間開銷適中(通常為三個指針的大小)。多數操作具有對數時間複雜度。
sg_set/sg_multiset/sgtree: A std::set/std::multiset like intrusive associative containers based on scapegoat trees. Scapegoat can be configured with the desired balance factor to achieve the desired rebalancing frequency/search time compromise. The size overhead is moderate for user classes (usually the size of three pointers). Many operations have logarithmic time complexity.
sg_set/sg_multiset/sgtree: 類似於 std::set/std::multiset 的介入式關聯容器，基於 scapegoat 樹。scapegoat 樹可以按所期望的平衡因子來配置，以達到所希望的重新平衡頻度和查找時間之間的折衷。對於用戶類的空間開銷適中(通常為三個指針的大小)。多數操作具有對數時間複雜度。

Boost.Intrusive also offers semi-intrusive containers:
Boost.Intrusive 還提供了半介入式容器：

unordered_set/unordered_multiset: std::tr1::unordered_set/std::tr1::unordered_multiset like intrusive unordered associative containers. The size overhead is moderate for user classes (an average of two pointers per element). Many operations have amortized constant time complexity.
unordered_set/unordered_multiset: 類似於 std::tr1::unordered_set/std::tr1::unordered_multiset 的介入式無序關聯容器。對於用戶類的空間開銷適中(平均為每個元素兩個指針)。多數操作具有分期常量時間複雜度。

Most of these intrusive containers can be configured with constant or linear time size:
這些介入式容器中的多數可以被配置為帶有常量時間複雜度或線性時間複雜度的 size 函數：

Linear time size: The intrusive container doesn't hold a size member that is updated with every insertion/erasure. This implies that the size() function doesn't have constant time complexity. On the other hand, the container is smaller, and some operations, like splice() taking a range of iterators in linked lists, have constant time complexity instead of linear complexity.
線性時間的 size: 此類介入式容器不存在一個在每次插入/刪除時更新的 size 成員。這意味著 size() 函數不具有常量時間複雜度。另一方面，容器可以更小，而且某些操作，如接受一個在鏈表中的迭代器區間的 splice()，則具有常量時間複雜度而不是線性複雜度。
Constant time size: The intrusive container holds a size member that is updated with every insertion/erasure. This implies that the size() function has constant time complexity. On the other hand, increases the size of the container, and some operations, like splice() taking a range of iterators, have linear time complexity in linked lists.
常量時間的 size: 此類介入式容器保存了一個在每次插入/刪除時更新的 size 成員。這意味著 size() 函數具有常量時間複雜度。另一方面，這增加了容器的大小，而且某些操作，如接受一個在鏈表中的迭代器區間的 splice()，則具有線性複雜度。

To make user classes compatible with these intrusive containers Boost.Intrusive offers two types of hooks for each container type:
為了讓用戶類兼容於這些介入式容器，Boost.Intrusive 為每種容器類型提供了兩類鉤子：

Base hook: The hook is stored as a public base class of the user class.
基類鉤子：鉤子被保存為用戶的一個公有基類。
Member hook: The hook is stored as a public member of the user class.
成員鉤子：鉤子被保存為用戶的一個公有成員。

Apart from that, Boost.Intrusive offers additional features:
除此以外，Boost.Intrusive 還提供了以下特性：

Safe mode hooks: Hook constructor initializes the internal data to a well-known safe state and intrusive containers check that state before inserting a value in the container. When erasing an element from the container, the container puts the hook in the safe state again. This allows a safer use mode and it can be used to detect programming errors. It implies a slight performance overhead in some operations and can convert some constant time operations to linear time operations.
安全模式鉤子：鉤子的構造函數將內部數據初始化為一種可知的安全狀態，介入式容器在插入一個值之前檢查該狀態。從容器中刪除一個元素時，容器再次將鉤子置回安全狀態。這樣就允許了一種安全的使用模式，它可以被用於檢測程序的錯誤。它意味著某些操作會有輕微的性能開銷，也可能將一些常量時間的操作變為線性時間。
Auto-unlink hooks: The hook destructor removes the object from the container automatically and the user can safely unlink the object from the container without referring to the container.
自斷鉤子：鉤子的析構函數自動將對像從容器中移除，用戶無需知道容器就可以安全地將對像從容器斷開。
Non-raw pointers: If the user wants to use smart pointers instead of raw pointers, Boost.Intrusive hooks can be configured to use any type of pointer. This configuration information is also transmitted to the containers, so all the internal pointers used by intrusive containers configured with these hooks will be smart pointers. As an example, Boost.Interprocess defines an mart pointer compatible with shared memory, called offset_ptr. Boost.Intrusive can be configured to use this smart pointer to allow shared memory intrusive containers.
非裸指針：如果用戶想用智能指針代替裸指針，Boost.Intrusive 鉤子可以被配置為使用任意類型的指針。這一配置信息也被轉送到容器，所以以這些鉤子進行配置的介入式容器所使用的所有內部指針都會是智能指針。例如，Boost.Interprocess 定義了一個兼容於共享內存的智能指針，名為 offset_ptr。 Boost.Intrusive 可以被配置為使用此智能指針，就可以使用共享內存介入式容器。