C++ STL container interator

Posted on Edited on

trace 聽說比較好讀的 LLVM libcxx。寫法是 template 所以 implementation 都在 header file 裡，這裡以 list 為例。

LLVM libcxx：http://libcxx.llvm.org/index.html

首先，class list 繼承 __list_imp。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
523 template <class _Tp, class _Alloc>
524 class __list_imp
525 {
526     __list_imp(const __list_imp&);
527     __list_imp& operator=(const __list_imp&);
528 protected:
529     typedef _Tp                                                     value_type;
533     typedef typename __alloc_traits::void_pointer                   __void_pointer;
534     typedef __list_iterator<value_type, __void_pointer>             iterator;
536     typedef __list_node_base<value_type, __void_pointer>            __node_base;
...
552     __node_base __end_;
...
587     iterator begin() _NOEXCEPT
588     {
589 #if _LIBCPP_DEBUG_LEVEL >= 2
590         return iterator(__end_.__next_, this);
591 #else
592         return iterator(__end_.__next_);
593 #endif
594     }
...
805 template <class _Tp, class _Alloc /*= allocator<_Tp>*/>
806 class _LIBCPP_TYPE_VIS_ONLY list
807     : private __list_imp<_Tp, _Alloc>
808 {

從 __list_imp::begin() 開始，iterator 在 line 534 被定義為 __list_iterator<value_type, __void_pointer>，__list_iterator 是個 class：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
273 template <class _Tp, class _VoidPtr>
274 class _LIBCPP_TYPE_VIS_ONLY __list_iterator
275 {
276     typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
277     typedef typename _NodeTraits::__link_pointer __link_pointer;
278 
279     __link_pointer __ptr_;
280 
281 #if _LIBCPP_DEBUG_LEVEL >= 2
282     _LIBCPP_INLINE_VISIBILITY
283     explicit __list_iterator(__link_pointer __p, const void* __c) _NOEXCEPT
284         : __ptr_(__p)
285     {
286         __get_db()->__insert_ic(this, __c);
287     }
288 #else
289     _LIBCPP_INLINE_VISIBILITY
290     explicit __list_iterator(__link_pointer __p) _NOEXCEPT : __ptr_(__p) {}
291 #endif

在 __list_iterator constructor 存下傳進來的 __link_pointer，也就是 __list_imp::__end_.__next_。__list_node_pointer_traits 是個 struct，裡面定義了 type __link_pointer，然後這東西追下去有點沒完沒了，照字面意思當它是個 pointer 吧。

__end_ 是個 __node_base，也就是 __list_node_base<value_type, __void_pointer>：

1
2
3
4
5
6
7
8
9
10
228 template <class _Tp, class _VoidPtr>
229 struct __list_node_base
230 {
231     typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
232     typedef typename _NodeTraits::__node_pointer __node_pointer;
233     typedef typename _NodeTraits::__base_pointer __base_pointer;
234     typedef typename _NodeTraits::__link_pointer __link_pointer;
235 
236     __link_pointer __prev_;
237     __link_pointer __next_;

那麼 __end_ 又是做什麼用的呢？我猜它跟 list 的最後一個 node 之類的有關係，所以看看 push_back() 是不是會動到它。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
1537 template <class _Tp, class _Alloc>
1538 void
1539 list<_Tp, _Alloc>::push_front(const value_type& __x)
1540 {
1541     __node_allocator& __na = base::__node_alloc();
1542     typedef __allocator_destructor<__node_allocator> _Dp;
1543     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1544     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1545     __link_pointer __nl = __hold->__as_link();
1546     __link_nodes_at_front(__nl, __nl);
1547     ++base::__sz();
1548     __hold.release();
1549 }
1550 
1551 template <class _Tp, class _Alloc>
1552 void
1553 list<_Tp, _Alloc>::push_back(const value_type& __x)
1554 {
1555     __node_allocator& __na = base::__node_alloc();
1556     typedef __allocator_destructor<__node_allocator> _Dp;
1557     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1558     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1559     __link_nodes_at_back(__hold.get()->__as_link(), __hold.get()->__as_link());
1560     ++base::__sz();
1561     __hold.release();
1562 }
...
1099 // Link in nodes [__f, __l] at the front of the list
1100 template <class _Tp, class _Alloc>
1101 inline
1102 void
1103 list<_Tp, _Alloc>::__link_nodes_at_front(__link_pointer __f, __link_pointer __l)
1104 {
1105     __f->__prev_ = base::__end_as_link();
1106     __l->__next_ = base::__end_.__next_;
1107     __l->__next_->__prev_ = __l;
1108     base::__end_.__next_ = __f;
1109 }
1110 
1111 // Link in nodes [__f, __l] at the front of the list
1112 template <class _Tp, class _Alloc>
1113 inline
1114 void
1115 list<_Tp, _Alloc>::__link_nodes_at_back(__link_pointer __f, __link_pointer __l)
1116 {
1117     __l->__next_ = base::__end_as_link();
1118     __f->__prev_ = base::__end_.__prev_;
1119     __f->__prev_->__next_ = __f;
1120     base::__end_.__prev_ = __l;
1121 }

list 繼承 __list_imp，所以 __link_nodes_at_front() 的 base::__end_ 是 __list_imp 的 __end_。從上面四個 function 看起來，__end_.__prev_ 指到 list 的最後一個 node，__end_.__next_ 指向 list 第一個 node。也就是說，__end_ 是用來記錄 list 的第一個及最後一個 node。

到這裡回頭看 begin()，它生了個 __list_iterator 並把 list 第一個 node 的 address 丟給 __list_iterator，__list_iterator 將 address 記在 __ptr_。

最後，iterator 如何取值跟移動。

1
2
3
4
5
350     _LIBCPP_INLINE_VISIBILITY
351     pointer operator->() const
352     {
357         return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__value_);
358     }

就是直接拿 value。XD

1
2
3
4
5
6
360     _LIBCPP_INLINE_VISIBILITY
361     __list_iterator& operator++()
362     {
367         __ptr_ = __ptr_->__next_;
368         return *this;
369     }

透過 __next_ 移到下一個 node。

略過很多太細節的 struct，只是想知道 STL 的 iterator 大致是如何取值以及如何做「下一個」的動作的。總結，__list_iterator 是透過 pointer 去 access __list_imp 的內部資料。

其他資料