C++list的模拟实现

template<class T>
//struct也能定义类，默认类的访问限定符是 public
struct list_node
{
	//这个指针指向前一个节点
	list_node<T>* _prev;
	//这个指针指向后一个节点
	list_node<T>* _next;
	//这个是数据域中的元素
	T _data;
	
	//对节点使用匿名对象进行初始化
	list_node(const T& data = T())
		:_prev(nullptr)
		,_next(nullptr)
		,_data(data)
	{}
};

//这里后面的两个参数，在实际应用时通常是T& , T* 或者是 const T& , const T*
//根据加与不加const 可以分别实例化出：普通正向迭代器与正向const迭代器
template<class T, class Ref, class Ptr>
struct __list_iterator
{
	//将节点的类型进行typedef方便使用
	typedef list_node<T> node;
	
	//将类自己进行typedef方便使用
	typedef __list_iterator<T,Ref,Ptr> self;

	//成员变量 是一个指向节点的指针
	node* _pnode;

	//构造函数 用一个节点的地址对迭代器进行初始化，
	 __list_iterator(node* pnode)
		:_pnode(pnode)
	{}
};

template<class T>
class list
{
public:
	//将节点的类型进行typedef方便使用
	typedef list_node<T> node;
	//将迭代器进行typedef方便使用
	typedef __list_iterator<T, T&, T*> iterator;
	//将const迭代器进行typedef方便使用
	typedef __list_iterator<T, const T&, const T*> const_iterator;
	//默认构造函数
	list()
	{
		empty_init();
	}
	//初始化函数
	void empty_init()
	{
		//申请一个头节点，将节点的地址给_head
		_head = new node;
		//让哨兵位节点的 前指针指向自己
		_head->_prev = _head;
		//让哨兵位节点的 后指针指向自己
		_head->_next = _head;
	}
private:
	//指向哨兵位节点的指针
	node* _head;
};

// *运算符重载
Ref operator*()
{
	//迭代器中的那个指针不能是nullptr
	assert(_pnode);
	//返回节点中的数据域中的数据
	return _pnode->_data;
}

//前置++运算符
self& operator++()
{
	_pnode = _pnode->_next;
	return (*this);
}

//后置++运算符
self operator++(int)
{
	//先保存++之前的结果
	self tmp(*this);
	_pnode = _pnode->_next;
	//返回++之前的值
	return tmp;
}

//前置--运算符
self& operator--()
{
	_pnode = _pnode->_prev;
	return (*this);
}

//后置--运算符
self operator--(int)
{
	self tmp(*this);
	_pnode = _pnode->_prev;
	return tmp;
}

struct Date
{
	int _year;
	int _month;
	int _day;
}
//it是迭代器，指向了存储了Date类型的节点
//假设:在没有->操作符时,我们想要修改_year的值,
(*it)._year = 2023;
//如果有了-> 操作符，我们就能这样操作，更加符合我们的使用习惯
it->_year = 2023;

// ->运算符重载
Ptr operator->()
{
	return &(_pnode->_data);
}

it->->_year = 2023; 
//it-> 等价于 (&(_pnode->date)) 

//(&(_pnode->date))->year = 2023;

// !=运算符重载
bool operator!=(const self& s)
{
	return _pnode != s._pnode;
}

// ==运算符重载
bool operator==(const self& s)
{
	return _pnode == s._pnode;
}

//正向迭代器
iterator begin()
{
	//_head指向的是哨兵位的头节点，_head的下一个才是第一个节点！
	//这里使用的是一个指针构造的匿名对象做返回值，编译器会对此进行优化，能够增加效率
	return iterator(_head->_next);
}

iterator end()
{
	//由于是双向循环链表，所以最后一个节点的下一个位置就是哨兵位节点
	return iterator(_head);
}

//const迭代器的思路与普通迭代器类似
const_iterator begin() const
{
	return const_iterator(_head->_next);
}
const_iterator end() const 
{
	return const_iterator(_head);
}

void insert(iterator pos, const T& x)
{
	//先申请一个节点，存储我们要插入的数据
	node* new_node = new node(x);
	node* prev = pos._pnode->_prev;
	//链接过程
	prev->_next = new_node;
	new_node->_prev = prev;
	new_node->_next = pos._pnode;
	pos._pnode->_prev = new_node;
}

void push_front(const T& x)
{
	//在begin()位置进行插入就是头插！
	insert(begin(), x);
}

//尾插函数
void push_back(const T& x)
{
	//在end()位置进行插入，就是尾插
	insert(end(), x);
}

iterator erase(iterator pos)
{
	assert(pos != end());
	//链接过程
	node* prev = pos._pnode->_prev;
	node* next = pos._pnode->_next;
	prev->_next = next;
	next->_prev = prev;
	
	//删除节点
	delete pos._pnode;
	//返回指向原节点的下一个节点的迭代器，外部接收后可以防止迭代器失效！
	return iterator(next);
}

void pop_front()
{
	erase(begin());
}

void pop_back()
{
	//由于end()是最后一个节点的下一个位置，所以这里要对end()进行一次自减运算
	erase(--end());
}

void clear()
{
	list<T>::iterator it = begin();
	while (it != end())
	{
		//erase函数删除相应节点以后会返回下一个节点的迭代器
		it = erase(it);
	}
}

//swap函数
void swap(list<T>& lt)
{
	std::swap(_head, lt._head);
}

//迭代器区间构造,传入的迭代器应该至少是一个二元迭代器，能支持向前和向后遍历，这时链表的最低要求。
template<class Biditerator>
list(Biditerator first, Biditerator last)
{
	//调用初始化函数
	empty_init();
	//遍历迭代器同时将数据形成一个新节点插入链表中
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

//拷贝构造
list(const list<T>& lt)
{
	//初始化
	empty_init();
	//用迭代器区间构造创建一个新的list对象
	list<T> tmp(lt.begin(), lt.end());
	//将this指针指向的对象与这个新的tmp对象进行交换，拷贝就变相完成了
	swap(tmp);
}

//赋值运算符重载
//注意这里的传参方式是传值传参
list<T>& operator=(list<T> lt)
{
	//将this指针指向的对象与这个lt对象进行交换，赋值就变相完成了
	swap(lt);
	return (*this);
}

~list()
{
	clear();
	delete _head;
	_head = nullptr;
}