list的模拟实现

1.默认成员函数模拟实现

1.1 构造函数（头节点）

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

1.2 析构函数

~list()
{
	clear();
	delete _head;
	_head = nullptr;
}
void clear()
{
	//清理数据,不清头节点
	iterator it = begin();
	while (it != end())
	{
		it = erase(it);//it就是下一个位置
	}
}

1.3 拷贝构造函数

先搞头节点

void empty_init()
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;
}
//lt2(lt1)   lt2拷贝构造lt1,this就是lt2
list(const list<T>& lt)
{
	empty_init();
	for (auto e : lt)
	{
		push_back(e); 
	}
}

1.4 赋值重载函数

void swap(list<T>& lt)
{
	std::swap(_head, lt._head);//交换头指针
	std::swap(_size, lt._size);//交换_size
}
//lt3=lt1  lt就是lt1的拷贝构造  赋值重载
list<int>& operator=(const list<int>& lt)
{
	//现代写法
	swap(lt);
	return *this;
}

2.增删查改模拟实现

2.1 insert

iterator insert(iterator pos, const T& x)//在pos之前插入x
{
	Node* cur = pos._node;
	Node* newnode = new Node(x);
	Node* prev = cur->_prev;
	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = cur;
    cur->_prev = newnode;
    ++_size;
	return iterator(newnode);
}

2.2 erase

iterator erase(iterator pos) //在pos位置删除
{
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;
	delete cur;
	prev->_next = next;
	next->_next = prev;
	--_size;
	return iterator(next);
}

2.3 push_back、pop

void push_back(const T& x)
{
	insert(end(), x);
}
void push_front(const T& x)
{
	insert(begin(), x);
}
void pop_front()//头删就是在begin位置删除
{
	erase(begin());
}
void pop_back()//尾删
{
	erase(--end());
}

3.前置++、--、后置++、--

3.1前置：

self& operator++()
{
	_node = _node->_next;
	return *this;
}
self& operator--()
{
	_node = _node->_prev;
	return *this;
}

3.2后置：

self operator++(int) //能用前置就不要用后置，后置要返回++之后的
{
	self tmp(*this);
	_node = _node->_next;
	return tmp;
}
self operator--(int) 
{
	self tmp(*this);
	_node = _node->_prev;
	return tmp;
}

3.3 =、!=

bool operator!=(const self& s)
{
	return _node != s._node;  //看节点的指针是否相等
}
bool operator==(const self& s)
{
	return _node == s._node;  //看节点的指针是否相等
}

4.普通迭代器和const迭代器

4.1 普通迭代器 iterator

list迭代器不是原生的指针，将节点的指针进行封装，来模拟指针的行为。普通迭代器是可读可写

template<class T>
	struct list_node
	{
		T _data;
		list_node<T>* _next;
		list_node<T>* _prev;
		list_node(const T& x=T())
			:_data(x)
			,_next(nullptr)
			,_prev(nullptr)
		{}
	};
	template<class T>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T> self;
		Node* _node;
		__list_iterator(Node* node)
			:_node(node)
		{}
		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		self operator++(int) //能用前置就不要用后置，后置要返回++之后的
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}
		self operator--(int) 
		{
			self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
		T& operator*()
		{
			return _node->_data;
		}
		T* operator->()
		{
			return &_node->_data;
		}
		bool operator!=(const self& s)
		{
			return _node != s._node;  //看节点的指针是否相等
		}
		bool operator==(const self& s)
		{
			return _node == s._node;  //看节点的指针是否相等
		}
	};

如果list存的是自定义类型，怎么访问其中的数据呢？

需要实现重载-> 返回的是A对象的指针，在用->访问其中的成员

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

struct AA
{
	AA(int a1=0,int a2=0)
	:_a1(a1)
	,_a2(a2)
	{}
	int _a1;
	int _a2;
};
void test_list3()
{
	list<AA> lt; //list中存的是自定义类型
	lt.push_back(AA(1, 1));
	lt.push_back(AA(2, 2));
	lt.push_back(AA(1, 3));
	list<AA>::iterator it = lt.begin();
	while (it != lt.end())
	{
	//	cout << *it << " ";//*it是A,A不支持流插入
	//	cout << (*it)._a1 << " " << (*it)._a2<<endl;
		cout << it->_a1 << " " << it->_a2 << endl;
		++it;
	}
	cout << endl;
}

4.2 const迭代器 const_iterator

const对象只能使用const类型的迭代器，const是只读的，模拟const T*,是指向的内容不可改变，而不是本身不可改变。const_iterator是一个全新的类型，不是const iterator

