C++ list的模拟实现

目录

1. list介绍

2.模拟实现

3.比较list与vector

4.迭代器失效的问题

---

1. list介绍

list就是我们之前C语言数据结构实现过的 带头双向循环链表 ，我们很容易就能想到他的结构是什么样的，一个list对象中保存的无非就是哨兵头节点的指针。list相对于vector和string来说，他在任意位置的插入删除效率都很高，因为他不是连续的物理空间也不需要挪动数据这样的耗时操作。但是List是不支持方括号加下标的随机访问了，这也是它的结构带来的缺点，其实也不能叫做缺点，因为我们不会在需要随机访问的场景下去使用list来存储数据。 

同时，由于list 按需申请和释放空间的特点，list也就不需要resize 和 reserve 这样的接口了，因为没有意义，与它的结构相悖。 在list的适用于模拟实现中，我们就更能体会到STL容器的迭代器的优势，任意STL的对象都可以通过迭代器的方式，使用类似的代码进行遍历。但是由于list的迭代器我们无法再直接使用原生指针来实现了，所以模拟实现的时候可能会有点难度，需要对类和对象以及模板章节的内容有一定理解。

2.模拟实现

要定义 list 首先我们得有节点的结构体，而list的节点就是带头双向循环链表的节点结构。但是由于list是一个类模板，需要存储不同类型的数据，所以他的节点也应该是一个类模板，也要支持存储不同类型的数据。

 
	template<typename T>
	class listnode
	{
	public:
		listnode(T val =T() )
			:data(val)
			,prev(nullptr)
			,next(nullptr)
		{
		}
 
		T data;
		listnode* prev;
		listnode* next;
	};

节点的类我们只需要自己实现一个构造函数就行，节点的释放则由list的析构函数来完成。

template<typename T>
	class list
	{
	public:
		typedef listnode<T> listnode;
		
	private:
		listnode* phead;
	};

在这里我们用了 typedef 来对 listnode 类进行了显示实例化以及重命名。

为了方便测试简单的代码模块是否正常，我们首先实现简单的无参构造函数和析构函数

		//默认构造
		list() 
		{
			phead = new listnode();
			phead->next = phead;
			phead->prev = phead;
		}
 
		
		//析构
		~list()
		{
			listnode* cur = phead->next;
			while (cur != phead)
			{
				listnode* del = cur;
				cur = cur->next;
				delete del;
			}
			//最后释放头节点
			delete phead;
			phead = nullptr;
		}

然后再实现简单的首尾的插入删除的函数，同时由于头删尾删需要使用 empty方法来进行非空的判定，所以我们也直接一块实现了

 
		//判空
		bool empty()const
		{
			return phead == phead->next;
		}
 
		//头插
		void push_front(const T& val)
		{
			listnode* newnode = new listnode(val);
			newnode->next = phead->next;
			newnode->prev = phead;
			phead->next->prev = newnode;
			phead->next = newnode;
		}
 
		//头删
		void pop_front()
		{
			assert(!empty());
			listnode* del = phead->next;
			phead->next = del->next;
			del->next->prev = phead;
			delete del;
		}
		
		//尾插
		void push_back(T val)
		{
			listnode* newnode = new listnode(val);
			newnode->next = phead;
			newnode->prev = phead->prev;
			phead->prev->next = newnode;
			phead->prev = newnode;
		}
 
		//尾删
		void pop_back()
		{
			assert(!empty());
			listnode* del = phead->prev;
			del->prev->next = phead;
			phead->prev = del->prev;
			delete del;
		}

这些简单的方法我们很容易就能测试出来程序有没有bug，

在标准库中方法能够返回收尾的数据，我们也可以实现一下

		//头节点数据
		T& front()
		{
			assert(!empty());
			return phead->next->data;
		}
 
		const T& front()const
		{
			assert(!empty());
			return phead->next->data;
		}
 
		//尾节点数据
		T& back()
		{
			assert(!empty());
			return phead->prev->data;
		}
 
		const T& back()const
		{
			assert(!empty());
			return phead->prev->data;
		}

list的修改的方法如下

其中，assign是清空原链表的数据，然后使用传递的参数重新构造一个链表，这个方法效率不高，用的也很少，我们不实现了

 insert 和 erase 则是需要使用 迭代器 来指定插入或者删除的位置，等我们后面实现了迭代器再来实现。

swap函数就是交换两个链表的内容，其实只需要交换头节点就行了

		//swap
		void swap(list<T>& lt1)
		{
			std::swap(this->phead,lt1.phead);
		}

