ブーストリストのノード構造とは何ですか？

Question

見てくださいhereブーストリストのノード構造は何ですか？そして、それはコードのコメントに記載されている、これは挿入が（償却）である理由私は困難を理解することができます理解していない一定の時間：

リストは二重にリンクされたリストです。つまり、 が//両方をサポートするのはシーケンスです。順方向および逆方向トラバーサル、および（償却） 一定時間挿入および//！最初 または末尾要素の除去、又は中間

Answer 1

挿入/除去は、それが既に挿入/除去位置のノードを指しており、iterator上で動作します。

もちろん、それは一定の時間の挿入/除去を達成することができます。

---

更新：それは一定の時間を「償却」した理由を私は知らないが、あなたは内部ノードについて尋ねている、ここにあります。

template<class VoidPointer> 
struct list_hook 
{ 
    typedef typename container_detail::bi::make_list_base_hook 
     <container_detail::bi::void_pointer<VoidPointer>, container_detail::bi::link_mode<container_detail::bi::normal_link> >::type type; 
}; 

template <class T, class VoidPointer> 
struct list_node 
    : public list_hook<VoidPointer>::type 
{ 
... 
} 

それはlist_hook::typeを継承し、それでは、それが何であるかを見てみましょう：boost/container/list.hppで

、list_nodeは次のように定義されます。

intrusive/list_hook.hppで：

は

template 
    < class GetNodeAlgorithms 
    ,... 
    > 
class generic_hook 
    : ... 
    , public make_node_holder<GetNodeAlgorithms, Tag, LinkMode, HookType>::type 

それはmake_node_holder::typeを継承し、次のとおりです：

template<class VoidPointer> 
struct get_list_node_algo 
{ 
    typedef circular_list_algorithms<list_node_traits<VoidPointer> > type; 
}; 

struct make_list_base_hook 
{ 
    ... 
    typedef detail::generic_hook 
    < get_list_node_algo<typename packed_options::void_pointer> 
    , ... 
    > implementation_defined; 
    /// @endcond 
    typedef implementation_defined type; 
}; 

だから、最初のテンプレートパラメータとしてcircular_list_algorithms<list_node_traits>で、generic_hookある

template 
    < class GetNodeAlgorithms 
    , class Tag 
    , link_mode_type LinkMode 
    , int HookType 
    > 
struct make_node_holder 
{ 
    typedef typename detail::if_c 
     <!detail::is_same<Tag, member_tag>::value 
     , detail::node_holder 
     < typename GetNodeAlgorithms::type::node 
     , Tag 
     , LinkMode 
     , HookType> 
     , typename GetNodeAlgorithms::type::node 
     >::type type; 
}; 

それですタイプGetNodeAlgorithms::type::nodeと210：

template<class Node, class Tag, link_mode_type LinkMode, int> 
struct node_holder 
    : public Node 
{}; 

そしてここGetNodeAlgorithms::type::nodeはintrusive/detail/list_node.hppで定義されたlist_node_traits::node次のとおりです。

template<class VoidPointer> 
struct list_node 
{ 
    ... 
    node_ptr next_; 
    node_ptr prev_; 
}; 

template<class VoidPointer> 
struct list_node_traits 
{ 
    typedef list_node<VoidPointer> node; 
    ... 
} 

今、私たちはnext_とprev_ポインタを参照してください！

---

だからすべてに、継承ツリーは次のとおりです。

list_node 
-> list_hook::type 
    -> make_list_base_hook::type 
     -> generic_hook::type 
     -> make_node_holder::type 
      -> node_holder 
       -> Node 

Nodeのタイプはboost::intrusive::list_nodeあり、そしてそれは前と次ポインタを持っています。