设计模式之迭代器模式

● Iterator抽象迭代器

????????抽象迭代器负责定义访问和遍历元素的接口，而且基本上是有固定的2个方法：begin()获得第一个元素，end()是否已经访问到底部（Java叫做hasNext()方法）。

● ConcreteIterator具体迭代器

????????具体迭代器角色要实现迭代器接口，完成容器元素的遍历。

● Container抽象容器

????????容器角色负责提供创建具体迭代器角色的接口，必然提供一个类似createIterator()这样的

方法，在Java中一般是iterator()方法。

● ConcreteContainer具体容器

????????具体容器实现容器接口定义的方法，创建出容纳迭代器的对象。

实例分析

1、按照上面的模式结构分析，我们实现一遍，代码如下：

?Iterator.h

#include <vector>
#include <assert.h>

template <typename T>
class  IIterator
{
public:
	virtual ~IIterator() {}
	virtual void first() = 0;
	virtual void next() = 0;
	virtual bool hasNext() = 0;
	virtual T current() = 0;
};

template <typename T>
class IContainer
{
public:
	virtual ~IContainer() {}
	virtual T   get(int index) const = 0;
	virtual size_t  size() const = 0;
	virtual IIterator<T>* createIterator() = 0;
};

template <typename T>
class CConcreteIterator : public IIterator<T>
{
public:
	explicit CConcreteIterator(IContainer<T>* pContainer)
		: m_pContainer(pContainer), m_index(0) {}

public:
	void first() override {
		m_index = 0;
	}
	void next() override {
		m_index++;
	}
	bool hasNext() override {
		return  m_index != m_pContainer->size();
	}
	T current() override {
		if (m_index < m_pContainer->size()) {
			return m_pContainer->get(m_index);
		}
		assert(0);
		return T{}; //暂时这样
	}

private:
	IContainer<T>* m_pContainer;
	int m_index;
};

