【C++】模拟实现list

list<int> lage;      //存放学生年龄
list<string> lname;  //存放学生姓名
list<double> lhigh;  //存放学生身高
list<Student> lstu;  //存放自定义学生类

namespace mfc 
{
	template<class T>//链表结点类模板

    //struct定义结点就直接是公有的,如果用class就要将其设为public
	struct list_node 
	{
        //成员变量
		list_node<T>* _next;
		list_node<T>* _prev;
		T _val;

        //构造函数
		list_node(const T& val = T()){}
	};


	template<class T,class Ref,class Ptr>//链表迭代器类模板
	struct __list_iterator
	{
        //成员变量
		typedef list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> self;
		Node* _node;

        //构造函数
		__list_iterator(Node* node){}

		//操作符重载函数
		Ref operator*(){}
		Ptr operator->(){}
		
		self& operator++(){}
		self operator++(int){}
		self& operator--(){}
		self operator--(int){}

		bool operator!=(const self& it) const{}
		bool operator==(const self& it) const{}
	};


	template<class T>//链表类模板
	class list
	{
		typedef list_node<T> Node;

        //成员变量
    private:
		Node* _head;

        //成员函数
	public:
		typedef __list_iterator<T,T&,T*> iterator;
		typedef __list_iterator<T,const T&,const T*> const_iterator;
		
        //迭代器相关函数
		iterator begin(){}
		iterator end(){}
		const_iterator begin() const{}
		const_iterator end() const{}

        //默认成员函数
		void empty_init(){}
		list(){}
		list(const list<T>& lt){}
		void swap(list<T>& lt){}
		list<T>& operator=(list<T> lt){}
		~list(){}

        //成员函数
		void clear(){}
		void push_front(const T& x){}
		void pop_front(){}
		void push_back(const T& x){}
		void pop_back(){}
		iterator insert(iterator pos, const T& x){}
		iterator erase(iterator pos){}
		size_t size(){}
	};
}

prev->_next = newnode; //相当于在list_node外部直接通过类指针访问了类成员变量_next

template<class T>//链表结点类模板

struct list_node 
{
	list_node<T>* _next;
	list_node<T>* _prev;
	T _val;
};

//缺省值的作用是在无参调用时直接去调用模板实例化的类的无参构造函数
//这里一定不能将缺省值给0/nullptr!因为你不知道模板实例化的类具体到底是内置类型还是自定义类型
list_node(const T& val = T())
	:_next(nullptr)
	,_prev(nullptr)
	,_val(val)
{}

struct __list_iterator
{
    typedef list_node<T> Node;
    //这里typedef是为了防止我们把成员类型写成list_node*
    //对于类模板来说,类名不是类型,类名实例化出的类才是类型
    //即 list_node 不是类的类型 而 list_node<int> 才是类的类型

    Node* _node;
};

__list_iterator(Node* node)
	:_node(node)
{}

//const迭代器的设计让这里的返回值又套了一个模板参数Ref
//在这里不理解没关系,我们最后实现const迭代器时会详细讲
//在这里可以先认为根据模板的实例化不同 Ref = T& / const T&

Ref operator*()
{
	return _node->_val;
}

//因为我们把__list_iterator也写成类模板了,而返回值必须写的是类模板实例化的类型
//即__list_iterator<T, Ref, Ptr>
//为了方便,我们不妨typedef一下这个为self 方便后续用


//++前置
self& operator++()
{
	//更新一下*this的_node指针,然后再返回*this
	_node = _node->_next;
	return *this;
}

//后置++
self operator++(int)
{
	self tmp(*this);

	//更新一下*this的_node指针,然后再返回*this当前的值
	_node = _node->_next;

	return tmp;
}

//--前置
self& operator--()
{
	//更新一下*this的_node指针,然后再返回*this
	_node = _node->_prev;

	return *this;
}

//后置--
self operator--(int)
{
	self tmp(*this);

	//更新一下*this的_node指针,然后再返回*this
	_node = _node->_prev;

	return tmp;
}

