当前位置：首页 > news >正文

C++_list

news 2026/7/27 8:06:53

1.引言：

2.list的介绍与使用

2.1.list的介绍

2.2.list的使用

构造

析构

赋值运算符重载

迭代器

容量相关接口

元素访问

对象修改

专属接口

splice

remove

remove_if

unique

merge

sort

拓展：仿函数

reverse

3.list模拟实现

3.1.list源码观察

3.2.list模拟实现

迭代器初步实现

代码重构

insert

push_back和push_front

析构

erase

pop_back和pop_front

->运算符重载

const迭代器初步实现

迭代器优化

迭代器失效

clear

赋值运算符重载

源码

拓展

5.结语

1.引言：

这篇讲list的使用和模拟实现，在学list前，需要掌握这些内容

C++_类和对象（上）-CSDN博客
C++_类和对象（中）-CSDN博客
C++_类和对象（下）-CSDN博客
C++_模板初阶-CSDN博客
C++_内存管理_c++内存管理要如何做-CSDN博客

那么话不多说直接进入正文——————>

2.list的介绍与使用

2.1.list的介绍

list容器和我们先前讲的vector容器一样，都是模板，list底层涉及的数据结构就是链表，我们还是照着这个文档进行讲解，顺序依旧是能用，明理，能扩展list - C++ Reference

在讲list之前，我先讲下list结构，因为链表有很多种，list底层的链表是带哨兵位的双向循环链表，这个我会在看list底层的时候也讲

2.2.list的使用

经过string和vector的讲解和模拟实现，其实现在看list可以发现很多接口基本都知道是实现什么功能的了，所以这边我就一个个快速过下去了

构造

这构造就和vector一样的四种构造，第一个是默认构造，第二个是构造同时插入n个数据为val的对象，第三个就是迭代器构造，构造同时插入[first,last)这些位置的对象，第四个就是拷贝构造，没什么好说的

析构

赋值运算符重载

迭代器

这些迭代器就正向反向const，跟之前的也都一样，过一眼就好

注意：这里需要注意的是，从list开始，遍历就不能用【】+下标的遍历方式了，因为从list往后的那些容器全都不是顺序表了，那么，这个时候如果用[]+下标遍历的话，成本会很高，就比如说从begin()到end()的所有数据输出一遍，vector和string的时间复杂度是O(N)，但是如果这种非顺序表的话时间复杂度就会到O(N^2)了，因为比如链表想找第10个数据，那就要从头往后跳10次，，因为成本太高了，所以从list就没有operator[]重载，我们看如下图，他是这么跳的

这里的迭代器其实就和我们先前讲的vector，string的迭代器不一样了，因为这不是连续的空间，所以list的迭代器就肯定不是原生指针了，迭代器其实有三种，我们先前所讲的vector和string的迭代器是属于随机迭代器，而list是双向迭代器

单向迭代器：forward_list、unordered_map、unordered_set 支持++

双向迭代器： list、map、set... 支持++,--

随机迭代器：vector、string、deque.. 支持++,--,+,-

迭代器的性质是由底层的结构决定的，我们可以在这里看容器的迭代器是哪个类型的

容量相关接口

因为链表是一个个插入，想插入时候就创建个新对象，然后更新下指向就好了，所以链表和vector，string这种不一样，没有扩容的概念，所以这里接口不多，empty()就是判空，size()就是返回有几个数据，max_size返回可行最大容量，这也快速过了

元素访问

list的元素直接访问就只能获取到头和尾，也就是这俩个接口，这俩个返回的是引用，也就是可以修改

对象修改

这些接口全在前面讲过了，这里就看一眼过就行

拓展：这里讲下emplace相关接口的用法

拿emplace_back举例，这个和push_back相比在某些场景下会更高效，就如下面代码

