✨个人主页: 夜 默
?所属专栏: C++修行之路
?每篇一句: 图片来源
文章目录
?前言?️正文1、默认成员函数1.1、构造1.2、拷贝构造1.3、赋值重载1.4、析构 2、迭代器2.1、特殊设计模式 3、容量相关4、数据访问5、数据修改6、特殊操作6.1、拼接6.2、移除6.3、排序6.4、逆置 ?总结
?前言
STL
中的 vector
存在头部及中部操作效率低的缺陷,需要另一种容器来弥补其短板,此时 list
就应运而生,list
是一个双向带头循环链表,是链表的终极形态,除了不支持下标的随机访问外,其他方面效率都是极高的,本文将带大家认识、使用 list
容器
list
的结构示意图(双向带头循环链表)
出自 《STL源码剖析》
?️正文
学习使用容器首先需要从 默认成员函数
入手
1、默认成员函数
1.1、构造
list
支持三种构造方式:默认构造、带参构造及迭代器区间构造
默认构造:生成一个 list
对象,此时只有一个头节点(哨兵位节点)
带参构造:初始化对象,内含 n
个 val
值
迭代器区间构造:根据传入的迭代器区间,构造出目标区间值的对象
void TestList(){vector<int> arr = { 1,2,3,4,5,6,7,8 };list<int> l1;//默认构造list<int> l2(10, 1);//带参构造list<int> l3(arr.begin(), arr.end());//迭代器区间构造cout << "l1 size: " << l1.size() << endl;for (auto e : l1) cout << e << " ";cout << endl;cout << "l2 size: " << l2.size() << endl;for (auto e : l2) cout << e << " ";cout << endl;cout << "l3 size: " << l3.size() << endl;for (auto e : l3) cout << e << " ";cout << endl;}
注意: list
中不存在扩容的概念,欲使用的节点都是按需申请的,不会造成空间浪费
1.2、拷贝构造
将已存在的 list
对象拷贝构造出一个新的对象
void TestList(){list<int> src(5, 4);list<int> dst(src);cout << "src: ";for (auto e : src)cout << e << " ";cout << endl;cout << "dst: ";for (auto e : dst)cout << e << " ";cout << endl;}
拷贝构造出的新对象数据与源对象一模一样
1.3、赋值重载
赋值重载类似于拷贝构造,不过使用赋值重载时,源对象与目标对象都已存在
void TestList(){const char* ps = "Hello list!";list<char> src(ps, ps + strlen(ps));list<char> dst;//即使目标小于源,也能进行赋值dst = src;cout << "dst: ";for (auto e : dst)cout << e;cout << endl;}
注意: 即使目标对象比源对象小,也可以进行赋值
1.4、析构
对象成功创建,在其生命周期结束时,会自动调用析构函数,对其进行内存释放
随着析构函数的调用,对象中的头节点(哨兵节点)也将失效
2、迭代器
2.1、特殊设计模式
list
中的迭代器比较特殊,不同于 string
和 vector
的随机迭代器,list
中的是双向迭代器,不支持 it + 1
、it - 1
等操作,只能做单纯的双向移动,并且 list
中的迭代器不再是一个单纯的原生指针,而是一个经过封装的类(模拟实现时详细讲解)
list
中也有多种迭代器
iterator
反向迭代器 reveser_iterator
正向与反向的 const
版本
实际使用时,正向迭代器与 begin()
、end()
匹配使用,反向迭代器与 rbegin()
、rend()
匹配使用
void TestList(){string str = "I love BeiJing";list<char> l(str.begin(), str.end());//迭代器区间构造//正向遍历list<char>::iterator it = l.begin();while (it != l.end()){cout << *it;it++;}cout << endl;//反向遍历list<char>::reverse_iterator rit = l.rbegin();while (rit != l.rend()){cout << *rit;rit++;}cout << endl;}
因为 list
不支持下标的随机访问,所以在对 list
对象进行遍历时,必须使用迭代器,其他使用非连续空间容器也是如此,由此可以看出迭代器设计的巧妙之处(以统一的接口,规范所有容器的使用)
注意: list
也存在迭代器失效问题,在 erase
节点后,此处的迭代器将失效,需要及时更新迭代器
3、容量相关
list
中也存在容量相关概念
void TestList(){list<int> l(100, 1);//大小为100cout << "empty(): " << l.empty() << endl;//0表示不为空cout << "size(): " << l.size() << endl;cout << "max_size(): " << l.max_size() << endl;}
注意: max_size()
常用来检查大小调整时的合法性,假设欲调整大小大于 max_size()
,则不再执行 resize()
4、数据访问
访问 list
对象中数据时,采用 front()
和 back()
进行首尾数据的访问
void TestList(){vector<int> v = { 1,2,3,4,5 };list<int> l(v.begin(), v.end());cout << "Front: " << l.front() << endl;cout << "Back: " << l.back() << endl;}
其实 front()
就是头节点的下一个节点,back()
则是头节点的上一个节点
若是想遍历访问整个 list
对象,可以使用迭代器或范围 for
5、数据修改
双向链表对于头尾数据操作很占优势,因此提供的相关接口较多
赋值、头插删、尾插删
void Print(list<int>& l){for (auto e : l)cout << e << " ";cout << endl;}void TestList(){vector<int> v = { 1,2,3 };list<int> l(v.begin(), v.end());cout << "Original: ";Print(l);l.assign(5, 9);//赋值为 5个 9cout << "assign: ";Print(l);l.push_front(10);cout << "push_front: ";Print(l);l.pop_front();cout << "pop_front: ";Print(l);l.push_back(10);cout << "push_back: ";Print(l);l.pop_back();cout << "pop_back: ";Print(l);}
任意位置插删
需要配合迭代器使用,而目标位置的迭代器可以通过全局函数 find()
获取
void Print(list<int>& l){for (auto e : l)cout << e << " ";cout << endl;}void TestList(){vector<int> v = { 1,2,3 };list<int> l(v.begin(), v.end());cout << "Original: ";Print(l);//任意位置插入auto pos = find(l.begin(), l.end(), 2);cout << "insert(pos, val): ";l.insert(pos, 100);Print(l);cout << "insert(pos, n, val): ";l.insert(pos, 3, 6);Print(l);cout << "insert(pos, first, last): ";l.insert(pos, v.begin(), v.end());Print(l);//任意位置删除pos = find(l.begin(), l.end(), 3);cout << "erase(pos): ";l.erase(pos);Print(l);cout << "erase(first, last): ";l.erase(l.begin(), l.end());Print(l);}
关于 find()
: 如果出现相同值,默认返回第一次找到的位置
注意: erase
也会迭代器失效问题,需要及时更新迭代器位置
交换、调整、清理
虽说已有 std::swap
,但 list
中的 swap
效率会更高,直接交换头节点,比调用拷贝构造函数进行交换好得多
list
也支持调整其大小,假设调整后大小大于原大小,会尾插 T()
值
void Print(list<int>& l1, list<int>& l2){cout << "l1 size(): " << l1.size() << endl;for (auto e : l1)cout << e << " ";cout << endl;cout << "l2 size(): " << l2.size() << endl;for (auto e : l2)cout << e << " ";cout << endl;cout << "============" << endl;}void TestList(){vector<int> v = { 1,2,3 };list<int> l1(v.begin(), v.end());list<int> l2(v.rbegin(), v.rend());cout << "Original" << endl;Print(l1, l2);cout << "swap(): " << endl;l1.swap(l2);Print(l1, l2);cout << "resize(): " << endl;l1.resize(1);l2.resize(10);Print(l1, l2);cout << "clear(): " << endl;l2.clear();Print(l1, l2);}
注意: resize()
中参数的最大值,不能超过 max_size()
值;C++11
中新增了许多函数,比如 emplace_front()
等,它们的功能与常规操作一致,不过在某些场景下性能更优
6、特殊操作
对于 list
来说,还存在许多特殊操作,比如链表拼接、链表元素移除、链表逆置等等
6.1、拼接
拼接即 splice()
,对原链表中的区间进行拼接操作,拼接后,源区间将会消失,因此拼接操作应该叫做 move
才合理
void Print(list<int>& dst, list<int>& src){cout << "dst size(): " << dst.size() << endl;for (auto e : dst)cout << e << " ";cout << endl;cout << "src size(): " << src.size() << endl;for (auto e : src)cout << e << " ";cout << endl;cout << "============" << endl;}void TestList(){vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8 };list<int> dst(v.begin(), v.begin() + 5);list<int> src(v.begin() + 5, v.end());cout << "Original" << endl;Print(dst, src);cout << "splice(pos, list): " << endl;dst.splice(dst.end(), src);//拼接至结尾Print(dst, src);cout << "splice(pos, list, it): " << endl;dst.splice(dst.end(), dst, dst.begin());//拼接至结尾Print(dst, src);auto first = dst.begin();first++;//指向第二个节点auto last = dst.end();//指向最后一个节点cout << "splice(pos, list, first, last): " << endl;dst.splice(dst.begin(), dst, first, last);//拼接至开头Print(dst, src);}
关于拼接(接合)过程可以参考下图:
注意: 拼接之后,原位置处的节点将消失(已被拼接至其他地方)
6.2、移除
可能委员会觉得 find()
+ erase()
这种写法不太方便,于是就重新定义了一种新方法 remove()
,简单来说,它就是 find()
+ erase()
的封装版,使用起来很方便
void TestList(){vector<int> v = { 1,2,3 };list<int> l(v.begin(), v.end());cout << "Original: ";for (auto e : l)cout << e << " ";cout << endl;l.remove(2);//移除元素2cout << "remove(): ";for (auto e : l)cout << e << " ";cout << endl;}
6.3、排序
list
也支持排序,不过用的是其他排序方法,且效率较低(库中的 std::sort
用的是快排,需要下标进行随机访问,因此 list
无法使用)
注意: 实际上,list
的效率比较低,还不如先将数据拷贝至 vector
中,排完序后再拷贝回来的效率高
void TestList(){srand((size_t)time(NULL));//种子int n = 10000000;//排序千万级数据vector<int> tmp;tmp.reserve(n);list<int> l1;list<int> l2;int val = 0;int i = 0;while (i < n){//放入随机数val = rand() % 100 + 1;l1.push_back(val);l2.push_back(val);i++;}//进行排序//使用 list::sortint begin1 = clock();l1.sort();int end1 = clock();//使用 std::sortint begin2 = clock();//拷贝至 vector 中for (auto e : l2)tmp.push_back(e);std::sort(tmp.begin(), tmp.end());//快排//拷贝回去int pos = 0;for (auto& e : l2)e = tmp[pos++];int end2 = clock();cout << "list::sort: " << end1 - begin1 << endl;cout << "std::sort: " << end2 - begin2 << endl;}
可以看出,即使是 拷贝->排序->拷贝,速度也比直接使用 list::sort
快一倍左右(排序千万级数据)
6.4、逆置
reverse()
可以直接将 list
对象进行逆置(无脑解决链表翻转问题)
void TestList(){string str = "I love BeiJin";list<char> l(str.begin(), str.end());cout << "Original: ";for (auto e : l)cout << e;cout << endl;cout << "reverse(): ";l.reverse();for (auto e : l)cout << e;cout << endl;}
关于运算符重载(逻辑比较):实现时,只需要调用对象中具体数据类型的函数即可,比如 list<vector>
,在 list::operator==()
中,每个数据调用 vector::operator==()
进行逻辑判断
除此之外, list
中还有其他函数,感兴趣的同学可以阅读官方文档 《list》
?总结
以上就是本次关于 STL
中的 list
容器学习使用的全部内容了,list
相对于前两种容器来说比较特殊,值得细细研究,list
的核心内容在于其迭代器类的设计,将在下篇文章 《list的模拟实现》中讲解
如果你觉得本文写的还不错的话,可以留下一个小小的赞?,你的支持是我分享的最大动力!
如果本文有不足或错误的地方,随时欢迎指出,我会在第一时间改正
相关文章推荐
C++ STL学习之【vector的模拟实现】
C++ STL学习之【vector的使用】
===============
STL 之 string 类
C++ STL学习之【string类的模拟实现】
C++ STL 学习之【string】
===============
内存、模板
C++【模板初阶】
C/C++【内存管理】
![承蒙厚爱,感谢支持 感谢支持](http://zhangshiyu.com/zb_users/upload/2023/04/20230408162637168094239782623.gif)