迭代器的分类与框架
迭代器是一种设计模式，用来访问容器对象的内容而无须暴露容器的内部实现，而多叉树是一种具有递归性质的复合对象，因此它的迭代器是一种复合迭代器，且存在多种遍历顺序和策略，如前序、后序、广度、叶子、兄弟等，为了支持实现这种复合迭代器，就需要设计不同的迭代器类，由于迭代器封装了对多叉树的访问，而这种访问又可分为只读和读写两类，它们在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
春秋十二月 阅读(2713)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm