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;
}