C++STL容器List的模拟实现

一、引言

        list的实现，还是比较简单的，大家只要想着土家楼的形状，画出图来就好了，不需要过多担心。本次的博客会发出一个完整的实现List的List.hpp，以后也会这样，主要是分段发被说孩子分段生。

二、模拟List

        由于list中的结构需要特定的类型和特定的指定地址的，所以我们先要实现list中的结点和迭代器。正所谓"工欲善其事，必先利其器"。

        2.1        List内的结点制造

                 可以理解为一个包裹，用箱子包裹着的网购物品，list相当于分配的快递线。list结点要有前后指针，肯定也要有存储数据的类型。所以list_node中设计三个数据。

// 模版的使用。
// 可以套用任何类型，让编译器自己去推。
template< class T >
// 用struct是因为struct默认public访问(也就是允许访问任何资源)。
struct List_Node
{
    // 缺省参数，未传参时，可以默认初始化_val。
    // _next和_prev都是nullptr，初始化好，方便list类盖。
	List_Node(T val = T())
		:_val(val)
		, _next(nullptr)
		, _prev(nullptr)
	{
		;
	}

    // C++11的万能引用，等些到万能引用会粘贴好的。
	template < class X >
	List_Node(X&& val)
		:_val(val)
		, _next(nullptr)
		, _prev(nullptr)
	{
		;
	}
    
	T _val;
	List_Node* _next;
	List_Node* _prev;
};

        2.2      Iterator的模拟实现

                iterator迭代器是用来代替指针指向list中的地址的，所以肯定要有list结点的指针。在iterator迭代器中我们需要重载他们的运算符，重载运算符是C++的特性(operator 要重载的运算符，值得一提的是，重载的运算符不能违背运算符本身之外的操作，不然很容易报错)。我们根据迭代器类比指针就可以知道要重载什么运算符，由于list迭代器是双向迭代器，不支持+、-某一位置的单位距离，所以我们不能支持Self operator + ()和Self operator - ()，不仅如此还要删除掉他们。使用delete关键字，令这两个函数赋值delete，两个函数就会停止生成。

template< class T , class Ptr , class Ref >
struct Iterator
{
    // 设置list中的List_Node，一个具有标识性的名字。
    // 封装好一点。
	typedef List_Node < T > Node;
    // 可变性
    // 为了实现在list中的普通类型和const类型的迭代器。
    // 不用实现两份代码。
    // 在接下来的list中会讲。
    // 最主要的原因是list的迭代器不能像vector中的迭代器直接加const。
    // 如果只加const，说明迭代器指向了另一个结点类型，根本无法适用。
	typedef Iterator < T , Ptr , Ref > Self;
    // 而且这样不用写一大串类型名。
    
    // 初始化对象。
	Iterator(Node* node)
		:_node(node)
	{
		;
	}
    
	Ref operator * ()
	{
		return _node->_val;
	}

	Ptr operator -> ()
	{
		return &(_node->_val);
	}

	Self& operator ++ ()
	{
		_node = _node->_next;

		return (*this);
	}

	Self& operator -- ()
	{
		_node = _node->_prev;

		return _node;
	}

	Self operator ++ (int)
	{
		Self tmp(_node);
		_node = _node->_next;

		return tmp;
	}

	Self operator -- (int)
	{
		Self tmp(_node);
		_node = _node->_next;

		return tmp;
	}

    Self& operator = (const Self& s)
    {
        _node = s._node;

        return (*this);
    }

	// 减少拷贝，怕临时值捣乱，无法左值引用。
	bool operator == (const Self& node)
	{
		return _node == node._node;
	}

	bool operator != (const Self& node)
	{
		return _node != node._node;
	}
    
		// 删除这两个函数，不让这两个函数被错误调用。
		Self& operator + (size_t i) = delete;
		Self& operator - (size_t i) = delete;

	Node* _node;
};

        2.3        List中的基本结构和初始化函数

                List中一定包含着List_Node类型结点，就像快递线上有着的包裹，回转寿司有着寿司，土家族楼有着房间一样。上一章我们说过如果设计一个环形的结构，不知道以哪个结点为开头，所以我们新增一个带头链接点为开头，避免群龙无首的事情发生。另外插入过程中，我们无法通过结点直接的运算得到插入结点总数量为多少，所以我们添加一个变量，记录插入结点的总数量。

// 无参构造
List()
{
	_lt = new Node();

	_lt->_next = _lt;
	_lt->_prev = _lt;
}

// 初始化列表构造，就把它当做数组就行了。
// 另外initializer_list是C++11的内容，使用时记得调好编译器选项。
List(initializer_list<T> lt)
{
	_lt = new Node();

	for (auto& e : lt)
	{
		Emplace_back(e);
	}
}

