Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

Containers with custom ValueTraits 帶定制化 ValueTraits 的容器

ValueTraits interface  ValueTraits 接口
Custom ValueTraits example 定制化 ValueTraits 的例子
Reusing node algorithms for different values 為不同值重用節點算法
Simplifying value traits definition 簡化 value traits 的定義
Stateful value traits 有狀態的值 traits

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:
我們來解釋一下各個類型和函數:

  • node_traits: The node configuration that is needed by node algorithms. These node traits and algorithms are described in the previous chapter: Node Algorithms.
    node_traits: 節點算法所需的節點配置信息。這些節點 traits 和算法在前面的章節中已有說明:節點算法
  • node_ptr: A typedef for node_traits::node_ptr.
    node_ptrnode_traits::node_ptr 的 typedef。
  • const_node_ptr: A typedef for node_traits::const_node_ptr.
    const_node_ptrnode_traits::const_node_ptr 的 typedef。
  • value_type: The type that the user wants to insert in the container. This type can be the same as 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.
    value_type: 用戶想要插入到容器中的類型。該類型可以與 node_traits::node 相同,也可以不同(例如,node_traits::node 可以是 value_type 的一個成員類型)。如果 value_typenode_traits::node 為相同類型,則 to_node_ptrto_value_ptr 函數就是平凡的。
  • pointer: The type of a pointer to a 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>.
    pointervalue_type 的指針類型。它必須是與 node_ptr 相同的指針類型:如果 node_ptrnode*,則 pointer 必須是 value_type*。如果 node_ptrsmart_ptr<node_traits::node>,則 pointer 必須是 smart_ptr<value_type>。這可以用 Boost SmartPointers 中的 boost::pointer_to_other 工具來泛型地實現,其定義在 <boost/pointer_to_other.hpp>
  • const_pointer: The type of a pointer to a 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_pointerconst value_type 的指針類型。它必須是與 node_ptr 相同的指針類型:如果 node_ptrnode*,則 const_pointer 必須是 const value_type*。如果 node_ptrsmart_ptr<node_traits::node>,則 const_pointer 必須是 smart_ptr<const value_type>。這可以用 Boost SmartPointers 中的 boost::pointer_to_other 工具來泛型地實現,其定義在 <boost/pointer_to_other.hpp>
  • link_mode: Indicates that 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:
    link_mode: 表示 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 。容器也將得知它所含的值可以不通過容器所提供的函數就被悄悄地移除。
  • static node_ptr to_node_ptr (value_type &value) and static const_node_ptr to_node_ptr (const value_type &value): These functions take a reference to a value_type and return a pointer to the node to be used with node algorithms.
    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) and static const_pointer to_value_ptr (const_node_ptr n): These functions take a pointer to a node and return a pointer to the value that contains the node.
    static node_ptr to_node_ptr (value_type &value)static const_node_ptr to_node_ptr (const value_type &value): 這兩個函數接受一個節點指針,返回指向包含該節點的值的指針。

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.Intrusivevalue_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_ptrValueTraits::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_1value_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 的:

  • If the class is empty, a stateless value traits is assumed. Node <-> Value transformations must be static functions.
    如果類為空,則假設為 無狀態 value traits。節點 <-> 值的轉換必須是靜態函數。
  • If the class is not empty, a stateful value traits is assumed. Node <-> Value transformations must be non-static functions.
    如果類為非空,則假設為 有狀態 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 可以通過使用全局變量實現相同的目標),因此:

  • Thread-safety guarantees: Better thread-safety guarantees can be achieved with stateful value traits, since accessing global resources might require syncronization primitives that can be avoided when using internal state.
    線程安全性保證:使用有狀態 value traits 可以實現更好的線程安全性保證,因為訪問全局變量有可能需要同步原語,而使用內部狀態則可以避免它。
  • Flexibility: A stateful value traits type can be configured at run-time.
    靈活性:有狀態 value traits 類型可以在運行期進行配置。
  • Run-time polymorphism: A value traits might implement node <-> value transformations as virtual functions. A single container type could be configured at run-time to use different node <-> value relatioships.
    運行期多態:value traits 可以將節點 <-> 值的轉換實現為虛擬函數。一個容器類型可以在運行期配置為使用不同的節點 <-> 值關係。

Stateful value traits have many advantages but also some downsides:
有狀態的 value traits 具有很多優點,但是也有缺點:

  • Performance: Value traits operations should be very efficient since they are basic operations used by containers. A heavy node <-> value transformation will hurt intrusive containers' performance.
    性能:Value traits 操作應該是非常高效的,因為它們是容器要使用的基本操作。一個笨重的節點 <-> 值轉換會損害介入式容器的性能
  • Exception guarantees: The stateful ValueTraits must maintain no-throw guarantees, otherwise, the container invariants won't be preserved.
    異常安全性:有狀態 ValueTraits 必須提供無拋出的保證,否則容器的不變式將得不到保護。
  • Static functions: Some static functions offered by intrusive containers are not available because node <-> value transformations are not static.
    靜態函數:介入式容器提供的某些靜態函數將會無效,因為節點 <-> 值的轉換是非靜態的。
  • Bigger iterators: The size of some iterators is increased because the iterator needs to store a pointer to the stateful value traits to implement node to value tranformations (e.g. operator*() and operator->()).
    更大的迭代器:有些迭代器的大小將有所增加,因為迭代器需要保存一個指向有狀態 value traits 的指針以實現節點到值的轉換(如 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; }


PrevUpHomeNext