clear方法就是清除链表的所有数据，我们可以实现一下，然后析构函数就可以复用clear

		//clear
		void clear()
		{
			//头节点不释放
			listnode* cur = phead->next;
			while (cur != phead)
			{
				listnode* del = cur;
				cur = cur->next;
				delete del;
			}
			//头节点指向自己
			phead->next = phead;
			phead->prev = phead;
		}
 
		//析构
		~list()
		{
			clear();
			//最后释放头节点
			delete phead;
			phead = nullptr;
		}

Operation系列接口用的也很少，我们基本用不上

splice：转移链表节点，主角意识转移节点，而不是转移值，意思就是节点的地址和数据是不变的，变的只是他们的链接关系

remove和remove_if是用来删除特定数据或者满足某个条件的数据的。而sort则是用来排序的，算法库中的sort是无法对联表进行排序的，因为链表的数据在交换的时候会修改链接。同时，list的sort采用的是归并排序，而不是快排。

为什么算法库中的sort会报错呢？

首先我们要知道，算法库中的sort是要传迭代器区间的，而迭代器从功能的角度来看可以分为三类，一种是单向迭代器，也就是只能 ++ ，不能-- 和+ - ，一种是双向迭代器，就是既可以 ++ ，也可以 - - ，但是也不能进行 +  和 -  的操作，第三种就是随机迭代器，三种操作都支持。而我们的算法库中的sort是要传随机的迭代器的，并不是说不能够传其他的迭代器，编译器在传参的过程是检查不出来的，因为sort是一个函数模板，它的参数就是一个迭代器区间，传其他的迭代器也是能够正常实例化的。但是我们说了，算法库中的sort使用的是快排的思想，他在递归排序的过程中是会用到 两个迭代器相减 来判断迭代器是否支持随机访问，所以如果传的不是随机迭代器就会在相减的时候报错。 单链表的迭代器是单向的，list的迭代器是双向的。

unique ：去重，但是去重是有一个前提的，就是必须数据是有序的，否则达不到完全去重的效果

reverse：链表逆置，这里的逆置的话，我们也可以直接使用算法库中的逆置

这里的接口用的都不多，还是因为他们的效率不高。

迭代器的实现（最基础版本）

学习到了 list ，我们就不能再单纯使用原生指针来当迭代器了，因为满足不了迭代器的功能，list迭代器是支持++来进行迭代器的往后遍历的，而我们的节点由于是分批new出来的，空间不一定连续，所以我们要使用一个类模板来实现迭代器，同时要实现他的一些方法，比如 ++ ，！=以及 * 等运算符重载

迭代器的底层我们还是能够理解的，就是一个节点指针，它需要支持一系列的运算符重载来对迭代器对象中的节点的指针进行操作，迭代器这个类就是对原生指针的封装，能够让用户使用起来更加方便，同时封装了之后，以后也不用关系微妙的底层实现是什么，学习成本也低了。

//第一版最基础的迭代器
	template<typename T>
	class _list_iterator
	{
	public:
		typedef listnode<T> listnode;
 
		//迭代器的构造
		_list_iterator(listnode* p)
			:pnode(p)
		{
		}
		_list_iterator& operator++()
		{
			pnode = pnode->next;
			return *this;
		}
		bool operator!=(_list_iterator& it1)const
		{
			return pnode != it1.pnode;
		}
		T& operator*()
		{
			return pnode->data;
		}
		const T& operator*()const
		{
			return pnode->data;
		}
 
		listnode* pnode;
	};

当有了简单的迭代器之后，我们就能够实现 insert 和 erase了，而我们的传的迭代器参数可以直接使用算法库中的 find 来确定，因为find就是一次遍历，我们实现起来也没有多大的意义。

insert和erase由于不需要挪动数据，所以相比于string和vector而言实现起来十分简单。

 
		//插入一个数据
		iterator insert(iterator pos, T val)
		{
			listnode* newnode = new listnode(val);
			newnode->next = pos.pnode;
			newnode->prev = pos.pnode->prev;
			pos.pnode->prev->next = newnode;
			pos.pnode->prev = newnode;
			return iterator(newnode);
		}
		iterator erase(iterator pos)
		{
			pos.pnode->next->prev = pos.pnode->prev;
			pos.pnode->prev->next = pos.pnode->next;
			iterator ret(pos.pnode->next);
			delete pos.pnode;
			return ret;
		}
 
 
 
		//头插
		void push_front(const T& val)
		{
			insert(begin(), val);
		}
 
		//头删
		void pop_front()
		{
			assert(!empty());
			erase(begin());
		}
		
		//尾插
		void push_back(T val)
		{
 
			insert(end(), val);
		}
 
		//尾删
		void pop_back()
		{
			assert(!empty());
 
			//删除的是end的前一个数据
			erase(iterator(phead->prev));
		}