bool operator!=(const self& it) const
{
	return _node != it._node;
}

bool operator==(const self& it) const
{
	return _node == it._node;
}

it->x ;
(*it).x ;

//const迭代器的设计让这里的返回值又套了一个模板参数Ptr
//在这里不理解没关系,我们最后实现const迭代器时会详细讲
//在这里可以先认为根据模板的实例化不同 Ptr = T* / const T*

Ptr operator->()
{
	return &_node->_val;
}

const T& operator*()
{
	return _node->_val;
}

const T* operator->()
{
	return &_node->_val;
}

//迭代器的本质是通过自定义类型的封装,改变了类型的行为
//内置类型的行为不符合我们的要求时,C++就可以用一个类来封装这个类型,然后自己定义这个类型的行为
//这里的思路是,我们本身就想用结点的指针来做list的迭代器,但是因为list的结构原因
//它的++ / -- / * / != 等操作得到的结果不是我们想要的
//所以我们就把这个结点指针封装起来,重新定义它的++ / -- / * / != 等操作
//使这些操作得到的结果是我们想要的

template<class T,class Ref,class Ptr>
struct __list_iterator
{
	typedef list_node<T> Node;
	typedef __list_iterator<T, Ref, Ptr> self;

    //成员变量
	Node* _node;

    //成员函数
	__list_iterator(Node* node)
		:_node(node)
	{}

	Ref operator*()
	{
		return _node->_val;
	}

	Ptr operator->()
	{
		return &_node->_val;
	}

	//++前置
	self& operator++()
	{
		//更新一下*this的_node指针,然后再返回*this
		_node = _node->_next;
		return *this;
	}

	//后置++
	self operator++(int)
	{
		self tmp(*this);
		//更新一下*this的_node指针,然后再返回*this
		_node = _node->_next;
		return tmp;
	}

	//--前置
	self& operator--()
	{
		//更新一下*this的_node指针,然后再返回*this
		_node = _node->_prev;
		return *this;
	}

	//后置--
	self operator--(int)
	{
		self tmp(*this);
		//更新一下*this的_node指针,然后再返回*this
		_node = _node->_prev;
		return tmp;
	}	

	bool operator!=(const self& it) const
	{
		return _node != it._node;
	}

	bool operator==(const self& it) const
	{
		return _node == it._node;
	}
};

template<class T>
class list
{
	typedef list_node<T> Node;
public:
    /*
	因为iterator和const_iterator只有operator*和operator->的返回值不同
	所以我们不如把operator*和operator->的返回值也设置成模板参数,
	当是iterator的时候,返回值模板就是T&/T*
    当是const_iterator的时候,返回值模板就是const T&/const T*
	本质上iterator和const_iterator还是两个类,但是用模板可以简化一些
    */

	typedef __list_iterator<T,T&,T*> iterator;
	typedef __list_iterator<T,const T&,const T*> const_iterator;

private:
    Node* _head;
};    

void empty_init()
{
	_head = new Node;
	_head->_prev = _head;
	_head->_next = _head;
}

list()
{
	empty_init();
}

list(const list<T>& lt)
{
	empty_init();

	for (auto& e : lt)
	{
		push_back(e);
	}
}

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

list<T>& operator=(list<T> lt)
{
	swap(lt);
	return *this;
}

void clear()
{
	iterator it = begin();
	while (it != end())
	{
		it = erase(it);
	}
}

~list()
{
	clear();

	delete _head;
	_head = nullptr;
}

iterator begin()
{
	//return _head->_next;
	//上下两种方式都可以
	return (iterator)_head->_next;
}

const_iterator begin() const
{
	return (const_iterator)_head->_next;
}

iterator end()
{
	return (iterator)_head;
}

const_iterator end() const
{
	return (const_iterator)_head;
}

