C++ 迭代器iterator的实现原理

在经典的设计模式中，有一种迭代器模式，定义为：提供一个对象来顺序访问聚合对象中的一系列数据，而不暴露聚合对象的内部表示。

迭代器的主要优点如下。

1. 访问一个聚合对象的内容而无须暴露它的内部表示。
2. 遍历任务交由迭代器完成，这简化了聚合类。
3. 它支持以不同方式遍历一个聚合，甚至可以自定义迭代器的子类以支持新的遍历。
4. 增加新的聚合类和迭代器类都很方便，无须修改原有代码。
5. 封装性良好，为遍历不同的聚合结构提供一个统一的接口。

使用过STL的童鞋就知道，迭代器是STL使用最多的技术；那么迭代器具体是怎么实现的呢？本文来讨论一下迭代器的原理和相关实现。

1. list类

首先，我们简单的模拟一个单项链表，这个链表可以往表头插入数据，并且返回表头。

1.1 ListItem

首先，我们需要一个ListItem表示每个链表节点，这个声明如下：

namespace BH
{
    template<typename T>
	class ListItem;

	template<typename T>
	std::ostream& operator<<(std::ostream& out, ListItem<T>& d);

	template<typename T>
	class ListItem
	{
	public:
		ListItem(const T& t) : Data(t), Next(nullptr) {}
		ListItem(T&& t) : Data(std::forward<T>(t)), Next(nullptr) {}
		template<typename... Types>
		ListItem(Types&&... args) : Data(std::forward<Types>(args)...), Next(nullptr) {}

		void setnext(ListItem<T>* n)
		{
			Next = n;
		}
		ListItem<T>* next()
		{
			return Next;
		}
		friend std::ostream& operator<< <T>(std::ostream& out, ListItem& d);
	private:
		ListItem<T>* Next;
		T* Data;
	};

    template<typename T>
	std::ostream& operator<<(std::ostream& out, ListItem<T>& d)
	{
		out << d.Data;
		return out;
	}
}

首先这里构造函数：

1. 支持普通构造。
2. 支持移动函数。
3. 支持参数完美转发。
4. 友元operator<<，支持数据输出。

对于移动函数可以参考：C++ 移动函数原理浅析。

对于参数完美转发，参考：C++ 理解std::forward完美转发。

1.2 list类

这个类实现一个链表，支持简单的插入，并且返回头部节点。

namespace BH
{
	template<typename T>
	class list
	{
	public:
		list() noexcept : Head(nullptr) {}
		void push(const T& t)
		{
			ListItem<T>* Data = new ListItem<T>(t);
			Data->setnext(Head);
			Head = Data;
		}
		void push(T&& t)
		{
			ListItem<T>* Data = new ListItem<T>(t);
			Data->setnext(Head);
			Head = Data;
		}
		template<typename... Types>
		void emplace(Types&&... args)
		{
			ListItem<T>* Data = new ListItem<T>(std::forward<Types>(args)...);
			Data->setnext(Head);
			Head = Data;

		}
		ListItem<T>* front()
		{
			return Head;
		}
	private:
		ListItem<T>* Head;
	};
}

如上，为了演示，这个类实现的很简单，只支持push，和front两个操作。

2. iterator

使用过STL都知道，iterator主要是用来遍历容器中的数据节点，那么上面这个list，我们的主要功能是能够不用在外部知道list的实现原理，使用iterator来遍历数据。

所以iterator的主要功能有：

1. 支持++，遍历元素。
2. 支持*，取元素程序。
3. 支持->，指针操作。
4. 支持==和!=操作，比较iterator是否到了结尾。

所以这个实现可以如下：

namespace BH
{
    template <typename T>
	class ListIter
	{

	public:
		using value_type = T;
		using reference = T & ;
		using const_referenct = const T&;
		using pointer = T * ;
		using const_pointor = const T*;
		using size_type = size_t;
		using difference_type = ptrdiff_t;

		ListIter(pointer p = nullptr) : Iter(p) {}

		bool operator==(const ListIter& rhs) const noexcept
		{
			return Iter == rhs.Iter;
		}
		bool operator!=(const ListIter& rhs) const noexcept
		{
			return Iter != rhs.Iter;
		}
		ListIter& operator++()
		{
			Iter = Iter->next();
			return *this;
		}
		ListIter& operator++(int)
		{
			value_type tmp = *this;
			++&*this;
			return tmp;
		}
		reference operator*()
		{
			return *Iter;
		}
		pointer operator->()
		{
			return Iter;
		}
	private:
		pointer Iter;
	};
}

3. 使用

接下来，我们看一下这个iterator如何使用：

int main(int args, char* argv[])
{
	BH::list<std::string> l;
	l.push(std::string("hello"));
	l.push("world");
	l.push("abcd");
	l.push("efg");
	l.push("kmm");
	BH::ListIter<BH::ListItem<std::string>> iter(l.front());
	BH::ListIter<BH::ListItem<std::string>> end;
	while (iter != end)
	{
		std::cout << *iter << std::endl;
		++iter;
	}
	return 0;
}

输出：

kmm
efg
abcd
world
hello

4. 总结

从网上找了一个迭代器模式的UML类图，如下：

迭代器的主要作用是提供一个对象来顺序访问聚合对象中的一系列数据，而不暴露聚合对象的内部表示。通用STL的迭代器的作用也是如此，我们在使用STL的时候，不用关系vector，map，set，unordered_map的实现底层原理，使用迭代器，我们就可以遍历容器的节点数据了。