迭代器的分類與框架
迭代器是一種設計模式，用來訪問容器對象的內容而無須暴露容器的內部實現，而多叉樹是一種具有遞歸性質的復合對象，因此它的迭代器是一種復合迭代器，且存在多種遍歷順序和策略，如前序、后序、廣度、葉子、兄弟等，為了支持實現這種復合迭代器，就需要設計不同的迭代器類，由于迭代器封裝了對多叉樹的訪問，而這種訪問又可分為只讀和讀寫兩類，它們在stl中的實現就是const_iterator和iterator 類
模板，而且每種特定順序的迭代器實現，還可以按其相反的順序來遍歷，因此又衍生出了反轉迭代器，它在stl中的實現就是reserver_iterator 類
模板，這個reserver_iterator其實就是一個框架，它并不與容器直接聯系，它的實現依賴于其模板參數，當它為iterator讀寫迭代器時，就得到了一個讀寫反轉迭代器類，當它為const_iterator只讀迭代器時，就得到了一個只讀反轉迭代器類。在多叉樹中，我目前設計實現了前序、后序、葉子、深度和兄弟五種迭代器，每種迭代器均支持反轉遍歷、只讀和讀寫訪問，但是實現和stl有所不同，基本框架是每種迭代器均是帶有兩個布爾類型形參的模板類，其中一個表示是否只讀，一個表示是否反轉，從帶有一個模板形參的迭代器基類繼承，這個形參表示是否只讀，通過特化這個模板基類，就可得到只讀迭代器和讀寫迭代器類型，它們的區別在于不同的特化類攜帶的引用類型和指針類型不同，只讀迭代器攜帶的是只讀引用和指針類型，而讀寫迭代器攜帶的是非只讀引用和指針類型，由此可見，正是由于攜帶引用和指針類型的不同，所以才能實現只讀或讀寫的特性。這個迭代器基類作用是附帶公共的類型信息和實現一些公共的操作行為，如提領、取址、比較運算等，但它沒有迭代行為，具體的迭代行為則由其子類迭代器負責實現，而它最重要的作用是為上面五種迭代器的相互轉換提供了便利的接口，通過特化這5個迭代器模板類，就可得到對應的只讀、讀寫、只讀反轉、讀寫反轉4個迭代器類型，它們的關系UML圖如下
如上圖，iterator_base_impl是迭代器基類的實現模板類，pre_iterator_impl是前序遍歷迭代器的實現類
模板、post_iterator_impl是后序遍歷迭代器的實現類模板、sibling_iterator_impl是兄弟遍歷迭代器的實現類模板、fd_iterator_impl是深度遍歷迭代器的實現類模板、leaf_iterator_impl是葉子遍歷迭代器的實現類模板，后面5個類從iterator_base_impl繼承，而iterator_base_impl從stl::iterator繼承，它們6個都是mtree模板類的嵌套類，根據前面的分類，特化這6個模板類，iterator_base_impl得到2個迭代器類型，其它5個每個會有4種特化情況，得到20個迭代器類型，因此總共會得到22個迭代器類型，為了方便描述，特將iterator_base_impl對應的迭代器稱為一般迭代器。
迭代器的行為與區間
前面講到了，一般迭代器，沒有具體的遍歷行為，只有其它5種才具有，這5種迭代器的種類（iterator_category）都是雙向迭代器，即能向前和向后遍歷，對應的操作有前置遞增（operator++（int））、后置遞增（operator++）、前置遞減（operator--（int））、后置遞減（operator--）、步進（operator+=）和步退（operator-=）6種；在區間上，與stl一樣，支持使用前閉后開，這樣一來，就能與stl算法進行無縫的配合。在這里，關于哨位迭代器（end迭代器），有點與stl不一樣，由于這里的順序存儲是使用vector來實現的，那么如何來表示定位end迭代器呢？這要分以下兩種情況：
1）當一個迭代器對象沒有與實際的容器掛鉤時，對應實現是其內部樹指針為空和元素偏移量（樹結點在vector中相對于根結點的位置）為0，這時迭代行為沒有意義，但能允許進行任一迭代器與end迭代器的比較操作，這個情況下的所有迭代器的遍歷行為，都會導致程序的中斷。
2）當迭代器對象和容器掛鉤了，使用vector最后元素的下一位置來表示end迭代器，對應實現為偏移量vector::size()，在這種情況下，將遍歷區間想象設計為雙向環狀結構，如下圖所示
這樣一來，end的后一結點是第1個結點begin，前一結點是最末結點last；begin的前一結點是end，后一結點是第2個結點，也即++end==begin，--end==last，++begin=second，--begin==end。至于步進和步退的行為，當因步長迭代越界時，結果是返回end。
迭代器基類的實現
對應的實現為
iterator_base_impl類模板，其聲明如下
1
template<bool is_const>
2 class iterator_base_impl
3 : public std::iterator<std::bidirectional_iterator_tag,T,ptrdiff_t,
4 typename tree_type_trait<is_const,T,self_type,tree_node>::data_pointer_type,
5 typename tree_type_trait<is_const,T,self_type,tree_node>::data_reference_type
6 >
7
{
8
friend class mtree<T,false>;
9 typedef std::iterator<std::bidirectional_iterator_tag,T,ptrdiff_t,
10 typename tree_type_trait<is_const,T,self_type,tree_node>::data_pointer_type,
11 typename tree_type_trait<is_const,T,self_type,tree_node>::data_reference_type
12 > base_type;
13 protected:
14 typedef typename tree_type_trait<is_const,T,self_type,tree_node>::tree_pointer_type tree_pointer_type;
15 typedef typename tree_type_trait<is_const,T,self_type,tree_node>::node_pointer_type node_pointer_type;
16 typedef typename base_type::reference reference;
17 typedef typename base_type::pointer pointer;
18 public:
19 iterator_base_impl();
20 bool is_null() const;
21 reference operator*() const;
22 pointer operator->() const;
23 bool operator==(const iterator_base_impl& other) const;
24 bool operator!=(const iterator_base_impl& other) const;
25 void skip_progeny(bool skip);
26 protected:
27 iterator_base_impl(tree_pointer_type tree,size_t off,bool skip_progeny = false);
28 protected:
29 tree_pointer_type tree_;
30 size_t off_,root_;
31 bool skip_progeny_;
32
};
從上得知，operator*和operator->操作的返回類型、樹指針類型tree_pointer_type、樹結點類型node_pointer_type，實際上是由tree_type_trait模板類決定的，它和std::iterator一樣，是個空類，沒有聲明任何的成員變量及方法，只是重定義了幾種類型以方便萃取，下面是它的聲明定義
1 template<bool is_const,typename Data,typename Tree,typename Node>
2 struct tree_type_trait;
3
4 template<typename Data,typename Tree,typename Node>
5 struct tree_type_trait<true,Data,Tree,Node>
6 {
7 typedef const Data& data_reference_type;
8 typedef const Data* data_pointer_type;
9 typedef const Tree* tree_pointer_type;
10 typedef const Node* node_pointer_type;
11 };
12 template<typename Data,typename Tree,typename Node>
13 struct tree_type_trait<false,Data,Tree,Node>
14 {
15 typedef Data& data_reference_type;
16 typedef Data* data_pointer_type;
17 typedef Tree* tree_pointer_type;
18 typedef Node* node_pointer_type;
19 };
從上得知，tree_type_trait就是由其基本模板及2個特化構成的，且在命名空間tree內而不是作為mtree模板類內的成員，其中每個攜帶了不同的數據引用和指針類型、樹指針和結點類型。因此，根據模板形參is_const的取值，就可得到只讀和讀寫迭代器類型了，如下所示
1typedef iterator_base_impl<false> iterator_base;
2typedef iterator_base_impl<true> const_iterator_base;
最后，再來看一看iterator_base_impl迭代器基類的實現類模板定義，如下所示
1template<typename T>
2 template<bool is_const>
3 inline mtree<T,false>::iterator_base_impl<is_const>::iterator_base_impl
4 (tree_pointer_type tree,size_t off,bool skip_progeny /**//* = false */)
5 :tree_(tree),off_(off),root_(off),skip_progeny_(skip_progeny)
6 {
7 }
8 template<typename T>
9 template<bool is_const>
10 inline mtree<T,false>::iterator_base_impl<is_const>::iterator_base_impl()
11 :tree_(NULL),off_(0),root_(0),skip_progeny_(false)
12 {
13 }
14 template<typename T>
15 template<bool is_const>
16 inline bool mtree<T,false>::iterator_base_impl<is_const>::is_null() const
17 {
18 return NULL==tree_||off_==tree_->size();
19 }
20 template<typename T>
21 template<bool is_const>
22 inline typename mtree<T,false>::template iterator_base_impl<is_const>::reference
23 mtree<T,false>::iterator_base_impl<is_const>::operator*() const
24 {
25 return (*tree_)[off_].data_;
26 }
27 template<typename T>
28 template<bool is_const>
29 inline typename mtree<T,false>::template iterator_base_impl<is_const>::pointer
30 mtree<T,false>::iterator_base_impl<is_const>::operator->() const
31 {
32 return &(*tree_)[off_].data_;
33 }
34 template<typename T>
35 template<bool is_const>
36 inline bool mtree<T,false>::iterator_base_impl<is_const>::operator==(const iterator_base_impl<is_const>& other) const
37 {
38 return tree_==other.tree_&&off_==other.off_;
39 }
40 template<typename T>
41 template<bool is_const>
42 inline bool mtree<T,false>::iterator_base_impl<is_const>::operator!=(const iterator_base_impl<is_const>& other) const
43 {
44 return !(*this==other);
45 }
46 template<typename T>
47 template<bool is_const>
48 inline void mtree<T,false>::iterator_base_impl<is_const>::skip_progeny(bool skip)
49 {
50 skip_progeny_ = skip;
51 }
posted on 2011-07-31 07:55
春秋十二月 閱讀(2720)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm