一、類型定義
在多叉樹中，兄弟遍歷迭代器有只讀、讀寫、只讀反轉、讀寫反轉4種，在mtree容器中的定義如下：
1 typedef sibling_iterator_impl<false,false> sibling_iterator;
2 typedef sibling_iterator_impl<false,true> reverse_sibling_iterator;
3 typedef sibling_iterator_impl<true,false> const_sibling_iterator;
4 typedef sibling_iterator_impl<true,true> const_reverse_sibling_iterator;
二、接口定義
多叉樹的兄弟遍歷是指訪問給定結點的所有兄弟（包括它自己），下面代碼是兄弟遍歷迭代器的聲明：
1 template<bool is_const,bool is_reverse>
2 class sibling_iterator_impl : public iterator_base_impl<is_const>
3 {
4 friend class mtree<T,false>;
5 typedef iterator_base_impl<is_const> base_type;
6 typedef typename base_type::node_pointer_type node_pointer_type;
7 typedef typename base_type::tree_pointer_type tree_pointer_type;
8 using base_type::tree_;
9 using base_type::off_;
10 using base_type::root_;
11 public:
12 sibling_iterator_impl();
13 sibling_iterator_impl(const base_type& iter);
14 sibling_iterator_impl& operator++();
15 sibling_iterator_impl& operator--();
16 sibling_iterator_impl operator++(int);
17 sibling_iterator_impl operator--(int);
18 sibling_iterator_impl operator + (size_t off);
19 sibling_iterator_impl& operator += (size_t off);
20 sibling_iterator_impl operator - (size_t off);
21 sibling_iterator_impl& operator -= (size_t off);
22 sibling_iterator_impl begin() const;
23 sibling_iterator_impl end() const;
24 protected:
25 void first(no_reverse_tag);
26 void first(reverse_tag);
27 void last(no_reverse_tag);
28 void last(reverse_tag);
29 void increment(no_reverse_tag);
30 void increment(reverse_tag);
31 void decrement(no_reverse_tag);
32 void decrement(reverse_tag);
33 private:
34 void forward_first();
35 void forward_last();
36 void forward_next();
37 void forward_prev();
38 };
三、接口實現
下面重點講述兄弟遍歷中4種定位方法的具體實現，隨後列出其它所有方法的實現代碼。
（1）forward_first：求正向第一個兄弟，就是其父結點的第一個孩子，代碼如下：
1 template<typename T>
2 template<bool is_const,bool is_reverse>
3 inline void mtree<T,false>::sibling_iterator_impl<is_const,is_reverse>::forward_first()
4 {
5 node_pointer_type p_node = &(*tree_)[root_];
6 off_ = root_ + p_node->first_child_;
7 }
（2）forward_last：求正向最後一個兄弟，就是其父結點的最後一個孩子，代碼如下：
1 template<typename T>
2 template<bool is_const,bool is_reverse>
3 inline void mtree<T,false>::sibling_iterator_impl<is_const,is_reverse>::forward_last()
4 {
5 node_pointer_type p_node = &(*tree_)[root_];
6 off_ = root_ + p_node->last_child_;
7 }
（3）forward_next：求正向下一個兄弟，如果當前結點存在右兄弟，那麼就是它的右兄弟，否則返回end，代碼如下：
1 template<typename T>
2 template<bool is_const,bool is_reverse>
3 inline void mtree<T,false>::sibling_iterator_impl<is_const,is_reverse>::forward_next()
4 {
5 node_pointer_type p_node = &(*tree_)[off_];
6 p_node->next_sibling_ ? off_ += p_node->next_sibling_ : off_ = tree_->size();
7 }
（4）forward_prev：求正向前一個結點，如果當前結點存在左兄弟，那麼就是它的左兄弟，否則返回end，代碼如下：
1 template<typename T>
2 template<bool is_const,bool is_reverse>
3 inline void mtree<T,false>::sibling_iterator_impl<is_const,is_reverse>::forward_prev()
4 {
5 node_pointer_type p_node = &(*tree_)[off_];
6 p_node->prev_sibling_ ? off_ -= p_node->prev_sibling_ : off_ = tree_->size();
7 }
（5）構造函數的實現，代碼如下：
1 template<typename T>
2 template<bool is_const,bool is_reverse>
3 inline mtree<T,false>::sibling_iterator_impl<is_const,is_reverse>::sibling_iterator_impl()
4 :base_type()
5 {
6 }
7 template<typename T>
8 template<bool is_const,bool is_reverse>
9 inline mtree<T,false>::sibling_iterator_impl<is_const,is_reverse>::sibling_iterator_impl(const base_type& iter)
10 :base_type(iter)
11 {
12 if (!iter.is_null())
13 {
14 node_pointer_type p_node = &(*tree_)[off_];
15 p_node->parent_ ? root_ = off_ - p_node->parent_: root_ = tree_->size();
16 }
17
18 }
在上面有參構造函數中，如果結點非空，會計算保存其父結點的偏移量，存於成員變量root_中，如果不存在父結點（當為根結點時），root_等於size()。
（6）公有方法的實現，代碼如下：
1 template<typename T>
2 template<bool is_const,bool is_reverse>
3 inline typename mtree<T,false>::template sibling_iterator_impl<is_const,is_reverse>&
4 mtree<T,false>::sibling_iterator_impl<is_const,is_reverse>::operator++()
5 {
6 increment(typename reverse_trait<is_reverse>::type());
7 return *this;
8 }
9 template<typename T>
10 template<bool is_const,bool is_reverse>
11 inline typename mtree<T,false>::template sibling_iterator_impl<is_const,is_reverse>&
12 mtree<T,false>::sibling_iterator_impl<is_const,is_reverse>::operator--()
13 {
14 decrement(typename reverse_trait<is_reverse>::type());
15 return *this;
16 }
17 template<typename T>
18 template<bool is_const,bool is_reverse>
19 inline typename mtree<T,false>::template sibling_iterator_impl<is_const,is_reverse>
20 mtree<T,false>::sibling_iterator_impl<is_const,is_reverse>::operator++(int)
21 {
22 sibling_iterator_impl<is_const,is_reverse> iter(*this);
23 ++(*this);
24 return iter;
25 }
26 template<typename T>
27 template<bool is_const,bool is_reverse>
28 inline typename mtree<T,false>::template sibling_iterator_impl<is_const,is_reverse>
29 mtree<T,false>::sibling_iterator_impl<is_const,is_reverse>::operator--(int)
30 {
31 sibling_iterator_impl<is_const,is_reverse> iter(*this);
32 --(*this);
33 return iter;
34 }
35 template<typename T>
36 template<bool is_const,bool is_reverse>
37 inline typename mtree<T,false>::template sibling_iterator_impl<is_const,is_reverse>
38 mtree<T,false>::sibling_iterator_impl<is_const,is_reverse>::operator + (size_t off)
39 {
40 sibling_iterator_impl<is_const,is_reverse> iter(*this);
41 iter += off;
42 return iter;
43 }
44 template<typename T>
45 template<bool is_const,bool is_reverse>
46 inline typename mtree<T,false>::template sibling_iterator_impl<is_const,is_reverse>&
47 mtree<T,false>::sibling_iterator_impl<is_const,is_reverse>::operator += (size_t off)
48 {
49 while (off)
50 {
51 if (base_type::is_null()) break;
52 ++(*this); --off;
53 }
54 return *this;
55 }
56 template<typename T>
57 template<bool is_const,bool is_reverse>
58 inline typename mtree<T,false>::template sibling_iterator_impl<is_const,is_reverse>
59 mtree<T,false>::sibling_iterator_impl<is_const,is_reverse>::operator - (size_t off)
60 {
61 sibling_iterator_impl<is_const,is_reverse> iter(*this);
62 iter -= off;
63 return iter;
64 }
65 template<typename T>
66 template<bool is_const,bool is_reverse>
67 inline typename mtree<T,false>::template sibling_iterator_impl<is_const,is_reverse>&
68 mtree<T,false>::sibling_iterator_impl<is_const,is_reverse>::operator -= (size_t off)
69 {
70 while (off)
71 {
72 if (base_type::is_null()) break;
73 --(*this); --off;
74 }
75 return *this;
76 }
77 template<typename T>
78 template<bool is_const,bool is_reverse>
79 inline typename mtree<T,false>::template sibling_iterator_impl<is_const,is_reverse>
80 mtree<T,false>::sibling_iterator_impl<is_const,is_reverse>::begin() const
81 {
82 sibling_iterator_impl<is_const,is_reverse> iter(*this);
83 iter.first(typename reverse_trait<is_reverse>::type());
84 return iter;
85 }
86 template<typename T>
87 template<bool is_const,bool is_reverse>
88 inline typename mtree<T,false>::template sibling_iterator_impl<is_const,is_reverse>
89 mtree<T,false>::sibling_iterator_impl<is_const,is_reverse>::end() const
90 {
91 sibling_iterator_impl<is_const,is_reverse> iter(*this);
92 if (tree_)
93 {
94 iter.off_ = tree_->size();
95 }
96 return iter;
97 }
（7）間隔層定位方法的實現，代碼如下：
1 template<typename T>
2 template<bool is_const,bool is_reverse>
3 inline void mtree<T,false>::sibling_iterator_impl<is_const,is_reverse>::first(no_reverse_tag)
4 {
5 assert(tree_&&root_<=tree_->size());
6 if (root_!=tree_->size())
7 forward_first();
8 else
9 off_ = 0;
10 }
11 template<typename T>
12 template<bool is_const,bool is_reverse>
13 inline void mtree<T,false>::sibling_iterator_impl<is_const,is_reverse>::first(reverse_tag)
14 {
15 assert(tree_&&root_<=tree_->size());
16 if (root_!=tree_->size())
17 forward_last();
18 else
19 off_ = 0;
20 }
21 template<typename T>
22 template<bool is_const,bool is_reverse>
23 inline void mtree<T,false>::sibling_iterator_impl<is_const,is_reverse>::last(no_reverse_tag)
24 {
25 assert(tree_&&root_<=tree_->size());
26 if (root_!=tree_->size())
27 forward_last();
28 else
29 off_ = 0;
30 }
31 template<typename T>
32 template<bool is_const,bool is_reverse>
33 inline void mtree<T,false>::sibling_iterator_impl<is_const,is_reverse>::last(reverse_tag)
34 {
35 assert(tree_&&root_<=tree_->size());
36 if (root_!=tree_->size())
37 forward_first();
38 else
39 off_ = 0;
40 }
41 template<typename T>
42 template<bool is_const,bool is_reverse>
43 inline void mtree<T,false>::sibling_iterator_impl<is_const,is_reverse>::increment(no_reverse_tag)
44 {
45 assert(tree_&&off_<=tree_->size());
46 off_!=tree_->size() ? forward_next() : first(no_reverse_tag());
47 }
48 template<typename T>
49 template<bool is_const,bool is_reverse>
50 inline void mtree<T,false>::sibling_iterator_impl<is_const,is_reverse>::increment(reverse_tag)
51 {
52 assert(tree_&&off_<=tree_->size());
53 off_!=tree_->size() ? forward_prev() : first(reverse_tag());
54 }
55 template<typename T>
56 template<bool is_const,bool is_reverse>
57 inline void mtree<T,false>::sibling_iterator_impl<is_const,is_reverse>::decrement(no_reverse_tag)
58 {
59 assert(tree_&&off_<=tree_->size());
60 off_!=tree_->size() ? forward_prev() : last(no_reverse_tag());
61 }
62 template<typename T>
63 template<bool is_const,bool is_reverse>
64 inline void mtree<T,false>::sibling_iterator_impl<is_const,is_reverse>::decrement(reverse_tag)
65 {
66 assert(tree_&&off_<=tree_->size());
67 off_!=tree_->size() ? forward_next() : last(reverse_tag());
68 }
四、使用示例
（1）正向遍歷某結點的兄弟，代碼如下：
1 mtree<int,false>::iterator_base node;
2 mtree<int,false>::sibling_iterator it = node;
3 mtree<int,false>::sibling_iterator last = --it.end();
4 for (it = it.begin();it!=it.end();++it)
5 {
6 cout << *it;
7 if (it!=last)
8 cout <<" ";
9 }
（2）反向遍歷某結點的兄弟，代碼如下：
1 mtree<int,false>::iterator_base node;
2 mtree<int,false>::reverse_sibling_iterator r_it = node;
3 mtree<int,false>::reverse_sibling_iterator r_last = --r_it.end();
4 for (r_it = r_it.begin();r_it!=r_it.end();++r_it)
5 {
6 cout << *r_it;
7 if (r_it!=r_last)
8 cout <<" ";
9 }
