부스트리스트의 노드 구조 란 무엇입니까?

Question

Looking here Boost 목록의 노드 구조가 무엇인지 이해할 수 없습니까? 그리고이 삽입이 (상각) 왜 그것이 코드 주석에서 언급 나를 어렵게 일정 시간을 이해하게 이해하지 :

목록은 이중 연결리스트이다. 즉, 이 // 둘 다 지원하는 시퀀스입니다. 순방향 및 역방향 트래버스 및 (상각 된) 상수 시간 삽입 및 //! 처음 또는 마지막 요소의 제거, 또는 중간

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::node210 :

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

그리고 여기 GetNodeAlgorithms::type::node는 list_node_traits::node가 intrusive/detail/list_node.hpp에 정의되어

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이며,이 이전 및 다음 포인터를 가지고있다.