//pos位置之前插入
iterator insert(iterator pos, const T& x)
{
	//纪录下pos位置和pos的上一个位置
	Node* cur = pos._node;
	Node* prev = cur->_prev;

	//创建新结点
	Node* newnode = new Node(x);

	//将pos的上一个结点和新结点相互链接
	prev->_next = newnode;
	newnode->_prev = prev;

	//将新结点和pos结点相互链接
	cur->_prev = newnode;
	newnode->_next = cur;

	//返回新插入的结点的迭代器
	return newnode;
}

//删除pos位置的结点
iterator erase(iterator pos)
{
	//不能删哨兵位的头结点
	assert(pos != end());

	//纪录下pos位置, pos的上一个位置和下一个位置
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;

	//将pos的上一个位置和下一个位置相互链接
	prev->_next = next;
	next->_prev = prev;

	//删除pos位置结点
	delete cur;

	//返回pos位置的下一个结点的迭代器
	return next;
}

void push_front(const T& x)
{
	insert(begin(), x);
}

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

void push_back(const T& x)
{
	insert(end(), x);
}

void pop_back()
{
	erase(--end());
}

size_t size()
{
	size_t sz = 0;
    
    //通过迭代器遍历链表
	iterator it = begin();
	while (it != end())
	{
		++sz;
		++it;
	}

	return sz;
}

//仅测试list功能用
#include"STL_List.h"

int main()
{
	mfc::test_list1();
	mfc::test_list2();

	return 0;
}

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;

namespace mfc 
{
	template<class T>
	//链表的链和结点分装成两个类
	struct list_node //struct定义结点就直接是公有的,如果用class就要将其设为public
	{
		list_node<T>* _next;
		list_node<T>* _prev;
		T _val;

		list_node(const T& val = T())
			:_next(nullptr)
			,_prev(nullptr)
			,_val(val)
		{}
	};

	template<class T,class Ref,class Ptr>
	//迭代器的本质是通过自定义类型的封装,改变了类型的行为

	//内置类型的行为不符合我们的要求时,C++就可以用一个类来封装这个类型,然后自己定义这个类型的行为
	//这里的思路是,我们本身就想用结点的指针来做list的迭代器,但是因为list的结构原因
	//它的++ / -- / * / != 等操作得到的结果不是我们想要的
	//所以我们就把这个结点指针封装起来,重新定义它的++ / -- / * / != 等操作
	//使这些操作得到的结果是我们想要的
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> self;
		Node* _node;

		__list_iterator(Node* node)
			:_node(node)
		{}

		//const迭代器的设计
		Ref operator*()
		{
			return _node->_val;
		}

		Ptr operator->()
		{
			return &_node->_val;
		}


		//++前置
		self& operator++()
		{
			//更新一下*this的_node指针,然后再返回*this
			_node = _node->_next;
			return *this;
		}

		//后置++
		self operator++(int)
		{
			self tmp(*this);
			//更新一下*this的_node指针,然后再返回*this
			_node = _node->_next;
			return tmp;
		}


		//--前置
		self& operator--()
		{
			//更新一下*this的_node指针,然后再返回*this
			_node = _node->_prev;
			return *this;
		}

		//后置--
		self operator--(int)
		{
			self tmp(*this);
			//更新一下*this的_node指针,然后再返回*this
			_node = _node->_prev;
			return tmp;
		}	


		bool operator!=(const self& it) const
		{
			return _node != it._node;
		}