Node* _lt;
size_t _n;

        2.4        size()函数和empty()函数

                List不像Vector和String一样有capacity(）有着空间大小，只要有_n就行了。根据_n我们可以判断List中是否存在数据以及插入数据有多少个。

size_t size()
{
	return _n;
}

bool empty()
{
    return _n == 0;
}

        2.5        Insert()和Erase()函数

                Insert()函数和Erase()函数都是在指定位置插入删除。

                我们先从插入开始讲起。插入只需要将pos位置上的结点(我们将这个结点设为结点A)和要pos位置之前(_prev)的结点(我们将这个结点设为结点B)和该位置的结点的_prev、_next指针做修改就可以了。由图可知让结点A(pos)的_prev指针指向新结点的地址，结点B(--pos上的结点)的_next指针指向新结点的地址，再让新结点的_prev指向结点B，_next指针指向结点A。

                讲完插入，就要将删除了。删除就更简单了，将要删除结点pos之前的位置和要删除结点之后的位置直接相连。再将pos上的结点delete掉，返回现在处于pos位置上的结点，也就是pos位置上的下一个结点。

        另外为什么需要返回插入、删除位置上新结点？

        是为了更新迭代器显示的pos位置上的结点避免访问出现错误，那为什么不直接在函数内修改pos呢？

        这个主要是出于有些迭代器不需要去修改，这个只能让用户去进行决定，比如说insert(begin())，begin()需要修改内部的指针吗？况且有时候这是一份吃力不讨好的工作，毕竟拷贝也是有效率牺牲的。其前面也提到过C++追求极致的效率，是不可能损害效率的。

iterator Insert(iterator pos , const T& val)
{
	// 前节点
	Node* prev = ((pos._node)->_prev);
	// 后节点
	Node* next = pos._node;
	// 新插入节点。
	Node* tmp = new Node (val);

	// 新节点插入
	tmp->_next = next;
	tmp->_prev = prev;

	// 前节点更新next（记录下一个节点的地址。）
	prev->_next = tmp;

	// 后节点节点更新prev（记录上一个节点的地址。）
	next->_prev = tmp;

	// 更新结点个数。
	++_n;

	return iterator(tmp);
}

// 按照STL的思想，应该是返回后一个位置，因为返回删除后该位置的指针，后一个位置已经顶替了该位置的指针。
iterator Erase(iterator pos)
{
    // 判断是否存在数据。
	assert(empty());
    // 删除位置不能为确定位置的头结点。
	assert(pos != End());

	// 前节点
	Node* prev = ((pos._node)->_prev);
	// 后节点
	Node* next = (pos._node)->_next;

	// 删除该节点。
	next->_prev = prev;
	prev->_next = next;

	pos._node->_next = pos._node->_prev = nullptr;
	delete pos._node;

	// 更新结点个数。
	--_n;
    
    // 构建匿名对象(方便返回)，相当于调用一个Iterator的初始化函数。
	return iterator(next);
}

        2.6        begin()函数和end()函数

                begin()指明List中的起始位置(当List中没有结点时，会等于end())，所以begin()应返回的是定位的头结点。end()可以设为定位头结点本身。

		iterator begin()
		{
			return iterator(_lt->_next);
		}

		iterator end()
		{
			return iterator(_lt);
		}

        2.7        push_back()函数和pop_back()函数        

               至于这个就更简单了，代码应该讲究能复用时就复用，这样能提高代码的健壮性 ，毕竟改代码只用改一个地方还是改几个地方还是很便捷的，最重要的是使代码变得简洁，以后用的时候也好用。所以我们直接复用insert和erase。

void push_back(T val)
{
	Insert(end(),val);
}

void pop_back()
{
	Erase(end());
}

        2.8        emplace()函数和empalce_back()函数        

                这个我保证C++11的时候绝对会讲。到时候放个链接在这里。

三、全部代码

#include <iostream>
#include <initializer_list>
#include <cassert>
using namespace std;

namespace Link_List
{
	template< class T >
	struct List_Node
	{
		List_Node(T val = T())
			:_val(val)
			, _next(nullptr)
			, _prev(nullptr)
		{
			;
		}

		template < class X >
		List_Node(X&& val)
			:_val(val)
			, _next(nullptr)
			, _prev(nullptr)
		{
			;
		}

		T _val;
		List_Node* _next;
		List_Node* _prev;
	};

	template< class T , class Ptr , class Ref >
	struct Iterator
	{
		typedef List_Node < T > Node;
		typedef Iterator < T , Ptr , Ref > Self;

		Iterator(Node* node)
			:_node(node)
		{
			;
		}

		Ref operator * ()
		{
			return _node->_val;
		}

		Ptr operator -> ()
		{
			return &(_node->_val);
		}

		Self& operator ++ ()
		{
			_node = _node->_next;

			return (*this);
		}

		Self& operator -- ()
		{
			_node = _node->_prev;

			return _node;
		}

		Self operator ++ (int)
		{
			Self tmp(_node);
			_node = _node->_next;

			return tmp;
		}

		Self operator -- (int)
		{
			Self tmp(_node);
			_node = _node->_next;

			return tmp;
		}

		// 减少拷贝，怕临时值捣乱，无法左值引用。
		bool operator == (const Self& node)
		{
			return _node == node._node;
		}

		bool operator != (const Self& node)
		{
			return _node != node._node;
		}

		// 删除这两个函数，不让这两个函数被错误调用。
		Self& operator + (size_t i) = delete;
		Self& operator - (size_t i) = delete;

		Node* _node;
	};

	template < class T > 
	class List
	{
	public:
		typedef List_Node < T > Node;

		typedef Iterator < T  , T* , T& > iterator;
		typedef Iterator < T, const T*, const T& > Const_Iterator;

		List()
		{
			_lt = new Node();

			_lt->_next = _lt;
			_lt->_prev = _lt;
		}

		List(initializer_list<T> lt)
		{
			// 设计一个带头结点。
			_lt = new Node();

			_lt->_next = _lt;
			_lt->_prev = _lt;

			for (auto& e : lt)
			{
				Emplace_back(e);
			}
		}

		~List()
		{
			size_t n = _n;
			for(int i = 0;i < n;++i)
			{
				Erase(begin());
			}
			//cout << endl;
			//cout << _n << ":" << n << endl;
			//iterator it = Begin();
			//while (it != End())
			//{
			//	cout << *it << endl;
			//	++it;
			//}

			delete _lt;
			_lt = nullptr;
		}

		iterator begin()
		{
			return iterator(_lt->_next);
		}

		iterator end()
		{
			return iterator(_lt);
		}

		iterator Insert(iterator pos , const T& val)
		{
			// 前节点
			Node* prev = ((pos._node)->_prev);
			// 后节点
			Node* next = pos._node;
			// 新插入节点。
			Node* tmp = new Node (val);

			// 新节点插入
			tmp->_next = next;
			tmp->_prev = prev;

			// 前节点更新next（记录下一个节点的地址。）
			prev->_next = tmp;

			// 后节点节点更新prev（记录上一个节点的地址。）
			next->_prev = tmp;

			// 更新结点个数。
			++_n;

			return iterator(tmp);
		}

		// 按照STL的思想，应该是返回后一个位置，因为返回删除后该位置的指针，后一个位置已经顶替了该位置的指针。
		iterator Erase(iterator pos)
		{
			// 判断是否存在数据。
			// assert()不满足则触发。
            // 本质是一种检查。
            // 例如assert(false);常常被拿来做防御式编程
			assert(size());
			// 删除位置不能为确定位置的头结点。
			assert(pos != end());

			// 前节点
			Node* prev = ((pos._node)->_prev);
			// 后节点
			Node* next = (pos._node)->_next;

			// 删除该节点。
			next->_prev = prev;
			prev->_next = next;

			pos._node->_next = pos._node->_prev = nullptr;
			delete pos._node;

			// 更新结点个数。
			--_n;

			// 构建匿名对象(方便返回)，相当于调用一个Iterator的初始化函数。
			return iterator(next);
		}

		size_t size()
		{
			return _n;
		}

		bool empty()
		{
			return _n == 0;
		}

		void push_back(T val)
		{
			Insert(end(),val);
		}

		void pop_back()
		{
			Erase(end());
		}

		iterator add(iterator it)
		{
			return it;
		}

		// 接收参数包的类型，参数包不是单纯相同类型的集成。
		template < class X , class... ARGS >
		// 参数包后面...是展开的意思。
		// 前面则类似声明的意思。
		iterator add(iterator pos, X&& val, ARGS&&... args)
		{
			iterator it = Insert(pos , val);
			return add(it, args...);
		}
		
		template < class... ARGS >
		iterator Emplace(iterator cit, ARGS&&... args)
		{
			iterator it (cit);
			return add(it,args...);
		}

		template < class... ARGS >
		void Emplace_back(ARGS&&... args)
		{
			Emplace(end(),args...);
		}

	private:
		Node* _lt = nullptr;
		size_t _n;
	};

	// 测试Insert函数
	void test01()
	{
		List < int > lt;

		for (int i = 0; i < 13; ++i)
		{
			lt.push_back(i);
		}

		//lt.Erase(lt.begin());
		//lt.Erase(lt.end());
	}

	void test02()
	{
		List < int > lt = { 1,2,3,4,5,6,7 };

		for (auto& e : lt)
		{
			std::cout << e << " ";
		}
		std::cout << std::endl;
	}

	void test03()
	{
		//List < int > lt = { 11121,131,0321 ,1311,33,113,1321 };
		List < int > lt;

		int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

		for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
		{
			lt.push_back(a[i]);
		}

		List<int>::iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << *it << ' ';
			++it;
		}
		cout << endl;
	}
}


int main()
{
	Link_List::test02();

	return 0;
}