设计模式-迭代器模式

Posted on Edited on Symbols count in article: 5.8k Reading time ≈ 5 mins.

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 参考