C++（13）——STl之List的实现

STL

STL是C++的标准模板库，是一个具有工业强度，高效的C++程序库。

• STL一个最为重要的特点就是数据结构和算法的分离，你可以使用其中的一些函数操作几乎热河的数据集合，包含链表，容器和数组。
• STL的另一个特性就是它不是面向对象的，STL主要依赖模板而不是封装，继承和虚函数（多态性）

STL中包含的六大组件

1. 容器（container）：包含list、vector、deques，以模板类的方法提供，为了访问容器中的数据，可以使用由容器类输出的迭代器。
2. 迭代器（iterator）：提供为了访问容器中对象的方法。
3. 算法（Algorithm）：是用来操作容器中的数据的模板函数。
4. 仿函数（Functor）
5. 适配器（Adaptor）
6. 分配器（allocator）

大致了解STL是什么之后，完成对list类的理解，仿照VC6.0中list的源码，我们来自己实现一下list。
相关的细节我们已经在注释中写出：

#ifndef MK_LIST_H
#define MK_LIST_H
#include<iostream>
#include<stdlib.h>
#include<assert.h>
#include<string.h>

#include<initializer_list>
using namespace std;

namespace mk
{
template<class T>
void Swap(T &a,T&b)
{
	T tmp = a;
	a = b;
	b = tmp;
}
template<class _Ty>
class list
{
protected:
	struct _Node;
	typedef struct _Node* _Nodeptr;
	struct _Node
	{
		_Nodeptr _Prev, _Next;
		_Ty _Value;
	};
	struct _Acc;
	struct _Acc
	{
		typedef struct _Node*& _Nodepref;
		typedef _Ty& _Vref;
		//三个静态函数用于服务_Node结点的一些操作
		static _Vref _Value(_Nodeptr _P)//值引用返回
		{
			return (*_P)._Value;
		}
		static _Nodepref _Prev(_Nodeptr _P)//值结点指针引用返回
		{
			return (*_P)._Prev;
		}
		static _Nodepref _Next(_Nodeptr _P)//值结点指针引用返回
		{
			return (*_P)._Next; // return _P->_Next;
		}
	};
public:
	typedef _Ty          value_type;
	typedef _Ty&         reference;
	typedef const _Ty&   const_reference;
	typedef _Ty*         pointer;
	typedef const _Ty*   const_pointer;

	typedef size_t       size_type;
	typedef int          difference_type;

public:
	class const_iterator;
	class iterator;

	class const_iterator//对链表的数据值只能读不能写
	{
	protected:
		_Nodeptr _Ptr;//指向一个节点的首地址
	public:
		const_iterator(_Nodeptr _P = NULL) :_Ptr(_P) {}
		const_reference operator*() const
		{
			return _Acc::_Value(_Ptr);
		}
		const_pointer operator->() const
		{
			return &**this;
		}
		const_iterator & operator++()
		{
			_Ptr = _Acc::_Next(_Ptr);
			return *this;
		}
		const_iterator operator++(int)
		{
			const_iterator tmp = *this;
			++* this;
			return tmp;
		}
		const_iterator& operator--()
		{
			_Ptr = _Acc::_Prev(_Ptr);
			return *this;
		}
		const_iterator operator--(int)
		{
			const_iterator tmp = *this;
			--* this;
			return tmp;
		}
		bool operator==(const const_iterator& _X) const
		{
			return this->_Ptr == _X._Ptr;
		}
		bool operator!=(const const_iterator& _X) const
		{
			return !(*this == _X);
		}

		_Nodeptr _Mynode() const
		{
			return _Ptr;
		}
	};
	//普通迭代器，在List内部进行声明
	class iterator:public const_iterator//继承常性迭代器(公有继承：是一个)
	{
		typedef const_iterator base;
		// reference operator*() const//子类型和父类型的方法名相同：同名隐藏（不会调动父类里的方法，将其隐藏）
		// {
		// 	return _Acc::_Value(_Ptr);
		// }
		// pointer operator->() const
		// {
		// 	return &**this;
		// }
		
