设计模式-迭代器模式

发表于 更新于 本文字数： 1.1k 阅读时长 ≈ 4 分钟

1 迭代器模式

  • 在软件构建过程中，集合对象内部结构常常变化各异。但对于这些集合对象，我们希望在不暴露其内部结构的同时，可以让外部客户代码透明地访问其中包含的元素;同时这种“诱明遍历”也为“同一种算法在多种集合对象上进行操作”提供了可能。
  • 提供一种方法顺序访问一个聚合对象中的各个元素，而又不暴露（稳定）该对象的内部表示
  • 访问一个聚合对象的内容而无需暴露其内部实现；支持对聚合对象的多种遍历；为遍历不同的聚合结构提供统一的接口；健壮性考虑：遍历的同时更改迭代器所在聚合结构，会导致问题
  • 该篇介绍的是基于面向对象的迭代器实现，但是C++泛型编程迭代器已经淘汰掉面向对象的迭代器，然而思想一样，技术更新而已

2 迭代器v1

迭代器模式

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
/*
C++现在都是基于模板的迭代器，模板又称为编译时多态，速度肯定比虚函数的运行时多态要好很多
但是java、C#、PHP、Swift还是这种基于虚函数的迭代器（因为不支持编译时的模板机制）
*/
template<typename T>
class Iterator{
public:
    virtual void first() = 0;
    virtual void next() = 0;
    virtual bool isDone() const = 0;
    virtual T& current() = 0;
};

template<typename T>
class MyCollection{
public:
    Iterator<T>* GetIterator(){
        // ...
    }
};

template<typename T>
class CollectionIterator : public Iterator<T>{
    MyCollection<T> mc;
public:
    CollectionIterator(const MyCollection<T>& c): mc(c){ }
    
    void first() override {
        // ...
    }
    void next() override {
        // ...
    }
    bool isDone() const override{
        // ...
    }
    T& current() override{
        // ...
    }
};

void MyAlgorithm(){
    MyCollection<int> mc;
    Iterator<int>* iter = mc.GetIterator();
    for (iter->first(); !iter->isDone(); iter->next()){ // 多态
        cout << iter->current() << endl; // 多态
    }
}

3 迭代器v2（可执行）

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
/**
 * C++ has its own implementation of iterator that works with a different
 * generics containers defined by the standard library.
 */
template <typename T, typename U>
class Iterator {
public:
	typedef typename std::vector<T>::iterator iter_type;
	Iterator(U *p_data) : m_p_data_(p_data) {
		m_it_ = m_p_data_->m_data_.begin();
	}
	void First() {
		m_it_ = m_p_data_->m_data_.begin();
	}
	void Next() {
		m_it_++;
	}
	bool IsDone() {
		return (m_it_ == m_p_data_->m_data_.end());
	}
	iter_type Current() {
		return m_it_;
	}

private:
	U *m_p_data_;
	iter_type m_it_;
};

/**
 * Generic Collections/Containers provides one or several methods for retrieving
 * fresh iterator instances, compatible with the collection class.
 */

template <class T>
class Container {
	friend class Iterator<T, Container>;

public:
	void Add(T a) {
		m_data_.push_back(a);
	}
	Iterator<T, Container> *CreateIterator() {
		return new Iterator<T, Container>(this);
	}

private:
	std::vector<T> m_data_;
};

class Data {
public:
	Data(int a = 0) : m_data_(a) {}
	void set_data(int a) {
		m_data_ = a;
	}
	int data() {
		return m_data_;
	}

private:
	int m_data_;
};

/**
 * The client code may or may not know about the Concrete Iterator or Collection
 * classes, for this implementation the container is generic so you can used
 * with an int or with a custom class.
 */
void ClientCode() {
	std::cout << "__________Iterator with int__________" << std::endl;
	Container<int> cont;

	for (int i = 0; i < 10; i++) {
		cont.Add(i);
	}

	Iterator<int, Container<int>> *it = cont.CreateIterator();
	for (it->First(); !it->IsDone(); it->Next()) {
		std::cout << *it->Current() << std::endl;
	}

	Container<Data> cont2;
	Data a(100), b(1000), c(10000);
	cont2.Add(a);
	cont2.Add(b);
	cont2.Add(c);

	std::cout << "__________Iterator with custom Class__________" << std::endl;
	Iterator<Data, Container<Data>> *it2 = cont2.CreateIterator();
	for (it2->First(); !it2->IsDone(); it2->Next()) {
		std::cout << it2->Current()->data() << std::endl;
	}
	delete it;
	delete it2;
}

int main() {
	ClientCode();
	return 0;
}

4 迭代器v3（可执行）

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
template <class Item>
class Iterator {
public:
	virtual ~Iterator() {}
	virtual bool hasNext() = 0;
	virtual Item next() = 0;
};

template <class Item>
class Aggregate{
public:
	virtual ~Aggregate() {}
	virtual Iterator<Item> *CreateIterator() = 0;
};

// 前置声明
template <class Item>
class BookSelfIterator;

template <class Item>
class BookSelf : public Aggregate<Item> {
public:
	BookSelf(int maxSize) {
		m_books.resize(maxSize, std::string(""));
	}
	Iterator<Item>* CreateIterator() override {
		return new BookSelfIterator<Item>(this); // 传入this
	}
	Item GetBookAt(int index) const {
		return m_books.at(index);
	}
	void appendBoox(const Item &book) {
		m_books.emplace_back(book);
	}
	int length() const {
		return static_cast<int>(m_books.size());
	}
private:
	std::vector<Item> m_books;
};

template <class Item>
class BookSelfIterator : public Iterator<Item> {
public:
	BookSelfIterator(BookSelf<Item> *bookSelf) : m_bookSelf(bookSelf) {}
	virtual bool hasNext() override {
		return m_bookSelf->length() > 0 && m_currentIndex < m_bookSelf->length() - 1;
	}
	virtual Item next() override {
		m_currentIndex++;
		return m_bookSelf->GetBookAt(m_currentIndex);
	}

private:
	BookSelf<Item> *m_bookSelf;
	int m_currentIndex = -1;
};


class Book {
public:
	Book(const std::string &name) : m_name(name) {}
	const std::string &GetName() {
		return m_name;
	}
private:
	std::string m_name;
};

int main() {
	BookSelf<Book> container(0);
	container.appendBoox(Book(string("name1")));
	container.appendBoox(Book(string("name2")));
	container.appendBoox(Book(string("name3")));
	auto itor = container.CreateIterator();
	while (itor->hasNext()) {
		Book book = itor->next();
		cout << book.GetName() << endl;
	}
	delete itor;
	return 0;
}

5 总结

  • 迭代抽象：访问一个聚合对象的内容而无需暴露它的内部表示。
  • 迭代多态：为遍历不同的集合结构提供一个统一的接口，从而支持同样的算法在不同的集合结构上进行操作。
  • 迭代器的健壮性考虑：遍历的同时更改迭代器所在的集合结构，会导致问题。

6 参考