vector与list和各自iterator剖析2

迭代器是连接容器和算法的纽带，它们为数据提供了一种抽象的观点，使写算法的人不必关心多种多样的数据结构的具体细节。

1，迭代器概述

　　迭代器是指向序列元素的指针的一种抽象。通过使用迭代器，我们可以访问序列中的某个元素、改变序列中的某个元素的值、使迭代器向前或向后行走等等。

　　依据有效执行操作的情况，迭代器可以分为五类：输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机存取迭代器。STL中用五个类来代表这五种迭代器类别：

　　其中

　　· Input Iterator 所指的对象不允许外界改变

　　· Output Iterator 支持对该迭代器所指对象的写操作

　　· Forward Iterator 不仅支持Input Iterator和Output Iterator的操作，还能在序列中前向移动指向下一个元素

　　· Bidirectional Iterator 可以双向移动，既可指向序列中的下一个元素，也可以指向序列中的前一个元素

　　· Random Iterator 既可以双向移动，又可以跨越多个元素存取对象

2， 与迭代器操作相关的类型及其萃取机制

　　使用迭代器是为了获取被指向的对象和被指向的序列的信息。只要给出描述某个序列的迭代器，用户就可以通过迭代器间接去操作被指向的对象，并且可以确定序列中元素的个数。为了表述这种操作，STL必须能提供与迭代器有关的各种类型。

　　迭代器在元素操作的时候需要用到以下五种类型：

　　value_type: 代表迭代器所指对象的类型。

　　difference_type:代表两个迭代器之间的距离

　　reference_type:代表迭代器所指对象的引用类型。简言之，它是operator*()的返回类型

　　pointer_type:代表迭代器所致对象的指针类型。简言之，它是operator->()的返回类型

　　iterator_category:代表1中提出的五种迭代器的类型标识

3，迭代器的适配器

STL提供了许多基于迭代器的适配器，如back_insert_iterator, front_insert_iterator, inser_iterator, reverse_iterator, istream_iterator, ostream_iterator, istreambuf_iterator, ostreambuf_iterator等。

这些适配器大致可以分为三类：插入迭代器、反向迭代器和IO迭代器。

反向迭代器

　　　　顾名思义，反向迭代器会提供与普通迭代器相反方向的遍历功能。反向迭代器其实一个正向迭代器的适配器，它的实现都是通过调用正向迭代器的操作，为了与迭代器的概念保持一致（begin指向迭代器的第一个元素，end指向迭代器的最后一个元素的下一个位置），又与正向迭代器有一点点不同。

　　　　reverse_iterator的实现中有一个名为current的Iterator，它是模板参数，即正向迭代器。正向迭代器指向的范围是序列中的第一个元素到最后一个元素的下一个位置，为了保持迭代器概念的统一，反向迭代器的rbegin应该是序列的最后一个元素，rend应该是第一个元素前面的元素。

　　　　所以，current总是指向reverse_iterator所指元素之后的一个元素。这也意味这*返回的是值*(current-1)，++通过对current的--实现。下面贴上reverse_iterator的代码。　　

总结：迭代器将算法和数据结构有效地分离并粘合起来。实际上，STL中的很多容器都设计有自己专属的迭代器，因为只有它自己才能知道自身数据结构的布局及其遍历方法，只需要按照标准声明上面提到的五种迭代器要用到的数据类型即可。迭代器更多的是运用到算法中，有了泛型和迭代器的支持，算法可以达到很高的内聚性。

//list.h
#pragma once
#include<iostream>
#include<vector>
#include<list>
#include<assert.h>
#include"iterator.h"
using namespace std;
template<class T>
struct __ListNode
{
	T _data;
	__ListNode<T>* _prev;
	__ListNode<T>* _next;
	__ListNode(const T& x = T())
		:_prev(NULL)
		, _next(NULL)
		, _data(x)
	{}
};