template<class T>
	class list
	{
		typedef list_node<T> Node;
	public:
		typedef __list_iterator<T> iterator;
		typedef __list_const_iterator<T> const_iterator;
		const_iterator begin() const
		{
			return const_iterator(_head->_next);
			//也可以写成 return _head->_next;隐式类型转换，和上面是一样的
		}
		const_iterator end() const//哨兵卫位置
		{
			return const_iterator(_head);
		}
}
template<class T>
	struct __list_const_iterator
	{
		typedef list_node<T> Node;
		typedef __list_const_iterator<T> self;
		Node* _node;
		__list_const_iterator(Node* node)
			:_node(node)
		{}
		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		self operator++(int) //能用前置就不要用后置，后置要返回++之后的
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}
		self operator--(int)
		{
			self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
		//返回的是data的别名
		const T& operator*()
		{
			return _node->_data;
		}
		const T* operator->()
		{
			return &_node->_data;
		}
		bool operator!=(const self& s)
		{
			return _node != s._node;  //看节点的指针是否相等
		}
		bool operator==(const self& s)
		{
			return _node == s._node;  //看节点的指针是否相等
		}
	};

使用：

void print_list(const list<int>&lt)
{
	list<int>::const_iterator it = lt.begin();
	while (it != lt.end())
	{
		//*it = 10;不能修改，调用operator*返回data的别名，加const不能修改
		cout << *it << " ";
		it++;
	}
}
void test_list3()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	print_list(lt);
}

但是const迭代器和普通迭代器主要区别就是返回值不一样，所以上面的写法太冗余了。使用模板，交给编译器去做。

#pragma once
#include<iostream>
using namespace std;
namespace bit
{
	template<class T>
	struct list_node
	{
		T _data;
		list_node<T>* _next;
		list_node<T>* _prev;
		list_node(const T& x=T())
			:_data(x)
			,_next(nullptr)
			,_prev(nullptr)
		{}
	};
	//T T& T*
	//T const T& const 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)
			:_node(node)
		{}
		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		self operator++(int) //能用前置就不要用后置，后置要返回++之后的
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}
		self operator--(int) 
		{
			self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
		Ref operator*()
		{
			return _node->_data;
		}
		Ptr operator->()
		{
			return &_node->_data;
		}
		bool operator!=(const self& s)
		{
			return _node != s._node;  //看节点的指针是否相等
		}
		bool operator==(const self& s)
		{
			return _node == s._node;  //看节点的指针是否相等
		}
	};
	
	template<class T>
	class list
	{
		typedef list_node<T> Node;
	public:
		typedef __list_iterator<T,T&,T*> iterator;
		typedef __list_iterator<T,const T&,const T*> const_iterator;//通过模板参数去控制是普通迭代器还是const
		const_iterator begin() const
		{
			return const_iterator(_head->_next);
			//也可以写成 return _head->_next;隐式类型转换，和上面是一样的
		}
		const_iterator end() const//哨兵卫位置
		{
			return const_iterator(_head);
		}
		iterator begin()
		{
			return iterator(_head->_next);
		}
		iterator end() //哨兵卫位置
		{
			return iterator(_head);
		}
		void empty_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}
		list()
		{
			empty_init();
		}
		//lt2(lt1)   lt2拷贝构造lt1,this就是lt2
		list(const list<T>& lt)
		{
			empty_init();
			for (auto e : lt)
			{
				push_back(e); 
			}
		}
		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);//交换头指针
			std::swap(_size, lt._size);//交换_size
		}
		//lt3=lt1  lt就是lt1的拷贝构造  赋值重载
		list<int>& operator=(const list<int>& lt)
		{
			//现代写法
			swap(lt);
			return *this;
		}
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}
		void clear()
		{
			//清理数据,不清头节点
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);//it就是下一个位置
			}
		}
		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 push_front(const T& x)
		{
			insert(begin(), x);
		}
		void pop_front()//头删就是在begin位置删除
		{
			erase(begin());
		}
		void pop_back()//尾删
		{
			erase(--end());
		}
		iterator insert(iterator pos, const T& x)//在pos之前插入x
		{
			Node* cur = pos._node;
			Node* newnode = new Node(x);
			Node* prev = cur->_prev;
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
			++_size;
			return iterator(newnode);
		}
		iterator erase(iterator pos) //在pos位置删除
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;
			delete cur;
			prev->_next = next;
			next->_next = prev;
			--_size;
			return iterator(next);
		}
		size_t size()
		{
			return _size;
		}
	private:
		Node* _head;
		size_t _size;
	};
	void test_list1()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);
		//封装屏蔽底层差异和实现细节
		//提供统一的访问修改遍历方式
		list<int>::iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}
	struct AA
	{
		AA(int a1=0,int a2=0)
			:_a1(a1)
			,_a2(a2)
		{}
		int _a1;
		int _a2;
	};
	void test_list2()
	{
		list<AA> lt; //list中存的是自定义类型
		lt.push_back(AA(1, 1));
		lt.push_back(AA(2, 2));
		lt.push_back(AA(1, 3));
		list<AA>::iterator it = lt.begin();
		while (it != lt.end())
		{
		//	cout << *it << " ";//*it是A,A不支持流插入
		//	cout << (*it)._a1 << " " << (*it)._a2<<endl;
			cout << it->_a1 << " " << it->_a2 << endl;
			++it;
		}
		cout << endl;
	}
	void print_list(const list<int>&lt)
	{
		list<int>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			//*it = 10;不能修改，调用operator*返回data的别名，加const不能修改
			cout << *it << " ";
			it++;
		}
	}
	void test_list3()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);
		print_list(lt);
	}
}