什么是Boost列表的节点结构？

Question

Looking here我不明白什么是Boost列表的节点结构？和不理解这让我很难理解为什么插入（摊销）固定的时间因为它是在代码中的注释中提到：

列表是一个双向链表。也就是说，这是一个序列， 支持//！向前和向后遍历，和（摊销） 恒定时间插入和/！除去开头 或端元件，或在中间

Answer 1

当插入/去除，它操作上的iterator，已经指向在插入/移除位置的节点。

当然，它可以实现恒定的时间插入/移除。

---

更新：我不知道为什么它有“分期”恒定时间，但你问的是内部节点，在这里。

在boost/container/list.hpp，list_node被定义为：

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，所以让我们看看它是什么。

在intrusive/list_hook.hpp：

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

所以这是一个generic_hook，与circular_list_algorithms<list_node_traits>作为第一个模板参数：

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

它继承make_node_holder::type，那就是：

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

它是detail:node_holderGetNodeAlgorithms::type::node类型：

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，它有上一页和下一个指针。