【C＋＋STL】list的详细用法和底层实现

🌟个人主页：第七序章

🌈专栏系列：C＋＋

❄️前言：

🌈一：介绍

🌈二：list的创建

☀️基本框架

🌙节点类

🌙构造函数：

☀️list类

🌙构造函数

🌙拷贝构造函数

🌙赋值重载

🌙析构函数

☀️++运算符重载

🌙- -运算符的重载

🌙==运算符重载

🌙!=运算符的重载!=运算符的重载

🌙*运算符的重载

🌙->运算符的重载

☀️迭代器相关函数

☀️插入和删除函数

🌙insert

🌙erase函数

🌙push_fron, pop_back, pop_front

☀️其他函数

🌙size函数

🌙clear函数

🌙swap函数

☀️list的sort vs 库的sort

🌙vector和list的排序效率

☀️从迭代器类重新理解封装

🌻共勉:

❄️前言：

上一篇我们学习了C＋＋STL库vector的详细用法，今天我们来学习一下list的详细用法和底层实现。

🌈一：介绍

⭐list是一种序列式容器(带头双向循环链表)。该容器的底层是用双向链表实现的, 在链表的任一位置进行元素的插入、删除操作都是快速的。

🌈二：list的创建

☀️基本框架

🌙节点类

template<class T>
struct list_node
{T _data;list_node<T>* _next;list_node<T>* _prev;
};

🌙构造函数：

template<class T>
struct list_node
{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& x = T())	//别忘了写缺省参数:_data(x),_next(nullptr),_prev(nullptr){}
};

⭐这里我们就用初始化列表对链表节点对象进行初始化，对节点存储的值用匿名对象进行缺省参数赋值。前后节点指针初始化为空指针
⭐这里的匿名对象对于自定义类型会去调用他们的默认构造来初始化，内置类型也有构造函数就是int，float,double是0

☀️list类

🌙构造函数

void empty_init()
{_head = new Node(); //调用构造函数，创造节点初始化,链表是一个个节点连接起来_head->_next = _head;_head->_prev = _head;	//带头双向循环
}

⭐我们实现一个成员函数来初始化哨兵位节点

这里补充一下_head, 是链表的哨兵位节点

private:Node* _head;

⭐构造函数直接调用这个初始化函数就行了

list()
{empty_init();
}

🌙拷贝构造函数

		list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}

⭐在string和vector两个容器里面我已经详细讲解了拷贝构造的要求，最重要的就是要完成深拷贝。这里我们就用了push_back这个接口来完成深拷贝。

	void push_back(const T& x){Node* new_node = new Node(x); //new 可以开空间，也能调用构造函数初始化Node* tail = _head->_prev;tail->_next = new_node;new_node->_prev = tail;new_node->_next = _head;_head->_prev = new_node;	//改成_head->_prve就没有问题了_size++;}

⭐可以看到我们的push_back函数用new开了新空间，并且把对应的指针指向了新空间，这就完成了深拷贝。
⭐或许有同学疑问，为啥这_head->_prev = new_node;不写成tail = new_node
原因就是tail是一个指针变量，我们改变指针变量的值是不能改变指针变量指向的值的。

⭐所以改变tail并不能改变_head->_prev,这里我面的本意是想把_head->_prev这个指针的指向改变

🌙赋值重载

	list<T>& operator=(list<T> lt){swap(lt);return *this;}

⭐还记得我在前面两章说vector和string的赋值重载的时候吗，资本家思想。如果我想要得到lt的并且想扔掉原来的资源，只需要把swap一下，lt这个局部变量在调用完这个函数就会销毁。因为我现在已经把原来this的资源交换给了lt, 所以销毁lt就相当于销毁了原来this指向的资源。

🌙析构函数

	~list(){clear();delete _head;_head = nullptr;}

⭐这里我们直接先提前看一下clear的内部实现，来了解析构函数

		void clear(){auto it = begin();while (it != end()){it = erase(it);}}

⭐可以看到就是从头结点删除到尾节点，这里的erae方法后面介绍
⭐所以析构的时候我们就只需要delete一下哨兵节点就行了

☀️++运算符重载

Self& operator++()
{_node = _node->_next;return *this;
}

⭐从链表节点的类中我们知道节点的下一个节点的位置是用一个_next成员变量指针指向的，所以指向那个位置就行了。

⭐这就是一个后置++的实现，接下来我们实现前置++

	Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}

⭐这里我们就是返回自增之前的那个对象
⭐解释下Self的类型，其实就是迭代器对象的类型

typedef list_iterator<T, Ref, Ptr> Self;

🌙- -运算符的重载

		Self& operator--(){_node = _node->_prev;return *this;}

⭐和++相反，++是找到后面的那个节点，而–就是找到前面那个节点。

		Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}

⭐前置- - 同上面前置++

🌙==运算符重载

bool operagor == (const Self & s)
{return _node == s._node;
}

⭐判断两个节点指针指向的地址是否相同即可

🌙!=运算符的重载!=运算符的重载

⭐!=运算符刚好和==运算符的作用相反，我们判断这两个迭代器当中的结点指针的指向是否不同即可

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

🌙*运算符的重载

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

⭐返回节点指针的存储数据的成员变量_data就可以了
⭐这里的Ref是引用的类型，模板推导出来的引用类型

🌙->运算符的重载

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

