C++ STL库详解：list的详细模拟实现

一、前言

在详细学习并学习c++后，我们对stl库的例如vector、list、string都有了详细的了解，对模板的使用以及类和对象都有了熟练的掌握，而实践才是检验真理的唯一标准，在此片博客中，将利用先前学过的各模块知识来对list这个在数据结构中令许多初学者摸不到北，在c++中出场率不高的容器进行模拟实现。在巩固c++基础的同时，也感受一下前辈先贤们撰写list时的清奇思路。

当然，我们在进行编写时要开辟一个全新的namespace，以防和库里的list冲突。

二、listNode实现

template<class T>
	struct listNode
	{
		listNode<T>* _next;
		listNode<T>* _prev;
		T _data;

		listNode(const T& x = T())//初始化列表对其进行初始化
			:_next(nullptr)
			, _prev(nullptr)
			, _data(x)
		{

		}
	};

首先进行的就是list'中节点元素的实现，list作为一个带头双向链表，每个节点应该包含三个元素：next、prev、val。分别用来存放，前一个元素的地址、后一个元素的地址，和本元素的值。有时在调用list时，我们经常不传参直接申请节点，所以需要借助初始化列表来处理此情况，当不传参初始化列表时，就要调用无参的构造函数，const T& x = T()，当不传参时，根据此时T的类型来实现初始化，例如此时T是int，那么就会变成const T& x = int()，对于自定义类型，编译器会去调用自定义类型的构造函数，而对于内置类型（如：int、char、double），编译器会去调用它们的默认构造函数（像int、char这种内置类型，编译器底层都已经对其构造函数进行过无参初始化处理），所以此时再去进行list<int> lt;这种先申请空间不进行传参的操作时，编译器就会去调用我们写的listNode的构造函数进行初始化，而我们的构造函数在没有接收到参数时就会去调用T()这个内置类型的默认构造函数，从而完成初始化。

三、迭代器实现

template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef ListNode<T> Node;
		typedef __list_iterator<T, Ref, Ptr> self;
		Node* _node;

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

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

		// it++
		self operator++(int)
		{
			//__list_iterator<T> tmp(*this);
			self tmp(*this);

			_node = _node->_next;

			return tmp;
		}

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

		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;
		}
	};

因为迭代器有const和普通迭代器两种形式，所以在类内部也要做出区分，在套用模板时，考虑到->和*具有访问节点数据的作用，而const迭代器无法直接更改数据，所以在编写list迭代器时，多增加了两个模板参数针对调用两种不同的迭代器时所造成的返回值不同的问题进行处理。

? 对于前置++和前置--,先加加先减减再使用? 返回的是进行加减操作之后的值，而后置是先使用再操作，所以前置可以使用引用&接收直接由this指针所返回的当前节点的值，而后置进行过处理以后当前节点的数值已经发生了改变，所以必须重新开辟一个新的空间用this指针进行拷贝构造来存放加减运算之前的值，同时返回的值必须也要使用iterator类型来进行接收而不是引用来接收，因为调用完后置加减后tmp作为函数内部的临时变量会被自动销毁，此时如果用引用来接收就会产生野指针从而报错，而前置传的是this指针本身，函数调用完成后this指针不会被销毁所以可以用&引用。? ??

四、list内部功能实现

template<class T>
	class list
	{
		typedef ListNode<T> Node;
	public:
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;

		//typedef __list_const_iterator<T> const_iterator;


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

		iterator end()
		{
			return _head;
		}

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

		const_iterator end() const
		{
			return _head;
		}

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

		list()
		{
			empty_init();
		}

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

		~list()
		{
			clear();

			delete _head;
			_head = nullptr;
		}

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

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

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

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

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

			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());
		}

		// vector insert会导致迭代器失效
		// list会不会？不会
		iterator insert(iterator pos, const T& x)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* newnode = new Node(x);

			// prev newnode cur
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;

			//return iterator(newnode);
			return 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;

			return next;
		}

	private:
		Node* _head;
	};

? ? ?写好iterator后，就可以在list中直接对其进行复用，当调用const迭代器时，就传const型给迭代器，当调用普通类型迭代器时就穿普通类型给迭代器。写好insert和erase后就可以在list类内部实现链表头删尾删，头插尾插时配合和begin(),end()进行对其进行复用，更好的简化了代码量，避免出现大量重复冗余的代码。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?