#include <iostream> #include <list> using namespace std; struct A { A(int a1 = 1, int a2 = 1) :_a1(a1) , _a2(a2) { cout << "A(int a1 = 1, int a2 = 1)" << endl; } A(const A& x) { _a1 = x._a1; _a2 = x._a2; cout << "A(const A& x)" << endl; } ~A() { cout << "~A()" << endl; } private: int _a1; int _a2; }; int main() { list<A> lt; A aa1(1, 1); lt.push_back(aa1); lt.push_back(A(2,2)); lt.push_back(2, 2); lt.emplace_back(aa1); lt.emplace_back(A(2,2)); lt.emplace_back(2, 2); }

我们可以发现，如果用push_back,传2，2是会报错的，但是emplace_back不会，如下图

emplace_back可以拿值直接传过去构造，就会少一次拷贝构造，这就是emplace_back的优势，如下图

如果我们要传A类型的2,2的话，用emplace_back就不用像push_back一样传匿名对象了，直接传值就行了，传匿名对象会有构造和拷贝构造，但是传值的话他会只有一次构造，就提高了很多效率

这里只要了解就行，具体会在C++11部分讲

专属接口

splice

这个接口的作用是转移数据

第一条——把x内的所有节点全部转移到pos位置之前

第二条——把x内迭代器 i 所指向位置的单个节点转移到pos位置之前