但是insert远不止插入一个数据这么简单，他还能插入一段迭代器区间的数据，也能够插入n个相同的数据，但是实现起来也不难，无非就是复用单个插入的insert

		//插入n个val
		void insert(iterator pos, size_t n, const T& val)
		{
			while (n--)
			{
				pos = insert(pos, val);
			}
		}
		//插入一个迭代器区间的数据
		template<typename InputIterator>
		void insert(iterator pos, InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				insert(pos,*first);
				++first;
			}
		}

注意的是插入一个迭代器区间的时候，pos不用更新，我们不用改变要插入的迭代器区间的数据的顺序。

erase也支持一段迭代器区间的删除，我们也可以直接复用删除单个数据的erase

		//删除迭代器区间
		void erase(iterator first,iterator last)
		{
			while (first != last)
			{
				iterator del = first;
				first++;
				erase(del);
			}
		}

const迭代器 （第二版）

const迭代器与普通迭代器的区别就是 * 运算符重载返回的值的类型，他也需要支持 + +和!=等操作，除了 * 重载之外，与普通迭代器是一模一样的。

要实现const迭代器，最简单的做法就是直接再创建一个类，修改一下*的返回值

 
	template<typename T>
	class const_list_iterator
	{
	public:
		typedef listnode<T> listnode;
 
		//迭代器的构造
		_list_iterator(listnode* p)
			:pnode(p)
		{
		}
		_list_iterator& operator++()
		{
			pnode = pnode->next;
			return *this;
		}
		_list_iterator& operator++(int) //后置++
		{
			pnode = pnode->next;
			return *this;
		}
 
		bool operator!=(_list_iterator& it1)const
		{
			return pnode != it1.pnode;
		}
		const T& operator*()
		{
			return pnode->data;
		}
		const T& operator*()const
		{
			return pnode->data;
		}
 
		listnode* pnode;
	};
 

        typedef const_list_iterator<T> const_iterator; //const迭代器
 
 
 
		//const迭代器
		const_iterator begin()const
		{
			return const_iterator(phead->next);
		}
 
		//const迭代器
		const_iterator end()const
		{
			//要注意的是end是开区间，也就是最后一个数据的下一个位置，就是phead
			return const_iterator(phead);
		}

但是这种做法有很大的代码冗余，既然const迭代器与普通迭代器只有 * 的返回值不同，那么我们是不是可以在模板中再加一个参数，专门用来表示 * 的返回类型。

	template<typename T ,typename ref>
	class _list_iterator
	{
	public:
		typedef listnode<T> listnode;
 
		//迭代器的构造
		_list_iterator(listnode* p)
			:pnode(p)
		{
		}
		_list_iterator& operator++()
		{
			pnode = pnode->next;
			return *this;
		}
		_list_iterator& operator++(int) //后置++
		{
			pnode = pnode->next;
			return *this;
		}
 
		bool operator!=(_list_iterator& it1)const
		{
			return pnode != it1.pnode;
		}
	    ref operator*()
		{
			return pnode->data;
		}
		const T& operator*()const
		{
			return pnode->data;
		}
 
		listnode* pnode;
	};

		typedef _list_iterator<T, T&> iterator;
		typedef _list_iterator<T,const T&> const_iterator;
 
        //迭代器
		iterator begin()
		{
			return iterator(phead->next);
		}
 
 
		iterator end()
		{
			//要注意的是end是开区间，也就是最后一个数据的下一个位置，就是phead
			return iterator(phead);
		}
 
		//const迭代器
		const_iterator begin()const
		{
			return const_iterator(phead->next);
		}
 
		//const迭代器
		const_iterator end()const
		{
			//要注意的是end是开区间，也就是最后一个数据的下一个位置，就是phead
			return const_iterator(phead);
		}

这样一来就可以用一个模板实现普通迭代器和const迭代器了，大大减少了代码量

实现const迭代器是为了支持我们的拷贝构造，因为拷贝构造不能影响到被拷贝对象的数据，所以我们需要用一个const的引用来接收参数，而拷贝构造我们是使用迭代器区间的构造来间接实现的，所以必须要有const对象的的迭代器。

		//迭代器区间构造
		template<typename InputIterator>
		list(InputIterator first, InputIterator last)
		{
			phead = new listnode;
			phead->next = phead;
			phead->prev = phead;
			insert(end(), first,last);
		}
 
        //拷贝构造
		list(const list& lt)
		:phead(new listnode)
		{
			//要对*this进行基本的初始化，以便交换之后tmp能够正常的析构
			phead->next = phead;
			phead->prev = phead;
			list tmp(lt.begin(),lt.end());
			swap(tmp);
		}