template<class T,class Ref,class Ptr>
struct __ListIterator
{
	typedef __ListIterator<T, Ref, Ptr> Self;
	typedef BidirectionalIteratorTag IteratorCategory;
	typedef int DifferenceType;
	typedef T ValueType;
	typedef Ref Reference;
	typedef Ptr Pointer;

	__ListNode<T>* _node;
	__ListIterator()
	{}
	__ListIterator(__ListNode<T>* node)
		:_node(node)
	{}
	Reference operator*()
	{
		return _node->_data;
	}
	//当链表中存储结构体时，需要访问结构体成员变量
	Ptr& operator->()
	{
		//
		//return &(operator*());
		return &(_node->_data);
		//List<AA>::Iterator it=l.Begin();
		//cout<<it->_a<<endl;//编译器优化，按理说需要两个->->
	}
	bool operator==(const Self& s)
	{
		return _node == s._node;
	}
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	Self operator++(int)
	{
		Self tmp(*this);
		_node = _noode->_next;
		return tmp;
	}
	Self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}
	Self operator--(int)
	{
		Self tmp(*this);
		_node = _node->_prev;
		return tmp;
	}
	DifferenceType Size()
	{
		return Distance(Begin(), End());
	}
	Reference operator+=(DifferenceType n)
	{
		while (n--)
		{
			++*this;
		}
		return *this;
	}
	Self operator+(DifferenceType n)
	{
		Self tmp(*this);
		tmp += n;
		return tmp;
	}
	Reference operator-=(DifferenceType n)
	{
		while (n--)
		{
			--*this;
		}
		return *this;
	}
	Self operator-(DifferenceType n)
	{
		Self tmp(*this);
		tmp -= n;
		return tmp;
	}
};


template<class T>
class List
{
	typedef __ListNode<T> Node;
	Node* _head;
public:
	typedef __ListIterator<T, T&, T*> Iterator;
	typedef __ListIterator<T,const T&,const T*> ConstIterator;
	typedef ReverseIterator<ConstIterator> ConstReverseIterator;
	typedef ReverseIterator<Iterator> ReverseIterator;
	typedef T ValueType;
	typedef T* Pointer;
	typedef const T* ConstPointer;
	typedef ValueType& Reference;
	typedef const ValueType& ConstReference;
	typedef int DifferenceType;
	
	List()
		:_head(new Node)
	{
		_head->_next = _head;
		_head->_prev = _head;
	}
	~List()
	{
		if (_head == NULL)
			return;
		while (1)
		{
			if (_head == NULL)
				break;
			else if (_head->_next = _head)
			{
				delete _head;
				_head = NULL;
			}
			else
			{
				Node* del = _head;
				_head = _head->_next;
				_head->_prev = NULL;
				delete del;
			}
		}
	}
	/*void PushBack(const T& x)
	{
		Node* tail = _head->_prev;
		Node* tmp = new Node(x);
		tmp->_next = _head;
		_head->_prev = tmp;
		tail->_next = tmp;
		tmp->_prev = tail;
	}*/
	void PushBack(const T& x)
	{
		Insert(End(), x);
	}
	void PushFront(const T&x)
	{
		Insert(Begin(), x);
	}
	void PopBack()
	{
		Erase(--End());
	}
	void PopFront()
	{
		Erase(Begin());
	}
	void Insert(Iterator pos, const T& x)
	{
		Node* cur = pos._node;
		Node* prev = cur->_prev;
		Node* tmp = new Node(x);

		tmp->_next = cur;
		cur->_prev = tmp;

		prev->_next = tmp;
		tmp->_prev = prev;
	}
	Iterator Erase(Iterator pos)
	{
		assert(pos!=End());
		Node* prev = pos._node->_prev;
		Node* next = pos._node->_next;

		Node* del = pos._node;
		prev->_next = next;
		next->_prev = prev;
		delete del;
		return Iterator(next);
	}
	Iterator Begin()
	{
		return Iterator(_head->_next);
	}
	Iterator End()
	{
		return _head;//explicit
		//return Iterator(_head);
	}
	ReverseIterator RBegin()
	{
		return ReverseIterator(End());
	}
	ReverseIterator REnd()
	{
		return ReverseIterator(Begin());
	}
	ConstReverseIterator RBegin()const
	{
		return ConstReverseIterator(End());//explicit
	}
	ConstReverseIterator REnd()const
	{
		return ConstReverseIterator(Begin());//explicit
	
	}
};
void TestSList()
{
	List<int> l;
	l.PushBack(1);
	l.PushBack(2);
	l.PushBack(3);
	l.PushBack(4);
	l.PushBack(5);

	List<int>::Iterator iter = l.Begin();
	while (iter != l.End())
	{
		cout << *iter << " ";
		++iter;
	}
	cout << endl;

	iter = l.Begin();
	while (iter != l.End())
	{
		List<int>::Iterator tmp = iter;
		++tmp;
		if (*iter % 2 == 0)
		{
			l.Erase(iter);
		}
		iter = tmp;
		/*if (*iter % 2 == 0)
		{
			iter = l.Erase(iter);
		}
		else
			++iter;*/
	}

	List<int>::ReverseIterator it = l.RBegin();
	
	while (it != l.REnd())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	cout << Distance(l.Begin(), l.End())<<endl;
}
//vector.h
#pragma once
#include<iostream>
#include<vector>
#include<list>
#include<assert.h>
#include"iterator.h"
using namespace std;
template<class T>
class Vector
{
public:
	typedef T* Iterator;
	typedef const T* ConstIterator;
	typedef ReverseIterator<ConstIterator> ConstReverseIterator;
	typedef ReverseIterator<Iterator> ReverseIterator;
	typedef T ValueType;
	typedef T* Pointer;
	typedef T& Reference;
	typedef int DifferenceType;
protected:

