List的模拟实现

#include<iostream>
#include<assert.h>
namespace nrf
{
	template<class T>
	struct _list_node
	{
		_list_node<T>* _next;
		_list_node<T>* _prev;
		T _data;

		_list_node(const T& val = T())
			:_next(nullptr)
			, _prev(nullptr)
			, _data(val)
		{}
	};

	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)
		{}

		//*it,返回_data
		Ref operator*()
		{
			return _node->_data;
		}
		//it->date
		Ptr operator->()
		{
			return &_node->_data;
		}
		//it++,返回还是一个迭代器,前置++
		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		//前置--
		Self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		//后置++
		Self operator++(int)
		{
			Self tmp(*this);  //创建临时变量返回，后置加加，加加之前不变
			//_list_iterator<T>tmp = *this;
			_node = _node->_next;
			//++（*this)
			return tmp;
		}
		//后置--
		Self operator--(int)
		{
			Self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}

		//==
		bool operator ==(const Self& it)
		{
			return _node = it._node;
		}
		//it!=end()
		bool operator!=(const Self& it)
		{
			return _node != it._node;
		}
	};

	template<class T>
	class list
	{
	public:
		typedef _list_node<T> Node;
	public:
		typedef _list_iterator<T,T&,T*> iterator;
		typedef _list_iterator<T,const T&,const T*> const_iterator;
		iterator begin()            //第一个数据的迭代器，节点的指针构建迭代器
		{
			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);
		}


		//带头双向循环链表
		list()                     
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		} 

		//l2(l1)
		list(const list<T>& l1)           
		{
			//链表的最初状态
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;

			//const_iterator it = l1.begin();   //构造一个const迭代器尾插到新的迭代器中
			//while (it != l1.end())
			//{
			//	this->push_back(*it);
			//	it++;
			//}

			for (auto e : l1)
			{
				push_back(e);
			}
		}

		list<T>& operator=(const list<T>& l1)
		{
			if (this != &l1)
			{
				clear();
				for (auto e : l1)
				{
					push_back(e);
				}
			}
			return *this;
		}
		
		//现代版的拷贝构造
		//list<T>& operator=(list<T> l1)
		//{
		//	swap(_head, l1._head);
		//	return *this;
		//}
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				erase(it++);         
			}
		}
		~list()                      
		{
			clear();                 //clear没有删除头结点
			delete _head;
			_head = nullptr;
		}
		bool empty() const
		{
			return _head->_next == _head->_prev;
		}
		//T x  如果T类型是vector或者是string就造成了深拷贝,那么就得传引用，传引用不改变x就加const
		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 insert(iterator pos, const T& x)    //在pos这个迭代器的前面插入一个节点
		{
			Node* newnode = new Node(x);
			//pos 是个迭代器,而迭代器又是节点的指针，所以可以通过迭代器找到这个节点
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
			//return iterator(newnode);
		}

		void pop_back()
		{
			erase(--end());
		}
		void pop_front()
		{
			erase(begin());//end是最后一个有效数据的下一个位置，所以end先--，删除end--的位置
		}
		void erase(iterator pos)
		{
			//pos是一个迭代器，节点的指针，可以找到这个节点
			//找到要删除的节点del
			assert(pos != end());//头结点不能删除
			Node* del = pos._node;
			Node* next = del->_next;
			//假设有1 2 3节点，要删除pos位置2节点，
			//先2节点的前一个节点1节点的下一个节点指向2指向的3节点
			//然后要把3和1链接起来，把3的前一个节点指向1，
			//2的下一个节点3节点的前一个节点指向2的前一个节点
			//删除2
			del->_prev->_next = del->_next; 
			del->_next->_prev = del->_prev;
			delete del;
			//return iterator(next);//返回节点的下一个位置
		}
	private:
		Node* _head;
	};
	void testlist1()
	{
		list<int> lt1;
		lt1.push_back(1);
		lt1.push_back(2);
		lt1.push_back(10);
		lt1.push_back(20);
		lt1.pop_back();
		list<int>::iterator it = lt1.begin();
		while (it != lt1.end())
		{
			std::cout << *it << " ";
			++it;
		}
		std::cout << std::endl;
	}
	struct Date
	{
		int _year = 0;
		int _month = 1;
		int _day = 1;
	};

	void print_list(const list<int>& lt1)
	{
		list<int>::const_iterator it = lt1.begin();
		while (it != lt1.end())
		{
			std::cout << *it << " ";
			it++;
		}
		std::cout << std::endl;
	}
	void testlist2()
	{
		list<Date> lt1;
		lt1.push_back(Date());
		lt1.push_back(Date());
		list<Date>::iterator it = lt1.begin();
		while (it != lt1.end())
		{
			/*std::cout << *it << " ";*/
			//it->Date->_year  
			std::cout << it->_year << ":" << it->_month << ":" << it->_day << std::endl;
			std::cout << (*it)._year << ":" << (*it)._month << ":" << (*it)._day << std::endl;
			++it;
		}
		//print_list(lt1);
	}
	void testlist3()
	{
		list<int> l1;
		l1.push_back(1);
		l1.push_back(2);
		l1.push_back(3);
		l1.push_back(4);
		
		list<int>l2(l1); //拷贝构造，用l1拷贝构造l2
		for (auto e : l1)
		{
			std::cout << e << " ";
		}
		std::cout << std::endl;
		for (auto e : l2)
		{
			std::cout << e << " ";
		}
		std::cout << std::endl;
	}
}

重点

1.由于List的底层是双向带头循环链表，与Vector,String不同的是，我们要单独创建一个List的节点。
2.迭代器的类的实现，与Vector,String不同的是，这两个容器是将对象存在了一块连续的内存空间，与指针类似，通过指针的自增和自减可以完成对象的访问，但List是一个链表，节点在内存中的位置是随机的，而迭代器的意义就是，让使用者可以简单统一的对容器内的数据进行访问。所以我们创建的迭代器类，通过封装，对各种运算符的重载，实现了和其他容器一样的访问方法。
3.