![]() |
Home | Libraries | People | FAQ | More |
As explained in the Concepts section,
Boost.Intrusive containers need a ValueTraits class to perform transformations
between nodes and user values. ValueTraits
can be explicitly configured (using the value_traits<> option) or implicitly configured (using
hooks and their base_hook<>/member_hook<>
options). ValueTraits contains
all the information to glue the value_type
of the containers and the node to be used in node algorithms, since these types
can be different. Apart from this, ValueTraits
also stores information about the link policy of the values to be inserted.
正如在 概念 一節所說的,Boost.Intrusive 容器需要一個 ValueTraits 類來執行節點與用戶值之間的轉換。ValueTraits
可以顯式配置(使用 value_traits<> 選項)或隱式配置(使用鉤子和它們的 base_hook<>/member_hook<>
選項)。ValueTraits 包含了用於將容器的 value_type
與節點算法中所使用的節點粘合起來的所有信息,因為這兩種類型是不同的。除此之外,ValueTraits
還保存了有關被插入的值的鏈接策略的信息。
Instead of using Boost.Intrusive predefined
hooks a user might want to develop customized containers, for example, using
nodes that are optimized for a specific application or that are compatible
with a a legacy ABI. A user might want to have only two additional pointers
in his class and insert the class in a doubly linked list sometimes and in
a singly linked list in other situations. You can't achieve this using Boost.Intrusive predefined hooks. Now, instead of using
base_hook<...>
or member_hook<...>
options the user will specify the value_traits<...> options. Let's see how we can do
this:
用戶可能不想使用 Boost.Intrusive 預定義的鉤子,而想開發定制化的容器,例如,使用一些為特定應用優化的節點,或者是兼容於遺留ABI的節點。用戶可能只是想為他的類增加兩個指針,並且有時將這個類插入到一個雙鏈表中,有時又插入到一個單鏈表中。你不能用 Boost.Intrusive 預定義的鉤子來完成這一任務。現在,不要使用
base_hook<...> 或 member_hook<...>
選項,用戶要給出 value_traits<...> 選項。我們來看看該怎樣做:
ValueTraits has the following
interface:ValueTraits 具有以下接口:
#include <boost/pointer_to_other.hpp> #include <boost/intrusive/link_mode.hpp> struct my_value_traits { typedef implementation_defined node_traits; typedef implementation_defined value_type; typedef node_traits::node_ptr node_ptr; typedef node_traits::const_node_ptr const_node_ptr; typedef boost::pointer_to_other<node_ptr, value_type>::type pointer; typedef boost::pointer_to_other<node_ptr, const value_type>::type const_pointer; static const link_mode_type link_mode = some_linking_policy; static node_ptr to_node_ptr (value_type &value); static const_node_ptr to_node_ptr (const value_type &value); static pointer to_value_ptr (node_ptr n); static const_pointer to_value_ptr (const_node_ptr n); };
Let's explain each type and function:
我們來解釋一下各個類型和函數:
slist,
node_traits should
follow the interface needed by circular_slist_algorithms.slist,則
node_traits 應遵循 circular_slist_algorithms 所需的接口。
list,
node_traits should
follow the interface needed by circular_list_algorithms.list,則
node_traits 應遵循 circular_list_algorithms 所需的接口。
set/multiset, node_traits should follow the interface
needed by rbtree_algorithms.set/multiset,則 node_traits 應遵循 rbtree_algorithms 所需的接口。
unordered_set/
unordered_multiset,
node_traits should
follow the interface needed by circular_slist_algorithms.unordered_set/
unordered_multiset,則 node_traits 應遵循 circular_slist_algorithms 所需的接口。
node_traits::node_ptr.node_traits::node_ptr 的 typedef。
node_traits::const_node_ptr.node_traits::const_node_ptr 的 typedef。
node_traits::node but it can be different (for example,
node_traits::node can be a member type of value_type). If value_type
and node_traits::node are the same type, the to_node_ptr and to_value_ptr
functions are trivial.node_traits::node 相同,也可以不同(例如,node_traits::node 可以是 value_type 的一個成員類型)。如果 value_type 和 node_traits::node 為相同類型,則 to_node_ptr 和 to_value_ptr
函數就是平凡的。
value_type.
It must be the same pointer type as node_ptr:
If node_ptr is node*,
pointer must be value_type*.
If node_ptr is smart_ptr<node_traits::node>,
pointer must be smart_ptr<value_type>.
This can be generically achieved using boost::pointer_to_other
utility from Boost SmartPointers defined
in <boost/pointer_to_other.hpp>.value_type 的指針類型。它必須是與 node_ptr 相同的指針類型:如果 node_ptr 為 node*,則 pointer 必須是 value_type*。如果 node_ptr 是 smart_ptr<node_traits::node>,則
pointer 必須是 smart_ptr<value_type>。這可以用 Boost SmartPointers 中的 boost::pointer_to_other 工具來泛型地實現,其定義在 <boost/pointer_to_other.hpp>。
const value_type. It must be the same pointer
type as node_ptr: If node_ptr is node*, const_pointer
must be const value_type*. If node_ptr
is smart_ptr<node_traits::node>,
const_pointer must be
smart_ptr<const value_type> This can be generically achieved using
boost::pointer_to_other utility from Boost SmartPointers defined in <boost/pointer_to_other.hpp>.const value_type 的指針類型。它必須是與 node_ptr 相同的指針類型:如果 node_ptr 為 node*,則 const_pointer 必須是 const value_type*。如果 node_ptr 是 smart_ptr<node_traits::node>,則
const_pointer 必須是
smart_ptr<const value_type>。這可以用 Boost SmartPointers 中的 boost::pointer_to_other 工具來泛型地實現,其定義在 <boost/pointer_to_other.hpp>。
value_traits needs
some additional work or checks from the container. The types are enumerations
defined in the link_mode.hpp
header. These are the possible types:value_traits 需要來自容器的其它工作或檢查。該類型是枚舉類型,定義於 link_mode.hpp 頭文件。有以下可能的類型:
normal_link:
If this linking policy is specified in a ValueTraits
class as the link mode, containers configured with such ValueTraits won't set the hooks of
the erased values to a default state. Containers also won't check that
the hooks of the new values are default initialized.normal_link:
如果在一個 ValueTraits
類中指定此鏈接策略為鏈接模式,那麼以這個 ValueTraits 配置的容器不會將移除值的鉤子設置為缺省狀態。容器也不會檢查某個新值的鉤子是否為缺省初始化。
safe_link:
If this linking policy is specified as the link mode in a ValueTraits class, containers configured
with this ValueTraits
will set the hooks of the erased values to a default state. Containers
also will check that the hooks of the new values are default initialized.safe_link:
如果在一個 ValueTraits 類中指定此鏈接策略為鏈接模式,那麼以這個 ValueTraits
配置的容器將會把移除值的鉤子設置為缺省狀態。容器也會檢查新值的鉤子是否為缺省初始化。
auto_unlink:
Same as "safe_link" but containers with constant-time size
features won't be compatible with ValueTraits
configured with this policy. Containers also know that a value can
be silently erased from the container without using any function provided
by the containers.auto_unlink:
與 "safe_link" 相同,但是帶有常量時間 size
函數的容器不兼容於以此策略配置的 ValueTraits
。容器也將得知它所含的值可以不通過容器所提供的函數就被悄悄地移除。
Let's define our own value_traits
class to be able to use Boost.Intrusive
containers with an old C structure whose definition can't be changed. That
legacy type has two pointers that can be used to build singly and doubly
linked lists: in singly linked lists we only need a pointer, whereas in doubly
linked lists, we need two pointers. Since we only have two pointers, we can't
insert the object in both a singly and a doubly linked list at the same time.
This is the definition of the old node:
下面我們用一個不可修改定義的、舊的C結構來定義一個我們自己的、可用於 Boost.Intrusive 的 value_traits
類。這個舊的類型有兩個指針可用於構建單鏈表和雙鏈表:在單鏈表中我們只需要一個指針,而在雙鏈表中我們需要兩個指針。因為我們只有兩個指針,所以我們不能將這個對象同時插入到一個單鏈表和一個雙鏈表中。以下是舊節點結構的定義:
#include <boost/intrusive/link_mode.hpp> #include <boost/intrusive/list.hpp> #include <boost/intrusive/slist.hpp> #include <vector> //This node is the legacy type we can't modify and we want to insert in
//intrusive list and slist containers using only two pointers, since
//we know the object will never be at the same time in both lists.
//該節點是一個我們不能修改的舊類型,而我們想將它插入到介入式的 list 和 slist 容器中,
//只使用兩個指針,因為我們知道這個對象不會被同時插入到兩個鏈表中。
struct legacy_value { legacy_value *prev_; legacy_value *next_; int id_; };
Now we have to define a NodeTraits class that will implement the functions/typedefs
that will make the legacy node compatible with Boost.Intrusive
algorithms. After that, we'll define a ValueTraits class that will configure
Boost.Intrusive containers:
現在我們必須定義一個 NodeTraits 類來實現一些函數和 typedefs,以使得這個舊節點可以兼容於 Boost.Intrusive
的算法。之後,我們將定義一個 ValueTraits 類,用於配置
Boost.Intrusive 容器:
//Define our own NodeTraits that will configure singly and doubly linked
//list algorithms. Note that this node traits is compatible with
//circular_slist_algorithms and circular_list_algorithms.
//定義我們自己的 NodeTraits,它可以用於配置單鏈表算法和雙鏈表算法。注意,這個
//節點 traits 兼容於 circular_slist_algorithms 和 circular_list_algorithms。
namespace bi = boost::intrusive; struct legacy_node_traits { typedef legacy_value node; typedef legacy_value * node_ptr; typedef const legacy_value * const_node_ptr; static node *get_next(const node *n) { return n->next_; }
static void set_next(node *n, node *next) { n->next_ = next; }
static node *get_previous(const node *n) { return n->prev_; }
static void set_previous(node *n, node *prev) { n->prev_ = prev; }
}; //This ValueTraits will configure list and slist. In this case,
//legacy_node_traits::node is the same as the
//legacy_value_traits::value_type so to_node_ptr/to_value_ptr
//functions are trivial.
//這個 ValueTraits 將用於配置 list 和 slist。此時,legacy_node_traits::node
//與 legacy_value_traits::value_type 相同,因此 to_node_ptr/to_value_ptr 函數是平凡的。
struct legacy_value_traits { typedef legacy_node_traits node_traits; typedef node_traits::node_ptr node_ptr; typedef node_traits::const_node_ptr const_node_ptr; typedef legacy_value value_type; typedef legacy_value * pointer; typedef const legacy_value * const_pointer; static const bi::link_mode_type link_mode = bi::normal_link; static node_ptr to_node_ptr (value_type &value) { return node_ptr(&value); } static const_node_ptr to_node_ptr (const value_type &value) { return const_node_ptr(&value); } static pointer to_value_ptr(node_ptr n) { return pointer(n); } static const_pointer to_value_ptr(const_node_ptr n) { return const_pointer(n); } };
Defining a value traits class that simply defines value_type
as legacy_node_traits::node is a common approach when defining
customized intrusive containers, so Boost.Intrusive
offers a templatized trivial_value_traits
class that does exactly what we want:
在定義定制化的介入式容器時,定義一個值 traits 類,並將其中的 value_type 簡單地定義為 legacy_node_traits::node 是一個常見的方法,因此 Boost.Intrusive
提供了一個模板化的 trivial_value_traits
類來完成我們想要做的事情:
#include <boost/intrusive/trivial_value_traits.hpp> //Now we can define legacy_value_traits just with a single line
//現在我們可以只用一行來定義 legacy_value_traits
using namespace boost::intrusive; typedef trivial_value_traits<legacy_node_traits, normal_link> legacy_value_traits;
Now we can just define the containers that will store the legacy abi objects
and write a little test:
現在我們可以定義保存這個傳統 abi 對象的容器並編寫一個小的測試:
//Now define an intrusive list and slist that will store legacy_value objects
//現在定義一個介入式 list 和 slist,保存 legacy_value 對像
typedef bi::value_traits<legacy_value_traits> ValueTraitsOption; typedef bi::list<legacy_value, ValueTraitsOption> LegacyAbiList; typedef bi::slist<legacy_value, ValueTraitsOption> LegacyAbiSlist; template<class List> bool test_list() { typedef std::vector<legacy_value> Vect; //Create legacy_value objects, with a different internal number
//以不同的內部數字創建 legacy_value 對像
Vect legacy_vector; for(int i = 0; i < 100; ++i){ legacy_value value; value.id_ = i; legacy_vector.push_back(value); } //Create the list with the objects 用這些對像創建 list
List mylist(legacy_vector.begin(), legacy_vector.end()); //Now test both lists 現在測試兩個鏈表
typename List::const_iterator bit(mylist.begin()), bitend(mylist.end()); typename Vect::const_iterator it(legacy_vector.begin()), itend(legacy_vector.end()); //Test the objects inserted in our list 測試插入到鏈表中的元素
for(; it != itend; ++it, ++bit) if(&*bit != &*it) return false; return true; } int main() { return test_list<LegacyAbiList>() && test_list<LegacyAbiSlist>() ? 0 : 1; }
As seen, several key elements of Boost.Intrusive
can be reused with custom user types, if the user does not want to use the
provided Boost.Intrusive facilities.
可見,Boost.Intrusive
的多個關鍵元素都可以重用於用戶類型,如果用戶不想使用已提供的 Boost.Intrusive 工具。
In the previous example, legacy_node_traits::node
type and legacy_value_traits::value_type
are the same type, but this is not necessary. It's possible to have several
ValueTraits defining the
same node_traits type (and
thus, the same node_traits::node).
This reduces the number of node algorithm instantiations, but now ValueTraits::to_node_ptr and ValueTraits::to_value_ptr
functions need to offer conversions between both types. Let's see a small
example:
在前面的例子中,legacy_node_traits::node
類型和 legacy_value_traits::value_type
是同一個類型,但這不是必需的。可以有多個
ValueTraits 都定義相同的 node_traits 類型(即,相同的 node_traits::node)。這減少了節點算法實例化的數量,不過現在 ValueTraits::to_node_ptr 和 ValueTraits::to_value_ptr
函數必須提供兩種類型之間的轉換。我們來看一個小例子:
First, we'll define the node to be used in the algorithms. For a linked list,
we just need a node that stores two pointers:
首先,我們定義要在算法中使用的節點。對於一個鏈表而言,我們只需要一個保存兩個指針的節點:
#include <boost/intrusive/link_mode.hpp> #include <boost/intrusive/list.hpp> #include <vector> //This is the node that will be used with algorithms. 這是將被算法使用的節點。
struct simple_node { simple_node *prev_; simple_node *next_; };
Now we'll define two different types that will be inserted in intrusive lists
and a templatized ValueTraits
that will work for both types:
現在,我們來定義兩個要插入到介入式鏈表中的不同類型,以及一個與這兩個類型一起使用的模板化 ValueTraits:
class base_1{}; class base_2{}; struct value_1 : public base_1, public simple_node
{ int id_; }; struct value_2 : public base_1, public base_2, public simple_node { float id_; }; //Define the node traits. A single node_traits will be enough.
//定義節點 traits。一個 node_traits 就足夠了。
struct simple_node_traits { typedef simple_node node; typedef node * node_ptr; typedef const node * const_node_ptr; static node *get_next(const node *n) { return n->next_; }
static void set_next(node *n, node *next) { n->next_ = next; }
static node *get_previous(const node *n) { return n->prev_; }
static void set_previous(node *n, node *prev) { n->prev_ = prev; }
}; //A templatized value traits for value_1 and value_2
//用於 value_1 和 value_2 的模板化 value_traits
template<class ValueType> struct simple_value_traits { typedef simple_node_traits node_traits; typedef node_traits::node_ptr node_ptr; typedef node_traits::const_node_ptr const_node_ptr; typedef ValueType value_type; typedef ValueType * pointer; typedef const ValueType * const_pointer; static const boost::intrusive::link_mode_type link_mode = boost::intrusive::normal_link; static node_ptr to_node_ptr (value_type &value) { return node_ptr(&value); } static const_node_ptr to_node_ptr (const value_type &value) { return const_node_ptr(&value); } static pointer to_value_ptr(node_ptr n) { return static_cast<value_type*>(n); } static const_pointer to_value_ptr(const_node_ptr n) { return static_cast<const value_type*>(n); } };
Now define two containers. Both containers will instantiate the same list
algorithms (circular_list_algorithms<simple_node_traits>), due to the fact that the value traits
used to define the containers provide the same node_traits
type:
現在再定義兩個容器。這兩個容器都將實例化同一個鏈表算法(circular_list_algorithms<simple_node_traits>),因為用於定義這兩個容器的值 traits 實際上提供了同一個 node_traits 類型:
//Now define two intrusive lists. Both lists will use the same algorithms:
// circular_list_algorithms<simple_node_traits>
//現在定義兩個介入式鏈表。這兩個鏈表都將使用相同的算法: circular_list_algorithms<simple_node_traits>
using namespace boost::intrusive; typedef list <value_1, value_traits<simple_value_traits<value_1> > > Value1List; typedef list <value_2, value_traits<simple_value_traits<value_2> > > Value2List;
All Boost.Intrusive containers using predefined
hooks use this technique to minimize code size: all possible list
containers created with predefined hooks that define the same VoidPointer type share the same list algorithms.
所有使用預定義鉤子的 Boost.Intrusive 容器都使用了這一技巧來最小化代碼的大小:以定義了相同的 VoidPointer 類型的預定義鉤子所創建出來的所有可能的 list
容器都共享同一個鏈表算法。
The previous example can be further simplified using the derivation_value_traits
class to define a value traits class with a value that stores the simple_node as a base class:
前面的例子還可以進一步簡化,用 derivation_value_traits
類來為將 simple_node 作為基類保存的值定義 value traits 類:
#include <boost/intrusive/derivation_value_traits.hpp> //value_1, value_2, simple_node and simple_node_traits are defined
//as in the previous example...
//和前面的例子一樣,定義 value_1, value_2, simple_node 和 simple_node_traits
//...
using namespace boost::intrusive; //Now define the needed value traits using 現在定義所需的 value traits
typedef derivation_value_traits<value_1, simple_node_traits, normal_link> ValueTraits1; typedef derivation_value_traits<value_2, simple_node_traits, normal_link> ValueTraits2; //Now define the containers 現在定義容器
typedef list <value1, value_traits<ValueTraits1> > Value1List; typedef list <value2, value_traits<ValueTraits2> > Value2List;
We can even choose to store simple_node
as a member of value_1 and
value_2 classes and use
member_value_traits
to define the needed value traits classes:
我們甚至可以選擇將 simple_node
作為 value_1 和
value_2 類的成員來保存,並使用
member_value_traits
來定義所需的 value traits 類:
class base_1{}; class base_2{}; struct value_1 : public base_1, public simple_node
{ int id_; simple_node node_; }; struct value_2 : public base_1, public base_2, public simple_node { simple_node node_; float id_; }; using namespace boost::intrusive; typedef member_value_traits <value_1, simple_node_traits, &value_1::node_, normal_link> ValueTraits1; typedef member_value_traits <value_2, simple_node_traits, &value_2::node_, normal_link> ValueTraits2; //Now define two intrusive lists. Both lists will use the same algorithms:
// circular_list_algorithms<simple_node_traits>
//現在定義兩個介入式鏈表。這兩個鏈表都將使用相同的算法: circular_list_algorithms<simple_node_traits>
typedef list <value_1, value_traits<ValueTraits1> > Value1List; typedef list <value_2, value_traits<ValueTraits2> > Value2List;
Until now all shown custom value traits are stateless, that is, the transformation between nodes and values is implemented in
terms of static functions. It's possible to use stateful
value traits so that we can separate nodes and values and avoid
modifying types to insert nodes. Boost.Intrusive
differentiates between stateful and stateless value traits by checking if
the ValueTraits class is empty:
到目前為止,所有看到的定制化 value traits 都是無狀態的,即節點與值之間的轉換是以靜態函數來實現的。我們也可以使用有狀態的
value traits,這樣我們就可以把節點和值獨立開,並避免修改類型以插入節點。Boost.Intrusive
是通過檢查 ValueTraits 類是否為空來區分有狀態和無狀態的 value traits 的:
Using stateful value traits it's possible to create containers of non-copyable/moveble
objects without modifying the definition
of the class to be inserted. This interesting property is achieved without
using global variables (stateless value traits could use global variables
to achieve the same goal), so:
使用有狀態的 value traits,可以創建不可複製/不可移動對象的容器,而無需修改被插入類的定義。這個有趣的特性無需使用全局變量即可實現(無狀態 value traits 可以通過使用全局變量實現相同的目標),因此:
Stateful value traits have many advantages but also some downsides:
有狀態的 value traits 具有很多優點,但是也有缺點:
operator*()
and operator->()).operator*() 和 operator->())。
An easy and useful example of stateful value traits is when an array of values
can be indirectly introduced in a list guaranteeing no additional allocation
apart from the initial resource reservation:
有狀態 value traits 的一個簡易且有用的例子是,將一個值數組間接地傳入到鏈表中,且保證除了初始的資源保留以外,沒有其它的內存分配:
#include <boost/intrusive/list.hpp> using namespace boost::intrusive; //This type is not modifiable so we can't store hooks or custom nodes
//這個類型是不可修改的,因此我們不能保存鉤子或定制化的節點
typedef int identifier_t; //This value traits will associate elements from an array of identifiers with
//elements of an array of nodes. The element i of the value array will use the
//node i of the node array:
//這個 value traits 將一個 identifiers 數組與一個節點數組關聯起來。
//值數組的第i個元素將使用節點數組的第i個節點:
struct stateful_value_traits { typedef list_node_traits<void*> node_traits; typedef node_traits::node node; typedef node * node_ptr; typedef const node * const_node_ptr; typedef identifier_t value_type; typedef identifier_t * pointer;
typedef const identifier_t * const_pointer;
static const link_mode_type link_mode = normal_link; stateful_value_traits(pointer ids, node_ptr node_array) : ids_(ids), nodes_(node_array) {} ///Note: non static functions!
///注意:非靜態函數!
node_ptr to_node_ptr (value_type &value) { return this->nodes_ + (&value - this->ids_); } const_node_ptr to_node_ptr (const value_type &value) const { return this->nodes_ + (&value - this->ids_); } pointer to_value_ptr(node_ptr n) { return this->ids_ + (n - this->nodes_); } const_pointer to_value_ptr(const_node_ptr n) const { return this->ids_ + (n - this->nodes_); } private: pointer ids_; node_ptr nodes_; }; int main() { const int NumElements = 100; //This is an array of ids that we want to "store"
//這是一個我們準備"存入"的 ids 數組
identifier_t ids [NumElements]; //This is an array of nodes that is necessary to form the linked list
//這是一個形成鏈表所需的節點數組
list_node_traits<void*>::node nodes [NumElements]; //Initialize id objects, each one with a different number
//用不同的數字初始化各個 id 對像
for(int i = 0; i != NumElements; ++i) ids[i] = i; //Define a list that will "link" identifiers using external nodes
//定義一個鏈表,使用外部節點來"鏈接" identifiers
typedef list<identifier_t, value_traits<stateful_value_traits> > List; //This list will store ids without modifying identifier_t instances
//Stateful value traits must be explicitly passed in the constructor.
//這個鏈表將保存 ids 而無需修改 identifier_t 實例。有狀態的 value traits 必須明確傳入給構造函數。
List my_list (stateful_value_traits (ids, nodes)); //Insert ids in reverse order in the list
//將 ids 以反序插入到鏈表中
for(identifier_t * it(&ids[0]), *itend(&ids[NumElements]); it != itend; ++it) my_list.push_front(*it); //Now test lists 現在測試鏈表
List::const_iterator list_it (my_list.cbegin()); identifier_t *it_val(&ids[NumElements-1]), *it_rbeg_val(&ids[0]-1); //Test the objects inserted in the base hook list 測試插入到基類鉤子鏈表中的對象
for(; it_val != it_rbeg_val; --it_val, ++list_it) if(&*list_it != &*it_val) return 1; return 0; }