	Iterator _start;
	Iterator _finish;
	Iterator _storage;
	void _CheckCapacity()
	{
		if (_finish == _storage)
		{
			int capacity = _storage - _start;
			int newCapacity = capacity * 2 + 3;
			T* tmp = new T[newCapacity];
			for (int i = 0; i < capacity;++i)
			{
				//operator=
				tmp[i] = _start[i];//不能用memcpy，涉及指针拷贝
			}
			delete[] _start;
			_start = tmp;
			_finish = _start + capacity;
			_storage = _start + newCapacity;
		}
	}
public:
	Vector()
		:_start(NULL)
		,_finish(NULL)
		, _storage(NULL)
	{}
	Vector(size_t size)
		:_start(new T[size])
		,_finish(_start)
		, _storage(_start+size)
	{}
	~Vector()
	{
		if (_start)
			delete[] _start;
	}
	void PushBack(const T& x)
	{
		_CheckCapacity();
		*_finish = x;
		++_finish;
	}
	void PopBack()
	{
		assert(_finish > _start);
		--_finish;
	}
	Iterator Begin()
	{
		return _start;
	}
	Iterator End()
	{
		return _finish;
	}
	ReverseIterator RBegin()
	{
		return ReverseIterator(End());
	}
	ReverseIterator REnd()
	{
		return ReverseIterator(Begin());
	}
	DifferenceType Size()
	{
		return _finish - _start;
	}
	DifferenceType Capacity()
	{
		return _storage - _start;
	}
	Reference operator[](int index)
	{
		assert(index < Size());
		return _start[index];
	}
	ValueType at(int index)
	{
		assert(index < Size());
		return _start[index];
	}
};
void TestVector()
{
	Vector<int> v;
	v.PushBack(1);
	v.PushBack(2);
	v.PushBack(3);
	v.PushBack(4);
	v.PushBack(5);

	Vector<int>::Iterator it = v.Begin();
	while (it != v.End())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	Vector<int>::ReverseIterator rit = v.RBegin();
	while (rit != v.REnd())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;
	cout << Distance(v.Begin(), v.End()) << endl;
}
//iterator.h
#pragma once
#include<iostream>
using namespace std;
struct InputIteratorTag {};
struct OutputIteratorTag {};
struct ForwardIteratorTag : public InputIteratorTag{};
struct BidirectionalIteratorTag : public ForwardIteratorTag {};
struct RandomAccessIteratorTag : public BidirectionalIteratorTag {};