		bool operator==(const self& it) const
		{
			return _node == it._node;
		}

	};



	template<class T>
	class list
	{
		typedef list_node<T> Node;
	public:
		//因为iterator和const_iterator只有operator*和operator->的返回值不同
		//所以我们不如把operator*和operator->的返回值也设置成模板参数,
		//当是iterator的时候,返回值模板就是T&/T*
		//当是const_iterator的时候,返回值模板就是const T&/const T*
		//本质上iterator和const_iterator还是两个类,但是用模板可以简化一些
		typedef __list_iterator<T,T&,T*> iterator;
		typedef __list_iterator<T,const T&,const T*> const_iterator;
		
		iterator begin()
		{
			//因为迭代器的底层实现是Node*,所以这里直接返回Node*没问题
			//单参数的构造函数支持隐式类型转换
			//return _head->_next;
			//所以上下两种方式都可以
			return (iterator)_head->_next;
		}

		iterator end()
		{
			return (iterator)_head;
		}

		const_iterator begin() const
		{
			return (const_iterator)_head->_next;
		}

		const_iterator end() const
		{
			return (const_iterator)_head;
		}

		void empty_init()
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
		}


		list()
		{
			empty_init();
		}

		list(const list<T>& lt)
		{
			empty_init();

			for (auto& e : lt)
			{
				push_back(e);
			}
		}

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

		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}

		~list()
		{
			clear();

			delete _head;
			_head = nullptr;
		}

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}


		void push_front(const T& x)
		{
			insert(begin(), x);
		}
		void pop_front()
		{
			erase(begin());
		}

		void push_back(const T& x)
		{
			/*
			//找尾
			Node* tail = _head->_prev;
			Node* newnode = new Node(x);
			
			//链接
			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;
			*/
			insert(end(), x);
		}

		void pop_back()
		{
			erase(--end());
		}

		//pos位置之前插入
		iterator insert(iterator pos, const T& x)
		{
			//纪录下pos位置和pos的上一个位置
			Node* cur = pos._node;
			Node* prev = cur->_prev;

			//创建新结点
			Node* newnode = new Node(x);

			//将pos的上一个结点和新结点相互链接
			prev->_next = newnode;
			newnode->_prev = prev;

			//将新结点和pos结点相互链接
			cur->_prev = newnode;
			newnode->_next = cur;

			//返回新插入的结点的迭代器
			return newnode;
		}

		//删除pos位置的结点
		iterator erase(iterator pos)
		{
			//不能删哨兵位的头结点
			assert(pos != end());

			//纪录下pos位置, pos的上一个位置和下一个位置
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

			//将pos的上一个位置和下一个位置相互链接
			prev->_next = next;
			next->_prev = prev;

			//删除pos位置结点
			delete cur;

			//返回pos位置的下一个结点的迭代器
			return next;
		}

		//size求法1:写函数
		//方法2:加一个成员变量_size.然后insert就++,erase就--,初始化记得附0
		size_t size()
		{
			size_t sz = 0;
			iterator it = begin();
			while (it != end())
			{
				++sz;
				++it;
			}
			return sz;
		}


	private:
		//写成list_node* _head;是错误的
		//因为有了类模板后,类名就不是类型了,只有类模板显示实例化出的类才是类型
		Node* _head;
	};

	//迭代器测试打印函数
	void Print(const list<int>& lt)
	{
		list<int>::const_iterator it = lt.begin();

		while (it != lt.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}
	
	//测试函数1
	void test_list1()
	{
		list<int> lt;

		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);

		list<int>::iterator it = lt.begin();//这个地方把begin()赋给it是拷贝构造
		//而iterator没有实现拷贝构造,则默认就是浅拷贝
		//没有出错的原因就是,这里本身就是应该浅拷贝
		//我把begin()赋值给it,本身就是希望it指向这个结点,而不是指向这个结点的拷贝
		//那么,多个指针指向一个结点没有崩溃的原因是,我们没有进行二次释放操作
		//一般来讲,指针的销毁都伴随着空间的销毁,但是迭代器并没有销毁链表结点的权力
		//所以我们不写迭代器的析构函数,迭代器的销毁不导致结点的释放,所以不会有二次释放的问题
		while (it != lt.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		Print(lt);
	}

	//测试函数2
	void test_list2()
	{
		class Point {
		public:
			int x;
			int y;
			Point(int xCoord = 0, int yCoord = 0)
				: x(xCoord)
				, y(yCoord)
			{}
		};

		list<Point> lt;
		lt.push_back(Point(1, 1));
		lt.push_back(Point(2, 2));
		lt.push_back(Point(3, 3));
		lt.push_back(Point(4, 4));
		list<Point>::iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << it->x << "," << it->y << endl;
			cout << (*it).x << "," << (*it).y << endl;
			cout << endl;
			++it;
		}

	}
}