第三条——把x的迭代器指向从[first,last）的所有元素全部转移到pos位置之前

注意：转移之后原先那些就全消除了，就比如第一条转移完，x就为空了

这个接口还可以调整自己链表的位置顺序

remove

这个接口就是用来删除数据

找val删，找到就删除，找不到也不会报错

注意：他是从头遍历到尾，所以如果有多个val，他会全部删除

remove_if

这个接口就是配合一个条件进行删除（这个得传仿函数，全局函数，静态函数或者匿名lambda），现在了解就行，不用会用

unique

这个接口的功能是去重，去重的前提也是链表要有序

merge

这个接口的功能是将俩个链表进行合并，链表合并的前提是俩个链表必须是有序的，这个合并的底层原理其实就是取小的尾插

需要注意的是，比如lt1.merge(lt2)，这就是lt2合并到lt1去了，这个时候lt2其实就空了，这里需要注意

sort

算法库里也是有sort的，但是算法库的sort底层是快排，堆排，三路划分的融合，这些都要基于顺序表才可以实现，所以算法库的sort只能接收随机迭代器，所以list无法用算法库的sort实现排序功能，我们可以看下算法库的sort

这个类型名是RandomAccess，也就是随机，即代表随机迭代器，那自然是不支持双向迭代器的

所以，list自己实现了一个sort，这个sort和算法库实现的sort效果一样，默认就是升序排序，但是 list的sort接口的底层是通过归并排序实现的（数据量大的情况下不要用list的排序，效率很低，可以先拷贝给vector排完序再拷贝回来）

拓展：仿函数

那么如果想要降序排序的话就要用到仿函数（仿函数就是重载了括号运算符-operator()的类的实例化），这里就教怎么用，首先有俩个类模板，less和greater，less就是用来排升序的，greater就是用来排降序的，样例如下

#include <iostream> #include <list> #include <algorithm> using namespace std; void test3() { list<int> lt; lt.push_back(2); lt.push_back(1); lt.push_back(3); lt.push_back(0); lt.push_back(5); less<int> ls; greater<int> lg; lt.sort(ls);//升序 for (auto x : lt) cout << x << " "; cout << endl; lt.sort(lg);//降序 for (auto x : lt) cout << x << " "; cout << endl; } int main() { test3(); }

那既然是类，自然就可以写匿名对象了,比如这样

lt.sort(greater<int>());//降序

reverse

这个reverse的效果就和算法库（algorithm）里的那个reverse实现效果一样，就是逆置，我们看算法库的reverse，如下图

算法库中的reverse是个函数模板，Bidirectional就是双向，也就是说，我们可以通过类型名来推断他支持什么，这个明显就是支持双向迭代器，既然支持双向迭代器，自然也就支持随机迭代器。那么list的迭代器是双向迭代器，调用这个就可以完成list的逆置了，我们可以俩个reverse都测一下

#include <iostream> #include <list> #include <algorithm> using namespace std; void test2() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); for (auto x : lt) cout << x << " "; cout << endl; lt.reverse(); for (auto x : lt) cout << x << " "; cout << endl; reverse(lt.begin(), lt.end()); for (auto x : lt) cout << x << " "; cout << endl; } int main() { test2(); }

运行可以发现都是没问题的

注意：虽然这俩个reverse实现的效果一样，但是底层效率而言是完全不一样的，算法库里的reverse是交换俩个迭代器的数据，而list里自己实现的reverse是直接交换next和prew指针（指向前一个和后一个的指针）。这么一看其实效率就天差地别了，所以其实这个reverse设计不冗余

3.list模拟实现

3.1.list源码观察

这边扒源码的方式就和vector部分看源码的方式一样，也是在那个文件夹里

我们先找到list打开

核心的毋庸置疑就是stl_list.h，我们找到这个文件去打开

我们先找到list类

我们可以发现，这个类内的成员变量就一个，那就是node

然后这个link_type是什么类型呢，我们跳转过去看，我们可以发现是list_node*类型

接下来我们再去看list_node是什么类型，可以发现是__list_node<T>类型的

接下来我们接着跳转

所以，node其实就是指向__list_node<T>对象的指针，我们可以通过图来理解这几个命名关系

我们观察__list_node类模板，可以发现，里面有三个成员，data存数据，next指向下一个节点，prev指向上一个节点

接下来，我们来看下list的构造

因为是默认构造，此时list内部还没有结构，所以node->next和node->prev都指向自己，我们再看get_node()内部

这其实就是向空间配置器申请一块内存，用来新建节点（其实就和我们上次实现vector的时候用裸内存定位new的方式中裸内存一样，就是给你一块裸空间，不创建对象）

这个节点的data成员并没有赋值，所以我们可以猜想这个可能会作为哨兵位，接下来，我们来看下push_back

首先push_back会调用insert

随后iinsert一开始进去会新创建一个节点，这个节点是通过create_node得到的，create_node就是像空间配置器申请一块空间后，调用construct函数来给p->data初始化（construct先前vector部分我们讲过，里面就是定位new初始化）

然后初始化完后就返回p给tmp接收，随后在更新prev和next的指向

其实从这里，我们就能看出list底层实现的时候是带有哨兵位的，我们通过图来更清晰的看

那么知道list的成员变量，知道list的链表是带哨兵位的双向循环链表后，我们就可以开始模拟实现list了

3.2.list模拟实现

这里我们依旧创建一个头文件——list.h

接下来，我们先搭个简单的结构之后再修改润色，这边我为了方便多加了个_size来统计节点个数

#pragma once #include <iostream> namespace qiu { template<class T> struct list_node { T data; list_node<T>* next; list_node<T>* prev; }; template<class T> class list { public: typedef list_node<T>* iterator; typedef const list_node<T>* const_iterator; void push_back(const T& x); list() :_size(0) { node = (iterator)::operator new(sizeof(list_node<T>)); node->next = node; node->prev = node; } size_t size() const { return _size; } bool empty() const { return size() == 0; } iterator begin() { return node->next; } iterator end() { return node; } const_iterator begin() const { return node->next; } const_iterator end() const { return node; } private: iterator node; size_t _size; }; template<class T> void list<T>::push_back(const T& x) { iterator new_node = (iterator)::operator new(sizeof(list_node<T>)); new_node->data = x; iterator old_node = node->prev; new_node->prev = old_node; new_node->next = node; old_node->next = new_node; node->prev = new_node; ++_size; } }

接下来，我们测试一下，没有什么大问题

#define _CRT_SECURE_NO_WARNINGS #include "list.h" int main() { qiu::list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); qiu::list<int>::iterator it = lt.begin(); while (it != lt.end()) { std::cout << it->data << " "; it = it->next; } return 0; }

在上面，我们虽然用迭代器成功遍历了list，但是list是有++，解引用重载这些的，但是list内部的成员变量存的是我们这个链表的哨兵位，这是不能改的，那么，我们就需要为了迭代器，在外部实现一个类，如下

迭代器初步实现

template<class T> struct list_iterator { typedef list_node<T>* Node; typedef list_iterator<T> iterator; list_iterator(Node _node) :node(_node) { } iterator& operator++() { node = node->next; return *this; } iterator operator++(int) { iterator _node(node); node = node->next; return _node; } iterator& operator--() { node = node->prev; return *this; } iterator operator--(int) { iterator _node(node); node = node->prev; return _node; } T& operator*() { return node->data; } bool operator!=(const iterator& it) const { return node != it.node; } bool operator==(const iterator& it) const { return node == it.node; } Node node; };

那么，我们上面所写的简单的结构就可以重构变成如下代码

代码重构

#pragma once #include <iostream> namespace qiu { template<class T> struct list_node { T data; list_node<T>* next; list_node<T>* prev; }; template<class T> struct list_iterator { typedef list_node<T>* Node; typedef list_iterator<T> iterator; list_iterator(Node _node) :node(_node) { } iterator& operator++() { node = node->next; return *this; } iterator operator++(int) { iterator _node(node); node = node->next; return _node; } iterator& operator--() { node = node->prev; return *this; } iterator operator--(int) { iterator _node(node); node = node->prev; return _node; } T& operator*() { return node->data; } bool operator!=(const iterator& it) const { return node != it.node; } bool operator==(const iterator& it) const { return node == it.node; } Node node; }; template<class T> class list { public: typedef list_node<T>* Node; typedef list_iterator<T> iterator; void push_back(const T& x); list() :_size(0) { node = (Node)::operator new(sizeof(list_node<T>)); node->next = node; node->prev = node; } size_t size() const { return _size; } bool empty() const { return size() == 0; } iterator begin() { return iterator(node->next); } iterator end() { return iterator(node); } private: Node node; size_t _size; }; template<class T> void list<T>::push_back(const T& x) { Node new_node = (Node)::operator new(sizeof(list_node<T>)); new (&new_node->data) T(x); Node old_node = node->prev; new_node->next = node; new_node->prev = old_node; old_node->next = new_node; node->prev = new_node; ++_size; } }

insert

template<class T> typename list<T>::iterator list<T>::insert(iterator pos, const T & x) { Node new_node = (Node)::operator new(sizeof(list_node<T>)); new (&new_node->data) T(x); new_node->next = pos.node; new_node->prev = pos.node->prev; new_node->next->prev = new_node; new_node->prev->next = new_node; ++_size; return new_node; }

insert实现后，我们其实push_back和push_front就可以复用这块代码了，能减少很多重复代码

push_back和push_front

template<class T> void list<T>::push_back(const T& x) { insert(end(), x); } template<class T> void list<T>::push_front(const T& x) { insert(begin(), x); }

析构

因为我们采用的方式是operator new加定位new，只构造了data对象，所以我们只需要自己手动销毁data的那块数据即可，所以在节点层面，我们不用写析构函数来销毁节点数据，只需要在list地方写个析构函数来销毁节点即可，代码如下

~list() { while (!empty()) pop_back(); ::operator delete(node); }

erase

template<class T> typename list<T>::iterator list<T>::erase(iterator pos) { assert(pos != end()); iterator it = pos.node->next; pos.node->prev->next = pos.node->next; pos.node->next->prev = pos.node->prev; pos.node->data.~T(); ::operator delete(pos.node); --_size; return it; }

erase实现好了后，尾删头删也就没问题了

pop_back和pop_front

template<class T> void list<T>::pop_back() { erase(node->prev); } template<class T> void list<T>::pop_front() { erase(node->next); }

->运算符重载

T* operator->() { return &node->data; }

直接看这个可能看不懂，我们先从我们之前表层运用来看，就比如，a1是一个结构体指针，我们想要访问里面其中一个成员变量，就会这样访问，a1->a;然后a1就是我们这里list里的data成员，所以我们正常实现是&node->data，这样就可以得到结构体的指针，然后想要访问结构体内部的成员变量，在&node->data的基础上->a1。

这里主要难理解是因为，我们调用的时候直接就是 it->a；但其实这里不止一个->，完整的其实是这样的，it.operator->()->a；也就和我们上面的思路一样，即(&node->data)->a；只是为了可读性，省略了一个->，省略的->是后面的那个->

拓展：

operator->拥有递归消解机制：
如果operator->返回的还是一个具备operator->的对象，编译器会继续调用它的operator->()；
直到返回原生指针，才停止递归，使用原生指针的->访问成员。

const迭代器初步实现

首先，const迭代器意味就是指向的内容不能修改，那么，我们来找找迭代器里，哪些部分的操作可能会影响到指向的空间

可以发现就这俩个，所以我们只需要在实现const迭代器的时候给这俩个加上限制，其余拷贝过去即可

template<class T> struct list_const_iterator { typedef list_node<T>* Node; typedef list_const_iterator<T> const_iterator; list_const_iterator(Node _node) :node(_node) { } const_iterator& operator++() { node = node->next; return *this; } const_iterator operator++(int) { const_iterator _node(node); node = node->next; return _node; } const_iterator& operator--() { node = node->prev; return *this; } const_iterator operator--(int) { const_iterator _node(node); node = node->prev; return _node; } const T& operator*() const { return node->data; } const T* operator->() const { return &node->data; } bool operator!=(const const_iterator& it) const { return node != it.node; } bool operator==(const const_iterator& it) const { return node == it.node; } Node node; };

迭代器优化

但是，这么实现的话太冗余了，因为这俩个相似度太高了，就*运算符重载和->运算符重载不一样

这个时候我们可以给模板多几个参数，然后优化合并到一起，如下

template<class T,class Ptr,class Re> struct list_iterator { typedef list_node<T>* Node; typedef list_iterator<T, Ptr, Re> Self; list_iterator(Node _node) :node(_node) { } Self& operator++() { node = node->next; return *this; } Self operator++(int) { Self _node(node); node = node->next; return _node; } Self& operator--() { node = node->prev; return *this; } Self operator--(int) { Self _node(node); node = node->prev; return _node; } Re operator*() { return node->data; } Ptr operator->() { return &node->data; } Re operator*() const { return node->data; } Ptr operator->() const { return &node->data; } bool operator!=(const Self& it) const { return node != it.node; } bool operator==(const Self& it) const { return node == it.node; } Node node; };

所以，之后如果遇到高度相似仅有类型不同的，可以想方设法变为同一个类模板

迭代器失效

接下来，我们来看下迭代器失效问题

首先是insert，insert不会有迭代器失效问题，因为list内部元素是一个一个节点，就算是用户使用一个迭代器，插入之后，那个迭代器所指向的空间里的数据也是不会变的

其次是erase，这个会有迭代器失效问题，因为erase会销毁pos位置的节点，如果用户有迭代器指向pos位置，那么就会有迭代器失效问题

clear

template<class T> void list<T>::clear() { iterator it = begin(); while (it != end()) it = erase(it); }

这个clear就可以复用到析构上

~list() { clear(); ::operator delete(node); }

赋值运算符重载

template<class T> void list<T>::swap(list<T>& x) { std::swap(node, x.node); std::swap(_size, x._size); } template<class T> list<T>& list<T>::operator=(list<T> x) { swap(x); return *this; }

至此，list主要的一些接口就实现完成了，接下来赋源码顺便拓展点东西

源码

#pragma once #include <iostream> #include <cassert> namespace qiu { template<class T> struct list_node { T data; list_node<T>* next; list_node<T>* prev; }; template<class T,class Ptr,class Re> struct list_iterator { typedef list_node<T>* Node; typedef list_iterator<T, Ptr, Re> Self; list_iterator(Node _node) :node(_node) { } Self& operator++() { node = node->next; return *this; } Self operator++(int) { Self _node(node); node = node->next; return _node; } Self& operator--() { node = node->prev; return *this; } Self operator--(int) { Self _node(node); node = node->prev; return _node; } Re operator*() { return node->data; } Ptr operator->() { return &node->data; } Re operator*() const { return node->data; } Ptr operator->() const { return &node->data; } bool operator!=(const Self& it) const { return node != it.node; } bool operator==(const Self& it) const { return node == it.node; } Node node; }; template<class T> class list { public: typedef list_node<T>* Node; typedef list_iterator<T, T*, T&> iterator; typedef list_iterator<T, const T*, const T&> const_iterator; void push_back(const T& x); void push_front(const T& x); iterator insert(iterator pos, const T& x); iterator erase(iterator pos); void pop_back(); void pop_front(); void clear(); void swap(list<T>& x); list<T>& operator=(list<T> x); list() :_size(0) { node = (Node)::operator new(sizeof(list_node<T>)); node->next = node; node->prev = node; } list(const list<T>& lt) :_size(0) { node = (Node)::operator new(sizeof(list_node<T>)); node->next = node; node->prev = node; const_iterator it = lt.begin(); while (it != lt.end()) { push_back(*it); ++it; } } ~list() { clear(); ::operator delete(node); } size_t size() const { return _size; } bool empty() const { return size() == 0; } iterator begin() { return iterator(node->next); } iterator end() { return iterator(node); } const_iterator begin() const { return const_iterator(node->next); } const_iterator end() const { return const_iterator(node); } private: Node node; size_t _size; }; template<class T> void list<T>::push_back(const T& x) { insert(end(), x); } template<class T> void list<T>::push_front(const T& x) { insert(begin(), x); } template<class T> typename list<T>::iterator list<T>::insert(iterator pos, const T & x) { Node new_node = (Node)::operator new(sizeof(list_node<T>)); new (&new_node->data) T(x); new_node->next = pos.node; new_node->prev = pos.node->prev; new_node->next->prev = new_node; new_node->prev->next = new_node; ++_size; return new_node; } template<class T> typename list<T>::iterator list<T>::erase(iterator pos) { assert(pos != end()); iterator it = pos.node->next; pos.node->prev->next = pos.node->next; pos.node->next->prev = pos.node->prev; pos.node->data.~T(); ::operator delete(pos.node); --_size; return it; } template<class T> void list<T>::pop_back() { erase(node->prev); } template<class T> void list<T>::pop_front() { erase(node->next); } template<class Container> void Print_Contaiiner(const Container& v) { for (auto x : v) std::cout << x << " "; std::cout << std::endl; } template<class T> void list<T>::clear() { iterator it = begin(); while (it != end()) it = erase(it); } template<class T> void list<T>::swap(list<T>& x) { std::swap(node, x.node); std::swap(_size, x._size); } template<class T> list<T>& list<T>::operator=(list<T> x) { swap(x); return *this; } }

拓展

我们在使用STL的时候，还有这种写法

list<int> lt = {1,2,3,4,5};

这种是C++11才开始有的，如下图

C++11开始就可以把{}括起来的类型认为是initializer_list，然后这个其实就是一个类模板，我们看下他的接口，可以发现，他也是支持迭代器的

然后这个东西的底层其实就是俩个指针，一个指向数据开头，一个指向数据结尾的下一个位置，我们可以用sizeof看下是不是

64位在，俩个指针16字节没问题

那么，既然这个类也支持迭代器，自然支持范围for，我们实现这个就很简单了，如下

list(std::initializer_list<T> il) { init(); for (auto& x : il) push_back(x); }

所以其实，使用这个构造是有三种写法的

qiu::list<int> lt0({ 1,2,32,34,32,4,324,23,43242,423,432 }); qiu::list<int> lt = { 1,2,32,34,32,4,324,23,43242,423,432 }; const qiu::list<int>& lt1 = { 1,2,32,34,32,4,324,23,43242,423,432 };

像第三种就是引用临时对象