设计模式之--迭代器模式（自定义迭代器与STL::find()配合查找链表元素）

127 阅读 0 评论 84 点赞

我是靠谱客的博主酷炫发夹，这篇文章主要介绍设计模式之--迭代器模式（自定义迭代器与STL::find()配合查找链表元素），现在分享给大家，希望可以做个参考。

以前看了好多STL的源码，总以为自己对STL的迭代器理解够深刻了，今天试着写了一下，因为刚开始没有重载operator==一直编译不过，唉，代码还是敲过一遍好，并不是眼睛看多了自己真的就熟悉了。

首先说下什么是迭代器模式：

提供一种方法，使之能够依次巡防某个容器内的各个元素，而又无需暴露该容器内部数据的表述方式

不管是泛型思维还是STL的实际运用，迭代器（iterator）都扮演者重要的角色。STL的中心思想在于：将数据容器（containers）和算法（algorithms）分开，彼此独立设计，最后再以一帖粘着剂将它们撮合在一起。这个粘着剂就是迭代器。

迭代器是一种智能指针

迭代器是一种行为类似指针的对象，而指针的各种行为最常见的就是解引用和成员访问。因此迭代器最重要的的工作就是对 operator* 和 operator-> 进行重载（overloading）工作。其次其实指针的前进、后退等等工作。

那么我就来设计一个单链表的迭代器，首先是链表节点类：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
template <typename T>
class list_node {
public:
list_node(int val, list_node* next=NULL)
: value_(val), next_(next) { }
T value() const { return value_; }
list_node* next() const { return next_; }
public:
T
value_;
list_node<T>* next_;
};

然后是链表类：

复制代码

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
template <typename T>
class linked_list {
public:
linked_list() : head_(new list_node<T>(0)), size_(0)
{ }
~linked_list() {
while(head_ != NULL){
list_node<T>* tmp = head_;
head_ = head_->next();
delete tmp;
}
}
public:
void insert_front(const T& value) {
list_node<T>* new_elem = new list_node<T>(value);
new_elem->next_ = head_->next_;
head_->next_ = new_elem;
}
void display(std::ostream &os = std::cout) const {
list_node<T>* tmp = head_->next_;
while(tmp != NULL){
os<<tmp->value()<<' ';
tmp = tmp->next();
}
}
list_node<T>* front() { return head_->next(); }
private:
list_node<T>*
head_;
long
size_;
//这个成员没用上
};

链表和链表节点类都有了，那么我们现在就缺一个迭代器了。我们来做一个迭代器用来访问链表，至少让它具备遍历链表一遍的功能吧，这样配合 std::find() 就可以实现查找功能了。

迭代器类设计如下：

复制代码

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
template <typename Item>
//struct list_iterator : public std::iterator<std::forward_iterator_tag, Item> {
//继承的方法其实更好
struct list_iterator {
public:
typedef Item
value_type;
//显示提供型别别名以供萃取
typedef Item*
pointer;
typedef Item*
iterator;
typedef Item&
reference;
typedef __gnu_cxx::ptrdiff_t
difference_type;
typedef std::forward_iterator_tag
iterator_category;
//迭代器种类选用前向迭代器
Item* ptr;
//data pointer
public:
list_iterator(Item *p = NULL)
//default NULL
: ptr(p) {}
Item& operator*() const { return *ptr; }
Item* operator->() const { return ptr; }
list_iterator& operator++() {
ptr = ptr->next();
// change ptr, finally the ptr will be NULL, and equal to end to break !
return *this;
}
list_iterator operator++(int) {
list_iterator tmp = *this;
++*this;
return tmp;
}
bool operator==(const list_iterator& i) const {
return ptr == i.ptr;
}
bool operator!=(const list_iterator& i) const {
return ptr != i.ptr;
}
};

自定义迭代器类list_iterator的设计就是上面这个样子。不过要特别注意由于要配合使用 std::find() 算法的缘故，所以必须提供相应型别别名以供其萃取。提供方法有两种：第一种是继承于 STL 提供的迭代器类，只需给明模板参数迭代器种类和迭代器模板参数 Item 即可。如果不提供，那就无法使用 STL 算法。第二种是手动提供，当然有可能会少写，不过编译期会报错。

在迭代器类 list_iterator 的设计中，list_iterator 的内部成员只有一个 ptr，并为之提供了相应的 * 和 ->，以及++等指针操作，所以完全可以说它是 smart pointer 了。迭代器list_iterator 只有一个构造函数，参数是底层指针的类型。如果构造函数不传参，默认为空，也就是迭代器 list_iterator 实际上身份就等于 NULL 。

我们下面会将链表的节点指针类型作为迭代器参数传入，如果 begin 传入链表的头指针的话，就可以构造出一个迭代器 list_iterator 对象，这个迭代器对象包裹了链表的头指针。迭代器前进++，相当于链表指针执行next()，当迭代器对象一直++，内部指针会走到 NULL。此时如果我们提前提供了一个构造函数参数为空的迭代器对象 end（也就是说它的内部ptr=NULL），那么两者比较，相等，即跳出循环，链表遍历结束。这个 list_iterator 类型的 end 对象就相当于 STL 的 end() 了。

测试代码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main()
{
linked_list<int> mylist;
for(int i=1; i<=5; ++i){
mylist.insert_front(i);
}
mylist.display();
list_iterator<list_node<int> > begin(mylist.front());
list_iterator<list_node<int> > end;
auto iter = std::find(begin, end, 6);
//default case: end.ptr = NULL :)
if(iter == end)
std::cout<<"not found"<<std::endl;
else
std::cout<<"found="<<iter->value()<<std::endl;
return 0;
}