最后就是赋值重载，复制重载也和拷贝构造一样，利用swap来进行复制，同时由于被复制的对象他是由原来的节点的，所以我们还不用对其进行基本的初始化，直接交换就行了

		//赋值重载
		list& operator=(list lt)
		{
			swap(lt);
			return *this;
		}

在上面的拷贝构造中，我们可能会有投一个问题，我们说过类模板他不是一个实际的类，对于普通的类而言，类名就是他们的类型。而对于类模板来说，雷鸣一般不等价于类型，比如我们的list是类模板的类名，但是实例化之后他才是具体的类型，比如 list这样的才叫类型。

而我们上面的拷贝构造等构造函数，函数名是类名，这没有问题，因为C++就是这样规定的，但是我们再累模板里面实现的一系列方法，我们的传参的类型写的是list(类名)，而不是list(类型)，为什么可以这样传参呢？

这是C++的一个特例，就是在类里面，类名可以代表类型，但是在类外面，类名不等于类型。

我们将上面的类中的方法的参数的类型换成list也是能够跑过的，而且我们其实更推荐使用list这样的传参，因为这样更符合标准。

最后再回归迭代器，我们说过，迭代器的行为是类似于指针的，而对于结构体的指针，我们是能够通过 -> 来直接访问到结构体中的数据的，那么这里的迭代器是不是也要支持这样的功能呢？这样一来，由于结构体指针也需要const指针和普通指针，所以我们的类模板还需要再加一个参数表示  ->重载返回结构体的指针。

		ptr operator->()
		{
			return pnode;
		}

那么按理来说，我们是不是应该这样使用

		list<int>lt1;
		lt1.push_back(1);
		lt1.push_back(2);
		lt1.push_back(3);
		lt1.push_back(4);
		lt1.push_back(5);
 
		list<int>::iterator it = lt1.begin();
		cout << it->->data << endl;

第一个 it->是一个函数调用，返回了 pnode ，而第二个 ->则作用于pnode也就是我们的结构体指针，这样就能够访问到节点中的数据了，那么事实真是这样吗？

我们发现他有一个报错，是一个很奇怪的报错，确实成员名，但是我们上面的代码是写了成员名的，也就是我们的data，所以错误肯定不是他所说的缺少成员名，而是 ->的错误使用，当我们删除其中一个 -> 的时候

		list<int>::iterator it = lt1.begin();
		cout << it->data << endl;

我们发现这时候就能够编译通过并且正常运行了，而且结果还是我们所预料的结果

是否很奇怪？

其实这是编译器做的一个处理，因为 it->->data这种用法既不好看也不好用，与我们运算符重载的目的（增加可读性）不符，所以编译器做了特殊处理，省略了一个箭头。所以如果我们只写一个   ->，编译器能够自动识别并且补上一个箭头。但是如果我们显式写了两个->，这样会干扰编译器的自动识别，所以就直接不允许这样写了。

当然我们可以显式写运算符重载的调用，

		cout << it.operator->()->data <<endl;

但是这样写的话完全就没有可读性了，不建议这么写，虽然这样写更好理解。

3.比较list与vector

vector优点：

支持随机访问

不需要频繁扩容

尾插尾删效率高（至少比list高，因为不需要每一次申请和释放空间）

cpu高速缓存命中率高（连续物理空间）

vector缺点：

头插头删（前面部分数据插入删除）效率低

存在空间浪费，扩容消耗大

list优点：

按需申请和释放

任意位置插入删除效率高

list缺点：

不支持随机访问

cpu高速缓存命中率低

如果我们单纯存储数据的话，一般是vector用的多，但是如果需要频繁在前面部分插入删除，用list更好，当然最好是互相配合一起解决具体的应用场景。

4.迭代器失效的问题

通过我们前面的模拟实现，我们能够知道vector的迭代器失效存在于 insert 和 erase，vector的insert失效是因为扩容而导致的，erase的失效则很好理解。 而list的erase也会失效，这也很好理解，因为空间被释放了 。而string我们一般不关注迭代器失效的问题，他的失效其实是和vector一样的，但是我们使用string的时候一般是不会用到迭代器的，string 的insert和erase等常用的接口函数都是支持下标的，我们很少使用迭代器的接口对string对象进行操作。