自定义实现list及其功能

在这里插入图片描述

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

namespace test
{
	//******************************设置结点******************************
	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)
		{}
	};

	//***************************************定义list迭代器***************************
	// typedeflist iterator<T， T&， T*>           iterator;
	// typedeflist iterator<T, const T&, const T*> const iterator;

	//list_node为结点类
	//template<class T>
	template<class T,class Ref,class Ptr>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T,Ref,Ptr> iterator;
		Node* _node;

		//构造函数，浅拷贝
		__list_iterator(Node* node)
			: _node(node)
		{}

		__list_iterator(const iterator& l)
			:_node(l._node)
		{}

		//重载!=
		bool operator!=(const iterator& it)const
		{
			return it._node != this->_node;
		}

		bool operator==(const iterator& s)const
		{
			return _node == s._node;
		}

		//重载 *it it.operator*()
		//T& operator*()
		//{
		//	return _node->_data;
		//}
		//T* operator->()
		//{
		//	return &(operator*());//&(_node->date);
		//}

		Ref operator*()
		{
			return _node->_data;
		}
		Ptr operator->()
		{
			return &(operator*());//&(_node->date);
		}

		//重载++前置
		iterator& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		
		//重载后置++
		iterator operator++(int)
		{
			iterator tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		//重载前置--
		iterator& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		//重置后置--
		iterator operator--(int)
		{
			iterator tmp(*this);
			_node = _node->_prev;
			return tmp;
		}



	};

	//**************************************模拟实现list******************************************
	//list_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_iterator begin()const
		 {
			 return const_iterator(_head->_next);
		 }
		 const_iterator end()const
		 {
			 return const_iterator(_head);
		 }

		 iterator begin()
		 {
			 return iterator(_head->_next);
		 }
		 iterator end()
		 {
			 return iterator(_head);
		 }

		 iterator insert(iterator pos, const T& x)
		 {
			 Node* cur = pos._node;
			 Node* prev = cur->_prev;

			 Node* newnode = new Node(x);

			 prev->_next = newnode;
			 newnode->_prev = prev;
			 newnode->_next = cur; 
			 cur->_prev = newnode;
			 ++size;
			 return iterator(newnode);
		 }

		 iterator erase(iterator pos)
		 {
			 assert(pos != end());

			 Node* cur = pos._node; 
			 Node* prev = cur->_prev; 
			 Node* next = cur->_next;
			 prev->_next = next; 
			 next->_prev = prev;
			 delete cur;
			 size--;
			 return iterator(next);
		 }

		 void push_back(const T& x)
		 {
			 //Node* tail = _head->_prev;
			 //Node* newnode = new Node(x);

			 _head  tail  newnode
			 //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_back()
		 {
			 erase(--end());
		 }

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

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

		 void empty_init()
		 {
			 //创建并初始化哨兵位头结点
			 _head = new Node;
			 _head->_next = _head;
			 _head->_prev = _head;
			 size = 0;
		 }

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

		 //构造函数
		 list()
		 {
			 /*_head = new Node;
			 _head->_next = _head;
			 _head->_prev = _head;*/
			 empty_init();
		 }

		 //模板构造函数初始化
		 template <class InputIterator>
		 list(InputIterator first, InputIterator last)
		 {
			 empty_init();
			 while (first != last)
			 {
				 push_back(*first);
				 ++first;
			 }
		 }

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

			 list<T> tmp(lt.begin(), lt.end());
			 swap(tmp);
		 }

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

		 size_t _size()
		 {
			 return size;
		 }
		 //析构函数
		 ~list()
		 {
			 clear();
			 delete _head;
			 _head = nullptr;
		 }
		 

	 private:
		 Node* _head;
		 size_t size = 0;
	 };

值得我们注意一下的是
在这里插入图片描述

struct Pos
	 {
		 int _a1;
		 int _a2;
		 Pos(int a1 = 0, int a2 = 0)
			 :_a1(a1)
			 ,_a2(a2)
		 {}
	 };
void test_list2()
	 {
		 int x = 10;
		 int* p1 = &x;
		 cout << *p1 << endl;


		 //多会用 . 多会用->
		 Pos aa;
		 Pos* p2 = &aa;
		 aa._a1;
		 p2->_a1;

		 list<Pos> lt;

		 lt.push_back(Pos(10, 20));
		 lt.push_back(Pos(10, 21));

		 list<Pos>::iterator it = lt.begin();
		 while (it != lt.end())
		 {
			 //cout << (*it)._a1 << " : " << (*it)._a2 << endl;
			 //it->是it.operator->()的类型（T*）
			 //语法为了可读性，编译器进行了特殊处理，省略了一个->

			 //return &(operator*());//&(_node->date);
			 cout << it->_a1 << " : " << it->_a2 << endl;
			 //原型cout << it->->_a1 << " : " << it->->_a2 << endl;
			 ++it;
		 }
		 cout << endl;
	 }