Boost C++ 库

这是世界上最受推崇、设计最精良的 C++ 库项目之一。 Herb SutterAndrei Alexandrescu,《C++ 编码标准

带有自定义 ValueTraits 的容器 - Boost C++ 函数库
PrevUpHomeNext

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);
};

让我们解释每种类型和函数

  • node_traits:节点算法所需的节点配置。这些节点特性和算法在前一章中已描述:节点算法
  • node_ptrnode_traits::node_ptr 的类型定义。
  • const_node_ptrnode_traits::const_node_ptr 的类型定义。
  • value_type:用户希望插入到容器中的类型。此类型可以与 node_traits::node 相同,但也可以不同(例如,node_traits::node 可以是 value_type 的成员类型)。如果 value_typenode_traits::node 是相同的类型,那么 to_node_ptrto_value_ptr 函数将是平凡的。
  • pointer:指向 value_type 的指针类型。它必须与 node_ptr 相同的指针类型:如果 node_ptrnode*,则 pointer 必须是 value_type*。如果 node_ptrsmart_ptr<node_traits::node>,则 pointer 必须是 smart_ptr<value_type>。这可以使用 boost::intrusive::pointer_traits(C++11 std::pointer_traits 的可移植实现)来通用地实现。
  • const_pointer:指向 const value_type 的指针类型。它必须与 node_ptr 相同的指针类型:如果 node_ptrnode*,则 const_pointer 必须是 const value_type*。如果 node_ptrsmart_ptr<node_traits::node>,则 const_pointer 必须是 smart_ptr<const value_type>
  • link_mode:指示 value_traits 需要容器进行一些额外的处理或检查。这些类型是定义在 link_mode.hpp 头文件中的枚举。以下是可能的类型:
    • normal_link:如果此链接策略在 ValueTraits 类中指定为链接模式,则使用此类 ValueTraits 配置的容器不会将已删除值的钩子设置为默认状态。容器也不会检查新值的钩子是否已默认初始化。
    • safe_link:如果此链接策略在 ValueTraits 类中指定为链接模式,则使用此 ValueTraits 配置的容器会将已删除值的钩子设置为默认状态。容器还会检查新值的钩子是否已默认初始化。
    • auto_unlink:与 "safe_link" 相同,但具有常数时间大小特性的容器将与使用此策略配置的 ValueTraits 不兼容。容器还知道,可以从容器中静默删除一个值,而无需使用容器提供的任何函数。
  • static node_ptr to_node_ptr (value_type &value)static const_node_ptr to_node_ptr (const value_type &value):这些函数接受对 value_type 的引用,并返回一个用于节点算法的节点指针。
  • static pointer to_value_ptr (node_ptr n)static const_pointer to_value_ptr (const_node_ptr n):这些函数接受一个节点指针,并返回包含该节点的指针。

让我们定义自己的 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_ptrValueTraits::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_1value_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,可以创建不可复制/移动对象的容器,无需修改要插入的类的定义。这一重要的特性是在不使用全局变量的情况下实现的(无状态的 value traits 可以使用全局变量来实现相同的目标),因此:

  • 线程安全保证:有状态的 value traits 可以实现更好的线程安全保证,因为访问全局资源可能需要同步原语,而使用内部状态可以避免这些。
  • 灵活性:有状态的 value traits 类型可以在运行时进行配置。
  • 运行时多态:value traits 可以将节点与值之间的转换实现为虚函数。单个容器类型可以在运行时配置为使用不同的节点与值关系。

有状态的 value traits 具有许多优点,但也存在一些缺点。

  • 性能:Value traits 操作应该是非常高效的,因为它们是容器使用的基本操作。繁重的节点与值转换会损害侵入式容器的性能
  • 异常保证:有状态的 ValueTraits 必须保持无异常的保证,否则,容器的不变量将不会被保留。
  • 静态函数:侵入式容器提供的一些静态函数将不可用,因为节点与值之间的转换不是静态的。
  • 更大的迭代器:一些迭代器的大小会增加,因为迭代器需要存储指向有状态 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;
}

PrevUpHomeNext