☀️迭代器相关函数

	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);}

⭐这里只需要把节点传给我们的迭代器类构造一个迭代器对象就可以获得头节点和尾部的迭代器。

☀️插入和删除函数

🌙insert

iterator insert(iterator pos, const T& val)
{Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(val);newnode->_next = cur;newnode->_prev = prev;prev->_next = newnode;cur->_prev = newnode;_size++;return iterator(newnode);}

⭐这里插入很easy，只需要把插入的新节点前后指针更新到对应的指针就行了

⭐注意这里插入不存在迭代器失效的问题，因为我们的扩容都是一个个独立的空间，不存在像vector那样扩容后会导致迭代器无法找到新开的空间，这里的迭代器是通过指针来找到空间的

🌙erase函数

	iterator erase(iterator pos){assert(pos != end()); //注意这里是给end， pos是迭代器的类型对象Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;next->_prev = prev;prev->_next = next;delete cur;_size--;return iterator(next);}

注意：这里释放节点就要注意迭代器失效的问题了，我们删除后，指向这个节点的迭代器指向的就是一个无效的内存，这时候就需要更新这个迭代器让他指向有效的内存。

🌙push_fron, pop_back, pop_front

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

复用insert和erase接口就行，push_front就是insert到头结点位置，pop_front就是删除头结点位置，pop_back则是删除end(end是最后一个节点的下一个节点)前一个位置

☀️其他函数

🌙size函数

size_t size() const
{return _size;
}

我们通过，一个成员变量来实现，如果链表插入节点的时候就自增_size,删除节点的时候就自减_size,可以看看前面的插入和删除函数

🌙clear函数

	void clear(){auto it = begin();while (it != end()){it = erase(it);}}

析构函数哪里前面已经解释过

🌙swap函数

		void swap(list<T>& tmp){std::swap(_head, tmp._head);}

这里ist容器当中存储的实际上就只有链表的头指针，我们就交换两个变量的头结点就行了，就让他们交换了数据，
这里我们还重载了一个全局的swap函数

template<class T>
void swap(list<T>& a, list<T>& b)
{a.swap(b);
}

⭐为了防止使用算法库中的i那个很多拷贝构造的swap函数，我们重载一个全局函数通过模板有现成吃现成(两个链表类型的变量，相同的类型)，会优先匹配我们自己实现的swap函数，然后我们这个全局的函数又调用成员函数swap,这个效率比算法库的那个效率高很多，为啥效率高，请看前面两个容器的讲解很详细。

☀️list的sort vs 库的sort

List为啥要自己实现一个sort函数来排序，不能直接用算法库中的sort吗？
1.不能，因为我们的迭代器按功能角度来分类有3种:
⭐(1)单向迭代器（支持++) 例如:foward_list(单链表)
⭐(2)双向迭代器(支持++.–)， list
⭐(3)随机迭代器(支持++,–, +, -) string,vector

⭐注意：算法库中的是必须要是随机迭代器，而我们 list 实际上是一个带头双向链表，只能用双向迭代器，那么就不能传给算法库中的 sort。随机迭代器就兼容单向和双向迭代器，相当于是一个包含关系。

🌙vector和list的排序效率

⭐我们第一组数据是vector用算法库sort和list用他的成员函数sort单独排序，第二组数据是list的数据拷贝到vector给算法库的sort排序和list用他的成员函数sort单独排序
⭐可以看到copy到vector给算法库的sort排序都比list的sort快

原因：
⭐链表这个不连续的结构并不适合大量数据的排序，他的索引访问不能像vector那样连续的索引访问那么高效，需要更多时间来找到索引位置
⭐算法库中的sort是快速排序算法，list的sort用的是归并排序，快速排序还是比归并排序要厉害一点的。

⭐想要更高的效率排序，最好拷贝到vector中排序，排完再拷贝回list

☀️从迭代器类重新理解封装

⭐大家可以看到我们的迭代器类实际上是一个

	struct list_iterator

⭐在类外是可以访问的，虽然在类外是可以访问，但是我们通过对迭代器类重命名

	typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;

⭐提供了类外统一用iterator来访问的方式，这样外面并不知道我实际是什么名字，并不能很好的猜出来，可以看到我们stl中容器的迭代器都是统一命名为iterator, 但是每个容器的迭代器的底层细节实现方式可能都有差异，但是用户都可以通过iterator来访问各个容器，只能通过我给的接口访问，这就是一个隐式的封装。
⭐为啥要写成struct,就是为了方便类里面对他的高频访问的问题。如迭代器函数begin,插入insert

⭐举个通俗例子：
想象你开车时，只需要操作方向盘、油门和刹车等控制系统，来控制车子的前进和停止。这些操作背后涉及了复杂的机械结构、发动机和电控系统等内部实现，但你作为司机并不需要了解这些内部细节，只需要通过车内的接口（方向盘、油门、刹车等）来进行控制。

在这个例子中：

车子就是对象，封装了车的内部组件（发动机、轮胎、刹车系统等）。
方向盘、油门和刹车是暴露出来的接口，司机通过这些接口与车子互动。
司机不需要知道发动机如何工作或者刹车是如何控制的，这些细节被隐藏了。

同样，封装在编程中通过类和方法来实现，外界使用对象时，只需要调用公开的接口（方法），而不需要关心类的内部实现。