如Concepts章节所述,Boost.Intrusive 容器需要一个 ValueTraits
类来执行节点和用户值的转换。 ValueTraits
可以显式配置(使用 value_traits<>
选项)或隐式配置(使用钩子及其 base_hook<>
/ member_hook<>
选项)。 ValueTraits
包含所有必要信息,用于连接容器的 value_type
和节点算法中使用的节点,因为这些类型可能不同。除此之外,ValueTraits
还存储有关要插入的值的链接策略的信息。
用户可能不想使用 Boost.Intrusive 预定义的钩子,而是想开发自定义容器,例如,使用针对特定应用程序优化的节点,或者与旧版 ABI 兼容的节点。用户可能只希望在他的类中包含两个额外的指针,并且有时将类插入到双向链表中,有时插入到单向链表中。使用 Boost.Intrusive 预定义的钩子无法实现这一点。现在,用户将指定 value_traits<...>
选项,而不是使用 base_hook<...>
或 member_hook<...>
选项。让我们看看如何做到这一点。
ValueTraits
具有以下接口
#include <boost/intrusive/pointer_traits.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::intrusive::pointer_traits<node_ptr>::rebind_traits <value_type>::type::pointer pointer; typedef boost::intrusive::pointer_traits<node_ptr>::rebind_traits <const value_type>::type::pointer 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); };
让我们解释每种类型和函数
slist
一起使用,那么 node_traits
应该遵循 circular_slist_algorithms
所需的接口。list
一起使用,那么 node_traits
应该遵循 circular_list_algorithms
所需的接口。set
/ multiset
一起使用,那么 node_traits
应该遵循 rbtree_algorithms
所需的接口。unordered_set
/ unordered_multiset
一起使用,那么 node_traits
应该遵循 circular_slist_algorithms
所需的接口。node_traits::node_ptr
的类型定义。node_traits::const_node_ptr
的类型定义。node_traits::node
相同,但也可以不同(例如,node_traits::node
可以是 value_type
的成员类型)。如果 value_type
和 node_traits::node
是相同的类型,那么 to_node_ptr
和 to_value_ptr
函数将是平凡的。value_type
的指针类型。它必须与 node_ptr
相同的指针类型:如果 node_ptr
是 node*
,则 pointer
必须是 value_type*
。如果 node_ptr
是 smart_ptr<node_traits::node>
,则 pointer
必须是 smart_ptr<value_type>
。这可以使用 boost::intrusive::pointer_traits
(C++11 std::pointer_traits
的可移植实现)来通用地实现。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>
。value_traits
需要容器进行一些额外的处理或检查。这些类型是定义在 link_mode.hpp
头文件中的枚举。以下是可能的类型:normal_link
:如果此链接策略在 ValueTraits
类中指定为链接模式,则使用此类 ValueTraits
配置的容器不会将已删除值的钩子设置为默认状态。容器也不会检查新值的钩子是否已默认初始化。safe_link
:如果此链接策略在 ValueTraits
类中指定为链接模式,则使用此 ValueTraits
配置的容器会将已删除值的钩子设置为默认状态。容器还会检查新值的钩子是否已默认初始化。auto_unlink
:与 "safe_link" 相同,但具有常数时间大小特性的容器将与使用此策略配置的 ValueTraits
不兼容。容器还知道,可以从容器中静默删除一个值,而无需使用容器提供的任何函数。让我们定义自己的 value_traits
类,以便能够使用 Boost.Intrusive 容器与一个无法更改定义的旧 C 结构。该遗留类型有两个指针,可用于构建单向和双向链表:在单向链表中,我们只需要一个指针,而在双向链表中,我们需要两个指针。由于我们只有两个指针,因此无法同时将对象插入到单向链表和双向链表中。这是旧节点的定义:
#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. struct legacy_value { legacy_value *prev_; legacy_value *next_; int id_; };
现在,我们必须定义一个 NodeTraits 类,它将实现将遗留节点与 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. 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. 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); } };
定义一个 value traits 类,它仅将 value_type
定义为 legacy_node_traits::node
,这是定义自定义侵入式容器的常用方法,因此 Boost.Intrusive 提供了一个模板化的 trivial_value_traits
类,它正好实现了我们想要的功能。
typedef bi::trivial_value_traits<legacy_node_traits, bi::normal_link> trivial_legacy_value_traits;
现在我们可以仅定义存储遗留 abi 对象的容器,并编写一个简单的测试。
//Now define an intrusive list and slist that will store legacy_value objects typedef bi::value_traits<legacy_value_traits> ValueTraitsOption; typedef bi::value_traits<trivial_legacy_value_traits> TrivialValueTraitsOption; typedef bi::list<legacy_value, ValueTraitsOption> LegacyAbiList; typedef bi::slist<legacy_value, ValueTraitsOption> LegacyAbiSlist; typedef bi::list<legacy_value, TrivialValueTraitsOption> TrivialLegacyAbiList; typedef bi::slist<legacy_value, TrivialValueTraitsOption> TrivialLegacyAbiSlist; template<class List> bool test_list() { typedef std::vector<legacy_value> Vect; //Create legacy_value objects, with a different internal number 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 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>() && test_list<TrivialLegacyAbiList>() && test_list<TrivialLegacyAbiSlist>() ? 0 : 1; }
正如所见,Boost.Intrusive 的几个关键元素可以与自定义用户类型重用,前提是用户不想使用提供的 Boost.Intrusive 功能。
在前面的示例中,legacy_node_traits::node
类型和 legacy_value_traits::value_type
是相同的类型,但这并非必需。可以有多个 ValueTraits
定义相同的 node_traits
类型(因此,相同的 node_traits::node
)。这减少了节点算法的实例化次数,但现在 ValueTraits::to_node_ptr
和 ValueTraits::to_value_ptr
函数需要提供这两种类型之间的转换。让我们看一个小例子。
首先,我们将定义要在算法中使用的节点。对于链表,我们只需要一个存储两个指针的节点。
#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_; };
现在,我们将定义两个将被插入到侵入式列表中的不同类型,以及一个模板化的 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. 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 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); } };
现在定义两个容器。由于用于定义容器的值特性提供了相同的 node_traits
类型,因此这两个容器都将实例化相同的列表算法(circular_list_algorithms<simple_node_traits>
)。
//Now define two intrusive lists. Both lists will use the same algorithms: // 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;
所有使用预定义钩子的 Boost.Intrusive 容器都使用此技术来最小化代码大小:所有由预定义钩子创建的可能的 list
容器,如果它们定义了相同的 VoidPointer
类型,则共享相同的列表算法。
可以使用 derivation_value_traits
类来进一步简化前面的示例,以定义一个 simple_node
作为基类的 value,其 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; //Now define the needed value traits using derivation_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 two intrusive lists. Both lists will use the same algorithms: // circular_list_algorithms<simple_node_traits> typedef list <value_1, value_traits<ValueTraits1> > Value1List; typedef list <value_2, value_traits<ValueTraits2> > Value2List;
我们甚至可以选择将 simple_node
存储为 value_1
和 value_2
类的成员,并使用 member_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> typedef list <value_1, value_traits<ValueTraits1> > Value1List; typedef list <value_2, value_traits<ValueTraits2> > Value2List;
到目前为止,所有展示的自定义 value traits 都是无状态的,也就是说,节点和值之间的转换是通过静态函数实现的。可以使用有状态的 value traits,以便我们可以分离节点和值,并避免修改要插入节点的类型。Boost.Intrusive 通过检查所有节点与值之间的转换函数是否为静态来区分有状态和无状态的 value traits(Visual 7.1 除外,因为无法检测重载的静态函数,在这种情况下,实现会检查类是否为空)。
使用有状态的 value traits,可以创建不可复制/移动对象的容器,无需修改要插入的类的定义。这一重要的特性是在不使用全局变量的情况下实现的(无状态的 value traits 可以使用全局变量来实现相同的目标),因此:
有状态的 value traits 具有许多优点,但也存在一些缺点。
operator*()
和 operator->()
)。有状态 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: 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) const { 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) const { 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" 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 for(int i = 0; i != NumElements; ++i) ids[i] = i; //Define a list that will "link" identifiers using external nodes 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. List my_list (stateful_value_traits (ids, nodes)); //Insert ids in reverse order in the list 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]), *it_rbeg_val(&ids[0]); //Test the objects inserted in the base hook list for(; it_val != it_rbeg_val; --it_val, ++list_it) if(&*list_it != &it_val[-1]) return 1; return 0; }