【C++】解锁＜list＞的正确姿势

  
> 🍃 本系列为初阶C++的内容，如果感兴趣，欢迎订阅🚩
> 🎊个人主页:[小编的个人主页])小编的个人主页
>  🎀   🎉欢迎大家点赞👍收藏⭐文章
> ✌️ 🤞 🤟 🤘 🤙 👈 👉 👆 🖕 👇 ☝️ 👍

---

目录

 🐼前言

🐼认识list

 🐼list的迭代器失效问题⭐️

🐼list的模拟实现

🚩定义链表节点结构

🚩定义list类

🚩正向迭代器实现⭐️

🚩迭代器使用

🚩insert操作

🚩erase操作

🚩增删

🚩list构造

🚩析构函数

🚩反向迭代器实现⭐️ 

 🐼全部源码

🐼总结

---

 🐼前言

👐在之前的容器<string>,<vector>中，我们遇到的底层物理空间都是连续的，在list中，由于底层物理空间不连续，但是逻辑上是连续的，此时底层是如何实现的呢❓迭代器的行为又是什么样呢❓小编这篇文章👇带你从0认识并掌握使用list并了解list的底层结构。

🐼认识list

我们可以借助Cplusplus来查看list类的一些常用接口(list类中的其它接口小伙伴们可以根据我给的链接在需要时进行查询)。

🌻list类的构造:

以及第一个构造空的初始化构造。

🌻list iterator的使用:

这里可以先简单将迭代器理解成一个指针，该指针指向list中的某个节点。在模拟实现时我们可以再谈。

🌻容量操作

🌻访问元素操作

list支持访问头部和尾部元素，不支持随机访问，因为效率太低。但是像vector支持随机访问。List不支持operator[]

🌻增删查改操作

和<vector>不同的是，list支持在头部和尾部操作，因为效率很高,<vector>不支持在头部操作。

其余操作，大家可以查文档。

 🐼list的迭代器失效问题⭐️

 在<vector>中我们认为insert需要扩容和erase后，原来的迭代器就失效了，不能继续使用。list稍微有一些不同。首先迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。本质上还是由于vector物理空间是连续的，扩容等操作需要发生空间搬移，而list物理空间不连续，迭代器指向的那块空间没有发生改变。

举个例子:

void Test_lsg_list08()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l1(array, array + sizeof(array) / sizeof(array[0]));auto it = l1.begin();while (it != l1.end()){// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给//	其赋值l1.erase(it);++it;}//改正list<int> l2(array, array + sizeof(array) / sizeof(array[0]));auto it = l2.begin();while (it != l2.end()){it = l2.erase(it);//返回下一个元素的迭代器}}

erase删除It迭代器之后，it位置的迭代器失效了，需要重新更新it，才能继续使用。

🐼list的模拟实现

list的底层使用的是双向循环带头链表。如果有不清楚的小伙伴，可以看这篇文章，双向循环带头链表。

🚩定义链表节点结构

//定义节点结构
template<class T>
struct List_Node
{List_Node<T>* _next;//指向下一个节点的指针List_Node<T>* _prev;//指向前一个节点的指针T _data;List_Node(const T& x = T()):_next(nullptr),_prev(nullptr),_data(x){}
};

定义链表节点结构，并对每个节点进行构造初始化，避免是垃圾值。

🚩定义list类

我们知道list是双向循环带头链表，在list类拿一个头结点来维护一个list对象，并且我们希望统计list中元素的个数，list类就可以这样定义了:

template<class T>
class list
{typedef List_Node<T> Node;typedef List_Node<T>* pNode;
public:void empty_init(){_head = new Node(-1);_head->_next = _head;_head->_prev = _head;}list(){empty_init();}private:pNode _head;size_t _size;
};

✅代码解析:

完成了对空list类对象的初始化，本质是双向循环带头链表。

🚩正向迭代器实现⭐️

下面，我们完成list迭代器的创建工作:

我们知道迭代器目的是不暴露底层结构，不管是<vector><list><tree>等，对于不同的容器遍历的使用方式都是一样的，而迭代器的行为就是像指针一样，有的迭代器就是指针，不需要我们封装，像<vector><string>,而有的迭代器需要我们封装，像<list>等，这正是我们的STL设计迭代器的目的，不暴露底层结构，对于不同容器间一套相同的访问方式。
 

在list类中，如果我们还希望迭代器能访问双链表中的元素，即*访问到当前节点保存的值，++访问到下一个节点。如果单靠Node*作为迭代器，那解引用是Node，++也访问不到下一个节点，这显而易见没有这么简单。既然迭代器行为是具有像指针一样的东西，那么如果我们就能对迭代器进行封装，可以重载*和++以及更多的迭代器操作。

正向迭代器非const版本实现:

	template <class T>struct List_iterator{typedef List_Node<T> Node;typedef List_Node<T>* pNode;pNode _Node;List_iterator(Node* node):_Node(node){}T& operator*(){return _Node->_data;}//前置++List_iterator<T>& operator++(){_Node = _Node->_next;return *this;}//后置++List_iterator<T> operator++(int){List_iterator<T> tmp = *this;_Node = _Node->_next;return tmp;}bool operator!=(const List_iterator<T>& it){return _Node != it._Node;}T* operator->(){return &_Node->_data;}};

✅代码解析:

迭代器支持*,我们就重载一份*操作符来访问元素的值，迭代器支持++,--，我们就重载一份++，--，让迭代器的行为能够支持++,--。这样，不暴露底层结构，我们就能完成一套相同的访问操作。而list迭代器本质还是一个Node*的指针，只不过我们进行了封装。

我们根据上述的思路再实现正向迭代器const版本。

template <class T>
struct const_List_iterator
{typedef List_Node<T> Node;typedef List_Node<T>* pNode;pNode _Node;const_List_iterator(Node* node):_Node(node){}const T& operator*() const{return _Node->_data;}//前置++const_List_iterator<T>& operator++() {_Node = _Node->_next;return *this;}const_List_iterator<T> operator++(int) {List_iterator<T> tmp = *this;_Node = _Node->_next;return tmp;}bool operator!=(const const_List_iterator<T>& it){return _Node != it._Node;}const T* operator->() const{return &_Node->_data;}
};

只需要把权限缩小到const。

但是这样写，代码有点冗余了，因为我们只想控制const和非const在<list>中，那么如果我们能够在迭代器实例化时传参时传入对应的参数，因为他们都是一系列共用的迭代器家族，只是权限上有差异。因此，我们可以用函数模版多加两个参数来避免代码冗余性。

//用模版方法来控制const和非const迭代器
template <class T,class Ref,class Ptr>
struct List_iterator
{typedef List_Node<T> Node;typedef List_Node<T>* pNode;typedef List_iterator<T, Ref, Ptr> Self;pNode _Node;List_iterator(Node* node):_Node(node){}//迭代器具有像指针一样的行为，可以解引用Ref operator*(){return _Node->_data;}//指针可以通过->访问其所指空间成员，因此迭代器类中必须重载oprator->()Ptr operator->(){return &_Node->_data;}//迭代器可以++//前置++Self& operator++(){_Node = _Node->_next;return *this;}//后置++Self operator++(int){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;}//迭代器支持比较bool operator!=(const Self& it){return _Node != it._Node;}bool operator==(const Self& it){return _Node == it._Node;}};

这样我们在list实例化时，传入对应的参数,list_iterator就能实例化出不同的迭代器版本。

🚩<list>迭代器使用

//传参来控制const迭代器和非const迭代器
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);
}

这里通过传参来控制const迭代器和非const迭代器，以构造匿名对象的形式来作为返回值，更简洁，也更好。

🚩insert操作

此处在pos位置和双链表中插入元素的逻辑一样，只不过pos此时是用迭代器封装的。

//insert后pos位置迭代器失效·
void insert(iterator pos, const T& x)
{pNode newnode = new Node(x);//prev newnode curpNode cur = pos._Node;pNode prev = cur->_prev;prev->_next = newnode;newnode->_next = cur;newnode->_prev = prev;cur->_prev = newnode;++_size;//pos = iterator(newnode);//如果想继续使用，更新pos位置的迭代器
}

注意:这里插入操作，pos位置的迭代器并没有失效，只不过逻辑上在下一个位置了，如果需要让pos指向新插入的节点，可以显式地更新它，如 pos = iterator(newnode);

iterator(newnode)是构造一个新的迭代器匿名对象，并将其赋值给 pos。

🚩erase操作

erase pos位置后，pos位置的迭代器被删除了，即失效了，不能继续使用。不过erase后，返回下一个元素位置的迭代器。

	iterator erase(iterator pos){pNode cur = pos._Node;pNode next = cur->_next;pNode prev = cur->_prev;prev->_next = next;next->_prev = prev;delete cur;--_size;return iterator(next);//返回下一个元素的迭代器}

✅代码解析:

实现方式和双向带头循环带头链表删除某个pos节点是一样的。

对比一下<vector> <list>insert和erase操作后迭代器失效问题:

<vector>insert操作，数据可能需要扩容，那么指向pos位置的迭代器就失效了；而<list>insert操作，pos位置的迭代器没有删除，只是逻辑上发生了变化，因此没有失效;

<vector><list>erase操作由于pos位置迭代器都删除了，因此都失效了。不过，erase后，都要返回下一个元素位置的迭代器。

🚩增删

有了insert和erase后，头插头删，尾插尾删都很方便。

void push_back(const T& x){insert(end(), x);}void pop_back(){erase(--end());}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}

我们需要注意的是，<vector>中，没有对头部的操作，因为要挪动数据，效率很低。

🚩list构造

我们这里实现一下分别实现拷贝构造，赋值运算符重载，以及用一段迭代器区间构造，和initializer_list的构造

void empty_init()
{_head = new Node(-1);_head->_next = _head;_head->_prev = _head;
}//拷贝构造
//lt2(lt1)
list(const list<T>& it)
{empty_init();for (auto& e : it){push_back(e);}
}void swap(list<T>& it){std::swap(_head, it._head);std::swap(_size, it._size);}
//赋值运算符重载list<T>& operator=(list<T> it){swap(it);return *this;}template <class InputIterator>
list(InputIterator first, InputIterator last)
{empty_init();while (first != last){push_back(*first);first++;}
}list(initializer_list<T> il)
{empty_init();for (auto& e : il){push_back(e);}
}

✅代码解析:

拷贝构造先调用empty_init为*this开辟头结点，再直接尾插。

有了拷贝构造就可以直接写赋值赋值运算符重载。

用一段迭代器区间构造，我们来遍历这段迭代器区间，然后完成尾插工作。

initializer_list调用empty_init为this开辟头结点，再拿il中的元素进行尾插。

🚩析构函数

析构函数是对有资源的对象完成销毁和清理工作.

明确一下，此处有资源的包括每个节点，以及头结点。

void clear()
{iterator it = begin();while(it != end()){it = erase(it);//erase后更新迭代器，防止迭代器失效;it++;}
}~list()
{clear();delete _head;_head = nullptr;
}

✅代码解析:

先释放<list>类对象中头结点后的所有元素，最后，释放头结点。

🚩反向迭代器实现⭐️ 

 首先我们来了解一下适配器的概念:

适配器（Adapter）是一个设计模式，用于解决两个不兼容接口之间的兼容性问题。适配器模式允许你通过创建一个适配器类来“转换”一个类的接口，使其能够与另一个类的接口兼容。

简单可以理解成类模版之间的复用

而我们已经实现了正向迭代器，反向迭代器的行为跟正向迭代器没有什么不同，解引用可以取元素，迭代器++,--支持移动。无非就是反向迭代器的++是正向迭代器的--,反向迭代器的--是正向迭代器的++，逻辑上是相反的。

因此我们可以使用正向迭代器作为适配器，来适用于反向迭代器的实现。

我们先简单实现一下👉:

#pragma oncetemplate<class Iterator,class Ref,class Ptr>struct Reverse_iterator{typedef Reverse_iterator<Iterator, Ref, Ptr> Self;Reverse_iterator(Iterator it):_it(it){}//迭代器支持解引用/*Ref operator*(){return *_it;}*///返回前一个元素的值Ref operator*(){Iterator tmp = _it;tmp--;return *tmp;}Ptr operator->(){return &(operator*());}//迭代器支持移动Self& operator++(){--_it;return *this;}Self operator++(int){Self tmp(*this);--_it;return tmp;}Self& operator--(){++_it;return *this;}Self operator--(int){Self tmp(*this);++_it;return tmp;}//迭代器支持比较bool operator==(const Self& it){return _it == it._it;}bool operator!=(const Self& it){return _it != it._it;}Iterator _it;
};

反向迭代器的成员变量是<iterator>类型，用<iterator>作为适配器。

调用只需要调用适配器的接口，只需要注意逻辑上方向的问题，反向迭代器的++是正向迭代器的--。

这里有个问题，就是为什么反向迭代器解引用是访问前一个数据❓

这里设计本质是希望对称，即你的end()是我的rbegin()，你的begin()是我的rend() 

因此这样从rbegin开始遍历，由于第一个位置是头结点，只能访问前面一个元素，也就是4，然后3,2,1，直到rbegin==rend

因此我们有了反向迭代器，对所有容器都可以使用，前提是只要提供了它的正向迭代器，我们拿它的正向迭代器适配出对应的反向迭代器。

因此在<list>中，我们构造出反向迭代器的rbegin(),rend()const和非const版本。

//反向迭代器
typedef Reverse_iterator< iterator, T&, T*> reverse_iterator;
typedef Reverse_iterator< const_iterator, const T&, const T*> const_reverse_iterator;reverse_iterator rbegin()
{return reverse_iterator(end());
}reverse_iterator rend()
{return reverse_iterator(begin());
}const_reverse_iterator rbegin() const
{return const_reverse_iterator(end());
}const_reverse_iterator rend() const
{return const_reverse_iterator(begin());
}

<list>中传入模版参数，Reverse_iterator这样实例化。其中第一个参数以iterator作为适配器。

 🐼全部源码

list.h👇👇

#pragma once#include<iostream>
#include<list>
#include"iterator.h"
using namespace std;namespace lsg
{//定义节点结构template<class T>struct List_Node{List_Node<T>* _next;//指向下一个节点的指针List_Node<T>* _prev;//指向前一个节点的指针T _data;List_Node(const T& x = T()):_next(nullptr),_prev(nullptr),_data(x){}};两个迭代器版本(高度相似)//template <class T>//struct List_iterator//{//	typedef List_Node<T> Node;//	typedef List_Node<T>* pNode;//	//	pNode _Node;//	List_iterator(Node* node)//		:_Node(node)//	{}//	T& operator*()//	{//		return _Node->_data;//	}//	//前置++//	List_iterator<T>& operator++()//	{//		_Node = _Node->_next;//		return *this;//	}//	//后置++//	List_iterator<T> operator++(int)//	{//		List_iterator<T> tmp = *this;//		_Node = _Node->_next;//		return tmp;//	}//	//	bool operator!=(const List_iterator<T>& it)//	{//		return _Node != it._Node;//	}//	T* operator->()//	{//		return &_Node->_data;//	}//};//template <class T>//struct const_List_iterator//{//	typedef List_Node<T> Node;//	typedef List_Node<T>* pNode;//	pNode _Node;//	const_List_iterator(Node* node)//		:_Node(node)//	{}//	const T& operator*() const//	{//		return _Node->_data;//	}//	//前置++//	const_List_iterator<T>& operator++() //	{//		_Node = _Node->_next;//		return *this;//	}//	const_List_iterator<T> operator++(int) //	{//		List_iterator<T> tmp = *this;//		_Node = _Node->_next;//		return tmp;//	}//	bool operator!=(const const_List_iterator<T>& it)//	{//		return _Node != it._Node;//	}//	const T* operator->() const//	{//		return &_Node->_data;//	}//};//用模版方法来控制const和非const迭代器template <class T,class Ref,class Ptr>struct List_iterator{typedef List_Node<T> Node;typedef List_Node<T>* pNode;typedef List_iterator<T, Ref, Ptr> Self;pNode _Node;List_iterator(Node* node):_Node(node){}//迭代器具有像指针一样的行为，可以解引用Ref operator*(){return _Node->_data;}//指针可以通过->访问其所指空间成员，因此迭代器类中必须重载oprator->()Ptr operator->(){return &_Node->_data;}//迭代器可以++//前置++Self& operator++(){_Node = _Node->_next;return *this;}//后置++Self operator++(int){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;}//迭代器支持比较bool operator!=(const Self& it){return _Node != it._Node;}bool operator==(const Self& it){return _Node == it._Node;}};template<class T>class list{typedef List_Node<T> Node;typedef List_Node<T>* pNode;public:/*	typedef List_iterator<T> iterator;typedef const_List_iterator<T> const_iterator;*///传参来控制const迭代器和非const迭代器typedef List_iterator<T,T&,T*> iterator;typedef List_iterator<T,const T&,const T*> const_iterator;//反向迭代器typedef Reverse_iterator< iterator, T&, T*> reverse_iterator;typedef Reverse_iterator< const_iterator, const T&, const T*> const_reverse_iterator;reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rbegin() const{return const_reverse_iterator(end());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}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);}void empty_init(){_head = new Node(-1);_head->_next = _head;_head->_prev = _head;}list(){empty_init();_size = 0;}void clear(){iterator it = begin();while(it != end()){it = erase(it);//erase后更新迭代器，防止迭代器失效;it++;}}~list(){clear();delete _head;_head = nullptr;}//拷贝构造//lt2(lt1)list(const list<T>& it){empty_init();for (auto& e : it){push_back(e);}}list(initializer_list<T> il){empty_init();for (auto& e : il){push_back(e);}}template <class InputIterator>list(InputIterator first, InputIterator last){empty_init();while (first != last){push_back(*first);first++;}}void swap(list<T>& it){std::swap(_head, it._head);std::swap(_size, it._size);}list<T>& operator=(list<T> it){swap(it);return *this;}/*void push_back(const T& x){pNode newnode = new Node(x);pNode tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;_head->_prev = newnode;newnode->_next = _head;}*/void push_back(const T& x){insert(end(), x);}void pop_back(){erase(--end());}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}size_t size() const{return _size;}//insert后pos位置迭代器失效·void insert(iterator pos, const T& x){pNode newnode = new Node(x);//prev newnode curpNode cur = pos._Node;pNode prev = cur->_prev;prev->_next = newnode;newnode->_next = cur;newnode->_prev = prev;cur->_prev = newnode;++_size;//pos = iterator(newnode);//如果想继续使用，更细pos位置的迭代器}iterator erase(iterator pos){pNode cur = pos._Node;pNode next = cur->_next;pNode prev = cur->_prev;prev->_next = next;next->_prev = prev;delete cur;--_size;return iterator(next);//返回下一个元素的迭代器}private:pNode _head;size_t _size;};
}

Reverse_iterator.h👇👇

#pragma oncetemplate<class Iterator,class Ref,class Ptr>struct Reverse_iterator{typedef Reverse_iterator<Iterator, Ref, Ptr> Self;Reverse_iterator(Iterator it):_it(it){}//迭代器支持解引用/*Ref operator*(){return *_it;}*///返回前一个元素的值Ref operator*(){Iterator tmp = _it;tmp--;return *tmp;}Ptr operator->(){return &(operator*());}//迭代器支持移动Self& operator++(){--_it;return *this;}Self operator++(int){Self tmp(*this);--_it;return tmp;}Self& operator--(){++_it;return *this;}Self operator--(int){Self tmp(*this);++_it;return tmp;}//迭代器支持比较bool operator==(const Self& it){return _it == it._it;}bool operator!=(const Self& it){return _it != it._it;}Iterator _it;
};

