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