template <typename T>
class CConcreteContainer : public IContainer<T>
{
public:
	explicit CConcreteContainer(const std::vector<T>& v)
		: m_vecValues(v) {}
	T   get(int index) const override {
		return m_vecValues[index];
	}
	size_t  size() const override {
		return m_vecValues.size();
	}
	IIterator<T>* createIterator() override {
		return new CConcreteIterator<T>(this);
	}

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

main.cpp

#include "Iterator.h"
int  testIterator()
{
	std::vector<int> vecInt{ 1, 2, 3, 4, 5, 89, 33, 45 };

	//[1]
	std::unique_ptr<IContainer<int>> pContaner(new CConcreteContainer<int>(vecInt));
	std::unique_ptr<IIterator<int>> it(pContaner->createIterator());

	//[2]
	it->first();

	//[3]
	while (it->hasNext()) {
		qDebug() << it->current();
		it->next();
	}

	return 0;
}

????????上面的例子，模板类型T暂时只能支持std::is_pod判断为true的数据类型，如果是其它复杂类型，就需要另外处理了，所以说使用上面的代码还是有一定限制的，这里只是举例说明迭代器的原理。

????????迭代器中，主要涉及迭代器的抽象类和聚合抽象类（定义创建相应迭代器对象的接口），具体聚合类中实现创建相应的迭代器的接口。

2、C++11之后提供了获取迭代器的函数std::begin()、std::end()

template <class _Container>  //const容器的begin
_NODISCARD _CONSTEXPR17 auto begin(_Container& _Cont) -> decltype(_Cont.begin()) {
    return _Cont.begin();
}

template <class _Container> //容器的begin
_NODISCARD _CONSTEXPR17 auto begin(const _Container& _Cont) -> decltype(_Cont.begin()) {
    return _Cont.begin();
}

template <class _Container> //const容器的end
_NODISCARD _CONSTEXPR17 auto end(_Container& _Cont) -> decltype(_Cont.end()) {
    return _Cont.end();
}

template <class _Container> //容器的end
_NODISCARD _CONSTEXPR17 auto end(const _Container& _Cont) -> decltype(_Cont.end()) {
    return _Cont.end();
}

template <class _Ty, size_t _Size> //数组的begin
_NODISCARD constexpr _Ty* begin(_Ty (&_Array)[_Size]) noexcept {
    return _Array;
}

template <class _Ty, size_t _Size> //数组的end
_NODISCARD constexpr _Ty* end(_Ty (&_Array)[_Size]) noexcept {
    return _Array + _Size;
}

????????从上面的代码可以看出，STL标准的容器(如array、vector、list和map等等)和数组都能轻易的通过迭代器来访问容器；如果是用户自定义的容器，需要用std::begin和std::end来访问它，则需要自己实现_Container::begin()和_Container::end()。

? ? ? ? 统一使用std::begin()和std::end()，对调用STL的算法有很大的好处和方便，如下示例：

int a[] = { 1, 3, 5, 2, 9, 6, 8 };

std::make_heap(std::begin(a), std::end(a));
assert(std::is_heap(std::begin(a), std::end(a)));    //true

//9 3 8 2 1 6 5
std::copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;

//使第一个元素为最小
std::make_heap(std::begin(a), std::end(a), std::greater<int>());
assert(std::is_heap(std::begin(a), std::end(a), std::greater<int>()));    //true
	
//1 2 5 9 3 6 8
std::copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;

//将堆进行排序，由于上述make_heap操作使用了greater<int>()，所以在sort_heap函数的第三个参数设置为greater<int>()
std::sort_heap(std::begin(a), std::end(a), std::greater<int>());
assert(std::is_sorted(std::begin(a), std::end(a), std::greater<int>()));    //true
	
//9 8 6 5 3 2 1
std::copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;

具体实现方式探讨

????????可以考虑使用两种方式来实现iterator模式：内嵌类或者友元类。通常迭代类需访问集合类中的内部数据结构，为此可在集合类中设置迭代类为friend class，但这不利于添加新的迭代类，因为需要修改集合类，添加friend class语句。也可以在抽象迭代类中定义protected型的存取集合类内部数据的函数，这样选代子类就可以访问集合类数据了这种万式比较容易添加新的选代方式，但这种方式也存在明显快点：这些函数只能用于特定聚合类，并且不可避免造成代码更加复杂。
????????STL的vector::iterator、list::iterator、deque::iterator、rbtree::iterator等采用的都是外lterator类的形式，虽然STL的集合类的iterator分散在各个集合类中，但由于各lterator类具有相同的基类，保持了相同的对外的接口，从而使得它们看起来仍然像一个整体，同时也使得应algorithm成为可能。我们如果要扩展STL的iterator，也需要注意这一点，否则，我们扩展iterator将可能无法应用于名algorithm。

总结

1、迭代器简化了聚合的接口，有了迭代器的遍历接口，聚合本身就不再需要类似的遍历接口了，这样就简化了聚合的接口，也就简化了访问和遍历聚合对象元素的代码。

2、在同一个聚合上可以有多个遍历每个迭代器保持它自已的遍历状态，因此你可以同时进行多个遍历

3、迭代器模式解耦了聚合对象的内部表示和遍历行为，使得聚合对象的实现和遍历行为可以独立变化。

4、它支持以不同的方式遍历一个聚合复杂的聚合可用多种方式进行遍历，如二叉树的遍历，可以采用前序、中序或后序遍历。送代器模式使得改变遍历算法变得很容易：仅需用一个不同的迭代器的实例代替原先的实例即可，你可以自已定义迭代器的子类以支持新的遍历，或者可以在遍历中增加一些逻辑，如有条件的遍历等等。

5、此外，迭代器模式可以为遍历不同的聚合结构（需拥有相同的基类）提供一个统一的接口，即支持多态选代。

简单说来，迭代器模式也是Delegate原则的一个应用，它将对集合进行遍历的功能封装成独立的lterator，不但简化了集合的接口，也使得修改、增加遍历方式变得简单。从这一点讲，该模式与Bridge模式、Strategy模式有一定的相似性，但lterator模式所讨论的问题与集合密切相关，造成在lterator在实现上具有一定的特殊性。

参考书籍

<<设计模式之禅>>

<<STL源码剖析>>