泛型编程学习，编写一个类似STL库中的简易list的迭代器（iterator）

前言

近期在研究stl源代码及stl里各种实现的细节，初学入门免不了模仿，以下便写一次自己的简单的list容器的迭代器。
首先，在开始编写List的迭代器的时候我们首先应该了解我们要写的List和其迭代器要做出什么样的功能。（学习书籍《C++STL基础应用》《STL源代码剖析》《泛型思维》）

---

list

list相较于vector，list的好处是每次插入/删除一个数据，他就重新申请/释放一个空间，对内存的把握绝对的精准（vector是申请一片区域，超过此容量便进行“重新配置两倍区域，元素移动，释放原空间”）；另外 对于元素的移动，list永远是常数的时间。

迭代器

每一个容器都应有对应的迭代器（iterator），容器通过迭代器共享某一具体算法（之后使用display()函数举例）。迭代器是算法和容器之间起媒介作用（display(iterator it1,iterator it2)），迭代器思维的产生是编制泛型算法发展的必然结果。

简单的display()函数

template<class T>
void display(T start, T end) {
	cout << endl;
	for (T i = start; i != end; i++) {
		cout << *i << endl;
	}
	cout << endl;
}

我的目的就是为了使我编写的list容器可以使用此display()函数。

---

编写

list

我们想要的基础的list需要：基本的结点struct Node（含*head 和 *prev分别指向下一位和前一位结点）

//	  head->Node1->Node2->......Noden->tail
//	  next ->  next  ->  next  ->......  next  ->tail->NULL
//NULL<-  prev<-  prev  <- prev   <-...... prev  
template<class T>
	struct  Node
	{
		Node* next;
		Node* prev;
		T data;
		Node(T s = 0, Node* n = NULL, Node* p = NULL) :data(s), next(n), prev(p) {};
		//Node的构造函数
	};

确定好了Node开始编写class list

template<class T>
class list {
public:
	struct  Node
	{
		//......
	};
	//iterator
	class iterator 
	{
		//......
	};
	//_list的迭代器
private:
	Node * head,*tail;         //我们编写的list含首、尾指针
	int _size;
	void createlist() {
		_size = 0;
		head = new Node();
		tail = new Node();
		head->next = tail;
		tail->prev = head;
	}
public:
	list() {
		createlist();
	}
	~list() {
		while (!empty()) {
			pop_front();
		}
		delete head;
		delete tail;
	}
	bool empty()const { return _size == 0; };
	iterator begin() {
		return iterator(head->next);
	}
	iterator end() {
		return iterator(tail);
	}
	iterator insert(iterator pos, const T& value) {  
	//const T& value ：const 防止引用引用被修改，引用传递相当于传递指针，8字节 
	//而值传递会调用复制构造函数，占用内存大
		Node* p = new Node(value, pos.cur, pos.cur->prev);
		_size++;
		p->prev->next = p;
		pos.cur->prev = p;
		return iterator(p);
		// 大佬的写法
		//return iterator(p->prev = p->prev->next = new Node(val, p, p->prev));
	}
	iterator erase(iterator pos) {
		Node* p = pos.cur;
		iterator newite(p->next);
		p->prev->next = p->next;
		p->next->prev = p->prev;
		delete p;
		_size--;
		return newite;
	}
	void push_back(const T& value) {
		insert(end(), value);
	}
	void push_front(const T& value) {
		insert(begin(), value);
	}
	void pop_front() {
		erase(begin());
	}
	void pop_back() {
		erase(end());
	}
};

这样，我们的list就含有基础的push_back,push_front,pop_back,pop_front,insert,erase功能，和构造、析构函数了。

list 的iterator的编写

template<class T>
class list {
public:
	struct  Node
	{
		//......Node的实现内容
	};
	//iterator
	class iterator {
	private:
		Node* cur; //指针，指向link的结点
	public:
		friend class list;   
		//重要！将list声明为iterator的友元，iterator才可访问list的private
		explicit iterator(Node* p=0) {cur = p; } 
		//阻止不应该允许的经过转换构造函数进行的隐式转换的发生。
		//声明为explicit的构造函数不能在隐式转换中使用
		bool operator ==(iterator& x) { return (*this).cur == x.cur; }
		bool operator !=(iterator& x) { return (*this).cur != x.cur; }
		iterator& operator++() {  //前缀++
			cur = cur->next;
			return *this;
		}
		iterator operator++(int) { //后缀++
			iterator temp = *this;
			++(*this);
			return temp;
		}
		iterator& operator--() {
			cur = cur->prev;
			return *this;
		}
		iterator operator--(int) {
			iterator temp = *this;
			--(*this);
			return temp;
		}
		Node* operator->() {
			return cur;
		}
		T operator*() { return cur->data; }
		//如果不写这一个，我们可以使用编写重载全局
		//ostream operator<<(ostream& os,const iterator& it)
		//来实现display()中的“cout<<*iterator;”
	};
	//_list的迭代器
	//......
	//list的实现内容
};

因为display()函数中使用了++，！=，->,因此需要写迭代器的符号重载。

T operator*() { return cur->data; }

如果不写这一个，我们可以使用编写重载全局

ostream operator<<(ostream& os,const iterator& it){ //实现细节 }

来实现display()中的“

cout<<*iterator;

---

main()函数及运行结果

#include"_list.h"
#include<iostream>
using namespace std;
int main() {
	list<int>a;
	for (int i = 0; i < 5; i++) {
		a.push_back(i);
	}
	list<int>::iterator itb = a.begin();
	list<int>::iterator ite = a.end();
	display(itb, ite); // 0 1 2 3 4

	a.insert(ite, 5);
	display(itb, ite); //0 1 2 3 4 5 

	cout << *itb<<endl; // 0
	cout<<*(++itb)<<endl;//1
	cout << *(--ite) << endl<<endl;//5

	a.pop_back();
	display(a.begin(), a.end());// 0 1 2 3 4

	
	system("pause");
	return 0;
}

至此简历list及其迭代器就编写完了。
STL中list容器类的clear,remove,unique,splice,merge,reverse,sort等元素操作留着之后实现。
github个人博客