STL - 迭代器

迭代器概念

STL设计迭代器的初衷就是将容器细节与算法分离，转而用迭代器作为两者的桥梁。迭代器作为一种访问容器的结构，其本质上也是一种对指针的高级包装而已，因此对应于容器的结构特点，迭代器也分为单向迭代器(典型如单链表)、双向迭代器(如双链表)和随机访问迭代器(如vector等顺序存储容器)。

迭代器的实现

作为对容器元素指针的高级包装，迭代器不可避免的会暴露容器的实现细节，因此将迭代器完全脱离容器是不现实的，故STL容器都在内部实现了对应于特定容器的迭代器。为了说明迭代器的实现原理，下面以一个自定义的容器类MyList来进行演示：

#ifndef _MYLIST
#define _MYLIST
#include <iostream>

template<typename T>
struct MyListNode
{
	T _value;
	MyListNode<T>* _next;

	MyListNode():_value(0),_next(nullptr) {}
};

template<typename NodeTy>
class MyListIter
{
public:
	NodeTy* ptr;
	MyListIter( NodeTy* p = nullptr) :ptr(p){}

	NodeTy& operator*() const { return *ptr; }
	NodeTy* operator->() const { return ptr; }

	MyListIter& operator++() { ptr = ptr->_next; return *this; }
	MyListIter operator++(int) { MyListIter tmp = (*this); ++(*this); return tmp; }

	bool operator==(const MyListIter& i) const { return ptr == i.ptr; }
	bool operator!=(const MyListIter& i) const { return ptr != i.ptr; }

};

template<typename T>
class MyList
{
private:
	MyListNode<T>* _head;

public:
	void insert_front(T v) 
	{ 
		MyListNode<T>* tmp = new MyListNode<T>;
		tmp->_value = v;
		tmp->_next = _head->_next;
		_head->_next=tmp;
	}

	void display(std::ostream& os = std::cout) const
	{
		MyListNode<T>* tmp = _head->_next;
		while (tmp)
		{
			os << tmp->_value<<" ";
			tmp = tmp->_next;
		}
	}

	MyList() 
	{ 
		_head = new MyListNode<T>;
	}

	MyListIter<MyListNode<T>> begin() const
	{
		return MyListIter<MyListNode<T>>(_head->_next);
	}

	MyListIter<MyListNode<T>> end() const
	{
		return MyListIter<MyListNode<T>>(nullptr);
	}
};

#endif

main:

#include "mylist.h"

template<typename IterTy,typename Ty>
IterTy find(IterTy begin,IterTy end, Ty value);

int main()
{
	MyList<int> mylist;
	for (int i = 0; i < 5;i++)
		mylist.insert_front(i);
	mylist.display();
	auto ibegin=mylist.begin();
	auto iend = mylist.end();
	auto result = find(ibegin, iend, 2);
	std::cout << result.ptr->_value;
}

template<typename IterTy, typename Ty>
IterTy find(IterTy begin, IterTy end, Ty value)
{
	while (begin != end)
	{
		if (begin->_value == value)
			break;
		begin++;
	}
	return begin;
}

通过上面的简单链表迭代器，我们成功实现了独立于容器的泛型算法find。上述的迭代器仅仅是个雏形，如果一个算法需要一个迭代器类型变量而返回一个迭代器指向的元素类型，在仅使用一个模板参数的情况下，上述迭代器根本不可能做到。例如：

//两个参数可行
template<typename IterTy,typename NodeTy>
NodeTy somefunc(IterTy iter,NodeTy el)
{
	NodeTy tmp;
	...
	return tmp;
}

//一个参数无法完成
template<typename IterTy>
? somefunc(IterTy iter)
{
	? tmp;
}

实际上以上问题在allocator中已经出现过，STL在allocator中的解决方法是rebind，简单来说就是将可能会用到的类型定义为内嵌类型：

template<typename NodeTy>
class MyListIter
{
public:
	typedef NodeTy value_type;
	//...
}

template<typename IterTy>
typename IterTy::value_type somefunc(IterTy iter)
{
	//现在仅需要一个模板参数
	typename IterTy::value_type tmp；
}

然而以上技巧仅适用于迭代器类，对于无法定义内嵌类型的原生指针无能为力。泛型算法不应该仅考虑到迭代器，原生指针的行为理应与迭代器类似。

Traits编程技巧

Traits直译为“特性，特征”，即人为的赋予对象某些修饰，在需要的时候提取出来。显而易见，traits技术也只能用于类，仍然对原生指针束手无策。为了解决此问题，我们需要对原生指针进行一次包装，而包装方法就是使用模板偏特化：

template<typename IterTy>
struct iter_traits
{
	typedef typename IterTy::value_type value_type;
}

//指针偏特化模板
template<typename Ty>
struct iter_traits<Ty*>
{
	typedef Ty value_type;
}

现在无论是原生指针还是迭代器都可以使用iter_traits::value_type获取指向的元素类型。根据编程经验，STL规定迭代器至少定义5种基本特性：value_type、difference_type、pointer、reference和iterator_category

1. value_type:即迭代器指向的元素类型
2. difference_type:迭代器之间的距离
3. pointer:指向元素的指针
4. reference:元素的引用
5. category:迭代器类型

前面提到迭代器对应于特定容器分为单向迭代器、双向迭代器和随机访问迭代器，功能上还可分为输入迭代器和输出迭代器。很显然不同迭代器可定义的操作和效率是不同的，因此区分迭代器类型有利于提升性能。以advance()函数为例，该函数将一个给定的迭代器移动给定的距离：

//单向迭代器
template<typename ForwardIter,typename Distance>
void advance_fiter(ForwardIter& i,Distance n)
{
	while(n--)
		i++;
}

//双向迭代器
template<typename BidIter,typename Distance>
void advance_biter(BidIter& i,Distance n)
{
	if(n>0)
	{
		while(n--)
			i++;
	}
	else
	{
		while(n++)
			i--;
	}
}

//随机访问迭代器
template<typename RndIter,typename Distance>
void advance_rnditer(RndIter& i,Distance n)
{
	i += n;
}

为了区分迭代器类型而设计三个函数显然不明智，然而上述函数都是两个模板参数的模板函数，无法重载，因此需要引入另一个不同的参数达成重载条件，STL的做法是引入一个迭代器类型参数：

struct input_iterator_tag{};
struct output_iterator_tag{};
struct forward_iterator_tag:public input_iterator_tag{};
struct bidirectional_iterator_tag:public forward_iterator_tag{};
struct random_access_iterator_tag:public bidirectional)iterator_tag{};

//内部实现
template<typename InputIter,typename Distance>
void _advance(InputIter& i,Distance n,input_iterator_tag)
{
	//...
}

//...

//外部接口
template<typename Iterator,Distance n>
void advance(Iterator& i,Distance n)
{
	_advance(i,n,iterator_traits<Iterator>::iterator_category());
}

如上，通过定义几个用于标识迭代器类型的空类并作为参数启用函数重载，并在外部调用时使用traits技术获取迭代器类型，完成了不同迭代器的函数实现。并且STL迭代器类型是继承关系，利用模板协变，适用于低级迭代器的函数也可用于高级迭代器。