template<class Iterator>
struct IteratorTraits
{
	typedef typename Iterator::IteratorCategory IteratorCategory;
	typedef typename Iterator::ValueType        ValueType;
	typedef typename Iterator::DifferenceType   DifferenceType;
	typedef typename Iterator::Pointer           Pointer;
	typedef typename Iterator::Reference         Reference;

};
template<class T>
struct IteratorTraits<T*>
{
	typedef typename RandomAccessIteratorTag IteratorCategory;
	typedef typename T        ValueType;
	typedef typename int   DifferenceType;
	typedef typename T*           Pointer;
	typedef typename T&         Reference;
};
template<class T>
struct IteratorTraits<const T*>
{
	typedef typename RandomAccessIteratorTag IteratorCategory;
	typedef typename T        ValueType;
	typedef typename int   DifferenceType;
	typedef typename T*           Pointer;
	typedef typename T&         Reference;
};
template <class InputIterator>
int  __Distance(InputIterator first, InputIterator last, InputIteratorTag)
{
	int n = 0;
	while (first != last) {
		++first; ++n;
	}
	return n;
}
template <class RandomAccessIterator>
int __Distance(RandomAccessIterator first, RandomAccessIterator last,
	RandomAccessIteratorTag)
{
	return last - first;
}
template <class InputIterator>
int  Distance(InputIterator first, InputIterator last)
{
	return __Distance(first, last, IteratorTraits <InputIterator>::IteratorCategory());
}

template <class Iterator>
class ReverseIterator
{
protected:
	Iterator _cur;
	typedef ReverseIterator<Iterator> Self;
	typedef typename IteratorTraits<Iterator>::IteratorCategory	IteratorCategory;
	typedef typename IteratorTraits<Iterator>::DifferenceType DifferenceType;
	typedef typename IteratorTraits<Iterator>::ValueType  ValueType;
	typedef typename IteratorTraits<Iterator>::Pointer  Pointer;
	typedef typename IteratorTraits<Iterator>::Reference  Reference;
	

public:
	ReverseIterator()
	{}
	explicit ReverseIterator(Iterator i)
		:_cur(i)
	{}
	Reference operator*()
	{
		Iterator tmp = _cur;
		return *(--tmp);
	}
	//当链表中存储结构体时，需要访问结构体成员变量
	Pointer& operator->()
	{
		//
		//return &(operator*());
		return _cur.operator->();
		//List<AA>::Iterator it=l.Begin();
		//cout<<it->_a<<endl;//编译器优化，按理说需要两个->->
	}
	bool operator==(const Self& s)
	{
		return _cur == s._cur;
	}
	bool operator!=(const Self& s)
	{
		return _cur != s._cur;
	}
	Self& operator++()
	{
		--_cur;
		return *this;
	}
	Self operator++(int)
	{
		Self tmp(*this);
		--_cur;
		return tmp;
	}
	Self& operator--()
	{
		++_cur;
		return *this;
	}
	Self operator--(int)
	{
		Self tmp(*this);
		++_cur;
		return tmp;
	}
	Self& operator+=(int n)
	{
		_cur += n;
		return *this;
	}
	Self& operator-=(int n)
	{
		_cur -= n;
		return *this;
	}
	Self operator+(int n)
	{
		return Self(*this+n);
	}
	Self operator-(int n)
	{
		return Self(*this-n);
	}
	Reference operator[](DifferenceType n) const 
	{
		return *(*this + n);
	}
	//Iterator需实现operator+(n);
};
//main.cpp
#include"list.h"
#include"vector.h"
int main()
{
	TestSList();
	TestVector();
	system("pause");
	return 0;
}

本文出自 “小止” 博客，请务必保留此出处http://10541556.blog.51cto.com/10531556/1831592

vector与list和各自iterator剖析2

原文：http://10541556.blog.51cto.com/10531556/1831592