	public:
		iterator(_Nodeptr _P = NULL) :const_iterator(_P) {}
		iterator& operator++()
		{
			base::_Ptr = _Acc::_Next(base::_Ptr);
			return *this;
		}
		iterator operator++(int)
		{
			iterator tmp = *this;
			++* this;
			return tmp;
		}
		iterator& operator--()
		{
			base::_Ptr = _Acc::_Prev(base::_Ptr);
			return *this;
		}
		iterator operator--(int)
		{
			iterator tmp = *this;
			--* this;
			return tmp;
		}
		bool operator==(const iterator& _X) const
		{
			return this->_Ptr == _X._Ptr;
		}
		bool operator !=(const iterator& _X) const
		{
			return !(*this == _X);
		}
	};
public:
	iterator begin()
	{
		return iterator(_Acc::_Next(_Head));
	}
	iterator end() 
	{
		return iterator(_Head);
	}
	const_iterator begin() const 
	{
		return const_iterator(_Acc::_Next(_Head));
	}
	const_iterator end() const 
	{
		return const_iterator(_Head);
	}

public:
	typedef  const_iterator _It;
	//使用系统提供的初始化列表
	list(std::initializer_list<_Ty> list):list()
	{
		for(auto &x:list)
		{
			push_back(x);
		}
	}
	list() :_Head(_Buynode()), _Size(0) {}
	list(size_t count, const _Ty& val):_Head(_Buynode()), _Size(0)
	{
		insert(begin(), count, val);
	}
	list(const _Ty* _F, const _Ty* _L) :_Head(_Buynode()), _Size(0)
	{
		insert(begin(), _F, _L);
	}
	list(const list& _X) :_Head(_Buynode()), _Size(0)
	{
		insert(begin(), _X.begin(), _X.end());
	}
	list& operator=(const list _X)
	{
		if(this == &_X)return *this;
		iterator _F1 = begin();
		iterator _L1 = end();
		const_iterator _F2 = _X.begin();
		const_iterator _L2 = _X.end();

		for(;_F1 != _L1 && _F2 != _L2;++_F1,++_F2)
		{
			*_F1 = *F2;		
		}
		earse(_F1,_L1);
		insert(_L1,_F2,_L2);
		return *this;
	}
	~list()
	{
		clear();
		_Freenode(_Head);
	}
	void push_front(const _Ty& val)
	{
		insert(begin(), val);
	}
	void push_back(const _Ty& val)
	{
		insert(end(), val);
	}
	void insert(iterator _P,const _Ty *_F,const _Ty *_L)//插入一个数组
	{
		for (; _F != _L; ++_F)
		{
			insert(_P, *_F);
		}
	}
	void insert(iterator _P, size_t count,const _Ty &val)//插入同样的数值count个
	{
		while (count--)
		{
			insert(_P, val);
		}
	}
	void insert(iterator _P, _It _F, _It _L)//把一个链表插入到另一个链表
	{
		for (; _F != _L; ++_F)
		{
			insert(_P, *_F);
		}
	}
	void insert(iterator _P,std::initializer_list<_Ty> list)
	for(auto &x : List)
	{
		insert(_P,x);
	}
	iterator insert(iterator _P, const _Ty& val)//当前迭代器之前插入
	{
		_Nodeptr _S = _P._Mynode();//_S指向当前迭代器
		_Acc::_Prev(_S) = _Buynode(_Acc::_Prev(_S), _S);//购买节点，完成三步操作
		_S = _Acc::_Prev(_S);//_S指向插入节点
		_Acc::_Next(_Acc::_Prev(_S)) = _S;//完成最后一步操作
		new(&_Acc::_Value(_S)) _Ty(val);//定位new
		_Size += 1;
		return iterator(_S);
	}
	void pop_front()
	{
		erase(begin());
	}
	void pop_back()
	{
		erase(--end());//不是头节点，--指向最后一个节点
	}
	void erase(iterator _F, iterator _L)
	{
		for (; _F != _L; )
		{
			erase(_F++);
		}
	}
	void clear()
	{
		erase(begin(), end());
	}
	void remove(const _Ty &val)//从左往右遍历，删除第一个与val相等的结点
	{
		iterator _F = begin(),_L = end();
		while(_F != _L)
		{
			if(*_F != val)
			{
				_flag++;
			}
			else
			{
				erase(_F);
				break;  
			}
		}
	}
	void remove_all(const _Ty &val)//删除所有与val相等的结点
	{
		iterator _F = begin(),_L = end();
		while(_F != _L;)
		{
			if(*_F == val)
			{
				erase(_F++);
			}
		}
	}
	iterator erase(iterator _P)//返回删除结点后续一个结点迭代器的地址
	{
		_Nodeptr _node_del = _P++._Mynode();//调动顺序虽然如下：++ ——>_Mynode
		//此处为后置++，但是将亡迭代器tmp调动了_Mynode，即删除结点调动了_Mynode，因此是正确的的写法
		_Acc::_Next(_Acc::_Prev(_node_del)) = _Acc::_Next(_node_del);
		_Acc::_Prev(_Acc::_Next(_node_del)) = _Acc::_Prev(_node_del);
		(&_Acc::_Value(_node_del))->~_Ty();//对象释放自身资源(自定义类型),取value的原因就是需要释放的不是结点，而是结点内的对象
		_Freenode(_node_del);//释放空间，无法调动析构
		this->_Size--;
		return _P;//注意失效迭代器问题
	}
	
	void Swap(List& _X)
	{
		mk::Swap(this->_Head,_X._Head);
		mk::Swap(this->_Size,_X._Size);
	}
private:
	_Nodeptr _Buynode(_Nodeptr _Parg = NULL, _Nodeptr _Narg = NULL)
	{
		_Nodeptr _S = (_Nodeptr)malloc(sizeof(_Node));
		_Acc::_Prev(_S) = _Parg == NULL ? _S : _Parg;
		_Acc::_Next(_S) = _Narg == NULL ? _S : _Narg;
		return _S;
	}
	void _Freenode(_Nodeptr _P)
	{
		free(_P);
	}
	_Nodeptr _Head;
	size_type _Size;//数据结点的个数，不包含头结点
};
}
#endif

就地构造问题

使产生对象的个数变少，比如下面的代码：

 std::list<Object> alist;
 alist.push_back(Object(23));//2
 Object a(10;)alist.push_back(Object(a));//3
 alist.emplace_back(12);//4

• 第二行代码：按照push_back构建，先产生一个无名对象（右值），插入节点之后，将右值对象的资源移动构造到已插入结点中，将无名对象的资源拿到手，一共产生两个对象
• 第三行代码：按照push_back构建，它是一个具名对象（左值），此时再按照拷贝构造的方式进行构造，此时不会使用移动构造，因为一旦使用移动构造，a所拥有的资源将不存在，构建完成之后，需要再使用a时，此时它已经不具有资源，这是不被允许的，除非明确告知a不再需要使用此资源：alist.push_back(std::move(a));，强转成右值，形成上面的调动方式，我们需要考虑是否需要使用到a的资源，如何有效地利用资源，一共产生两个对象
• 第四行代码:按照emplace_back构建，我们不深究其实现方式（源码过于复杂），只了解这个过程中只产生一个对象即可。