🐼总结

通过<list>的认识以及模拟实现，加深了我们对迭代器的认识，迭代器支持++.--，比较，解引用,随机访问等等操作，我们知道了迭代器行为是像指针一样的东西，迭代器提供了一种统一的方式来访问容器中的元素，而无需关心容器的具体实现细节，在<list>中我们专门封装了一个iterator类来模拟迭代器的行为。

而介绍了适配器后，我们通过正向迭代器<iterator>来适配出反向迭代器<Reverse_iterator>类，通过类模版之间的复用实现了两个不同接口的兼容性。

我们也更加感受到了函数模版的魅力，通过模版参数，来减少很多逻辑上重复的代码，比如const对象和非const对象迭代器的实例化，我们控制实参，就能实例化出权限不同的迭代器版本。

感谢你耐心地阅读到这里，你的支持是我不断前行的最大动力。如果你觉得这篇文章对你有所启发，哪怕只是一点点，那就请不吝点赞👍，收藏⭐️，关注🚩吧！你的每一个点赞都是对我最大的鼓励，每一次收藏都是对我努力的认可，每一次关注都是对我持续创作的鞭策。希望我的文字能为你带来更多的价值，也希望我们能在这个充满知识与灵感的旅程中，共同成长，一起进步。再次感谢你的陪伴，期待与你在未来的文章中再次相遇！⛅️🌈 ☀️