【C++】介绍STL中list容器的常用接口
发布时间：2024年01月25日
目录
6.1 头插、尾插 —— push_front、push_back
6.2 尾插、尾删 —— pop_front、pop_back?
7.1 将一个list上的数据转移到另一个list —— splice
一、STL中的list简介
1. list是可以在常数时间(O(1))内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list与forward_list非常相似，最主要的不同在于forward_list是单链表，只能向前迭代，这让forward_list更简单高效。
3. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
4. 与其他的序列式容器(array，vector等)相比，list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，必须从已知的位置(比如头部或者尾部)迭代到目标位置，而迭代到目标位置需要线性的时间(O(n))开销；除此之外list还需要一些额外的空间，以保存每个节点的相关联系。
【文档描述】
二、构造函数
2.1 默认构造函数
【代码演示】
#include <iostream>
#include <list>
#include <string>
using namespace std;
int main()
{
//默认拷贝拷贝构造 list<T> lt;(T为list存储的数据类型)
list<string> ls;
return 0;
}【输出结果】
? ? ? ? 注：list不像string和vector，list没有容量capacity这个属性。?
2.2 填充构造（用n个相同的值构造）
【代码演示】
#include <iostream>
#include <list>
using namespace std;
int main()
{
//填充构造 list (size_type n, const value_type& val = value_type())
list<int> li(5, 20);
//如果不指定val的值就会初始化为相应类型的默认值
//int为0 double为0.0 char为'\0'……
list<double> ld(3);
for (const auto& k : li)
{
cout << k << " ";
}
cout << endl;
for (const auto& k : ld)
{
cout << k << " ";
}
cout << endl;
return 0;
}【输出结果】
2.3 迭代器构造?
【代码演示】
#include <iostream>
#include <list>
#include <string>
using namespace std;
int main()
{
//迭代器构造 list (InputIterator first, InputIterator last)
//迭代器区间为左闭右开 -》 [first, last)
//用数组构造
int array[] = { 1,2,3,4,5,6 };
list<int> li(array, array + sizeof(array) / sizeof(array[0]));
//这个其实是先用数组构造了一个list<int> temp
//然后用拷贝构造将temp拷贝给了li_another -》 list<int> li_another(temp)
list<int> li_another{ 1,2,3,4,5 };
//可以用别的容器的迭代器来构造list
string s("Hello list!");
list<char> lc(s.begin(), s.end());
//可以用list的迭代器来构造list
list<char> lc_copy(++lc.begin(), --lc.end());
for (const auto& k : li)
{
cout << k << " ";
}
cout << endl;
for (const auto& k : li_another)
{
cout << k << " ";
}
cout << endl;
for (const auto& k : lc)
{
cout << k;
}
cout << endl;
for (const auto& k : lc_copy)
{
cout << k;
}
cout << endl;
return 0;
}【输出结果】
2.4 拷贝构造和赋值运算符重载?
【代码演示】
#include <iostream>
#include <list>
using namespace std;
int main()
{
//拷贝构造 list (const list& x)
//赋值运算符重载 list& operator=(const list& x)
list<int> li{ 1,2,3,4,5 };
//拷贝构造
list<int> li_copy(li);
//赋值运算符重载
list<int> li_another = li;
for (const auto& k : li)
{
cout << k << " ";
}
cout << endl;
for (const auto& k : li_copy)
{
cout << k << " ";
}
cout << endl;
for (const auto& k : li_another)
{
cout << k << " ";
}
cout << endl;
return 0;
}【输出结果】?
三、迭代器
【示意图】
3.1 正向迭代器
【代码演示】
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> li{ 1,2,3,4,5 };
cout << *li.begin() << endl;
cout << *(--li.end()) << endl;
return 0;
}? ? ? ? list的迭代器不能直接使用加法或减法（如+1或-1）来实现迭代器位置的更换，因为list的各个节点并不在一块连续的空间，如果直接通过加减法来实现迭代器位置的更换会造成非法访问。所以我们需要使用重载过后的前置或后置的加加、减减操作符来实现迭代器位置的变更。
?【输出结果】
3.2 反向迭代器
【代码演示】
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> li{ 1,2,3,4,5,6,7 };
list<int>::reverse_iterator rbit = li.rbegin();
while (rbit != li.rend())
{
//从begin到end 从rbegin到rend都是++
cout << *rbit << " ";
++rbit;
}
cout << endl;
return 0;
}【输出结果】
四、容量相关?
4.1 获取list中有效数据的个数
【代码演示】
#include <iostream>
#include <list>
#include <string>
using namespace std;
int main()
{
list<string> ls{ "Hello", "lisr", "and", "string", "!" };
cout << ls.size() << endl;
return 0;
}【输出结果】?
4.2 判断list是否为空 —— empty
【代码演示】
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> li;
cout << li.empty() << endl;
//尾插一个1
li.push_back(1);
cout << li.empty() << endl;
return 0;
}【输出结果】
五、元素访问
5.1 获取第一个有效节点的数据
【代码演示】
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> li{ 1,2,3,4,5,6 };
cout << li.front() << endl;
return 0;
}【输出结果】
5.2 获取最后一个有效节点的数据
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<string> ls{ "Hello", "list!" };
cout << ls.back() << endl;
return 0;
}【输出结果】
六、修改相关
6.1 头插、尾插 —— push_front、push_back
【代码演示】
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> li{ 2,3,4,5 };
//头插1
li.push_front(1);
//尾插6
li.push_back(6);
for (const auto& k : li)
{
cout << k << " ";
}
cout << endl;
return 0;
}【输出结果】
6.2 尾插、尾删 —— pop_front、pop_back?
【代码演示】
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> li{ 1,2,3,4,5,6 };
//头删
li.pop_front();
//尾删
li.pop_back();
for (const auto& k : li)
{
cout << k << " ";
}
cout << endl;
return 0;
}【输出结果】
6.3 在任意位置插入
【代码演示】
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> li{ 1,2,3,5,6,7 };
list<int>::iterator pos = li.begin();
//list的迭代器不支持直接加减一个值。
//比如我们要在5的前面插入一个4，就必须让pos++3次，而不能pos + 3
//循环的次数可以看成目标位置下标的数值，但不是真正的下标
//因为list节点并不分布在一块连续的空间
for (int i = 0; i < 3; ++i)
{
++pos;
}
li.insert(pos, 4);
for (const auto& k : li)
{
cout << k << " ";
}
cout << endl;
return 0;
}【输出结果】
? ? ? ? list的插入操作不像vector的插入操作，在插入数据中如果进行了扩容，vector会发生迭代器失效，而list不会。这是因为vector的扩容是开辟一块更大的空间，将原空间数据拷贝到新空间后再释放原空间，而迭代器pos任然指向旧空间，这样就会对非法空间进行访问。但是list的扩容只是开辟一块空间来存储新的数据，其他数据的位置和关系并不会发生变化，所以并不会发生迭代器失效。
6.4 在任意位置删除 —— erase
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> li{ 1,2,3,4,5,6,7,8 };
list<int>::iterator pos = li.begin();
//删除list中的所有偶数
while (pos != li.end())
{
//避免发生迭代器失效
if (*pos % 2 == 0)
{
pos = li.erase(pos);
}
else
{
++pos;
}
}
for (const auto& k : li)
{
cout << k << " ";
}
cout << endl;
return 0;
}? ? ? ? 虽然list在插入过程中不会发生迭代器失效，但是在删除过程中任然会发生迭代器失效。为了避免这种情况我们就需要利用erase的返回值
? ? ? ? erase的返回值是一个指向被删除数据的下一个数据的迭代器，我们在执行删除操作之后让迭代器pos等于erase的返回值，如果没有执行就正常++，这样就能避免迭代器失效问题了。
6.5 交换两个list对象
【代码演示】
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> li1{ 1, 2, 3, 4 ,5 };
list<int> li2{ 6, 7, 8 ,9, 10 };
li1.swap(li2);
cout << "li1的数据为：";
for (const auto& k : li1)
{
cout << k << " ";
}
cout << endl;
cout << "li2的数据为：";
for (const auto& k : li2)
{
cout << k << " ";
}
cout << endl;
return 0;
}【输出结果】
6.6 清空list中的有效节点
【代码演示】
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> li{ 1,2,3,4,5 };
cout << "clear前的数据为：";
for (const auto& k : li)
{
cout << k << " ";
}
cout << endl;
li.clear();
cout << "clear后的数据为：";
for (const auto& k : li)
{
cout << k << " ";
}
cout << endl;
return 0;
}【输出结果】
七、链表操作
7.1 将一个list上的数据转移到另一个list —— splice
【函数原型】
【代码演示】
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> des1{ 1,2,3,4,5 };
list<int> des2(des1);
list<int> des3 = des2;
list<int> sour1{ 6,7,8,9,10 };
list<int> sour2(sour1);
list<int> sour3 = sour2;
//转移一整个链表
des1.splice(des1.end(), sour1);
//转移一个元素
des2.splice(des2.end(), sour2, sour2.begin());
//转移一个区间 -》左闭右开
des3.splice(des3.end(), sour3, ++sour3.begin(), --sour3.end());
cout << "des1的数据为：";
for (const auto& k : des1)
{
cout << k << " ";
}
cout << endl;
cout << "sour1的数据为：";
for (const auto& k : sour1)
{
cout << k << " ";
}
cout << endl;
cout << "des2的数据为：";
for (const auto& k : des2)
{
cout << k << " ";
}
cout << endl;
cout << "sour2的数据为：";
for (const auto& k : sour2)
{
cout << k << " ";
}
cout << endl;
cout << "des3的数据为：";
for (const auto& k : des3)
{
cout << k << " ";
}
cout << endl;
cout << "sour3的数据为：";
for (const auto& k : sour3)
{
cout << k << " ";
}
cout << endl;
return 0;
}【输出结果】
7.2 删除某个特定数据
【代码演示】
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> li{ 1,2,3,1,1,5,8,5,4,3 };
cout << "remove前的数据为：";
for (const auto& k : li)
{
cout << k << " ";
}
cout << endl;
li.remove(1);
cout << "remove后的数据为：";
for (const auto& k : li)
{
cout << k << " ";
}
cout << endl;
return 0;
}【输出结果】
7.3 给数据排序 —— sort
【代码演示】
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> li{ 32,5,86,12,6,2 };
//list排序通过归并排序实现
li.sort();
for (auto& k : li)
{
cout << k << " ";
}
cout << endl;
return 0;
}【输出结果】
? ? ? ? ?注：list用不了algorithm算法库中的sort，因为algorithm的sort的参数要求是随机迭代器RandomAccessIterator，而list的迭代器是双向迭代器bidirectional iterator。
? ? ? ? 除了随机迭代器RandomAccessIterator和双向迭代器bidirectional iterator外还有一种迭代器类型是InputIterator，这个迭代器类型就是只要是迭代器就行。
? ? ? ? 不过话虽如此，但并不建议对list进行排序，因为list的数据在空间上是分散开的，并不适合排序，list排序的效率远远不及vector这种在连续空间上储存数据的容器，因此并不建议对list进行排序。
7.4 去除重复数据 —— unique
【代码演示】
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> li{ 1,4,6,4,6,7,8,9,1,3,5 };
//在去重之前建议先对list进行排序 不然效率实在是太低了 不过排序的效率也很低就是了
li.sort();
li.unique();
for (const auto& k : li)
{
cout << k << " ";
}
cout << endl;
return 0;
}【输出结果】
7.5 反转数据 —— reverse
【代码演示】
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> li{ 1,2,3,4,5,6 };
li.reverse();
for (const auto& k : li)
{
cout << k << " ";
}
cout << endl;
return 0;
}【输出结果】
八、list与vector的对比?
| vector | list | |
| 底 层 结 构 | 动态顺序表，一段连续空间 | 带头结点的双向循环链表 |
| 随 机 访 问 | 支持随机访问，访问某个元素时间复杂度为O(1) | 不支持随机访问，访问某个元素时间复杂度为O(N) |
| 插 入 和 删 除 | 任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容；增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低 | 任意位置插入和删除效率高，不需要搬移元素，时间复杂度为 O(1) |
| 空 间 利 用 率 | 底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高 | 底层节点动态开辟，小节点容易造成内存碎片，空间利用率低， 缓存利用率低 |
| 迭 代 器 | 原生态指针 | 对原生态指针(节点指针)进行封装 |
| 迭 代 器 失 效 | 在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效；删除时，当前迭代器需要重新赋值否则会失效 | 插入元素不会导致迭代器失效， 删除元素时，只会导致当前迭代器失效，其他迭代器不受影响 |
| 使 用 场 景 | 需要高效存储，支持随机访问，不关心插入删除效率 | 大量插入和删除操作，不关心随机访问 |
文章来源:https://blog.csdn.net/2301_80909286/article/details/135830212
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！
最新文章
- Python教程
- 深入理解 MySQL 中的 HAVING 关键字和聚合函数
- Qt之QChar编码（1）
- MyBatis入门基础篇
- 用Python脚本实现FFmpeg批量转换
- NLP项目之语种识别
- RFIC设计的主要流程和发展趋势学习
- 基于内存的分布式NoSQL数据库Redis(三)常用命令
- Python列表数据处理全攻略（五）：常用内置方法轻松掌握
- Traffic Flow Prediction via Spatial Temporal Graph NeuralNetwork
- 后端 API 接口文档 Swagger 使用
- java性能优化-String对象的优化
- 众和策略股市行情分析：股票分红是按持股比例来分的吗？
- 【C#】面向对象的三大特性，还记得吗，简单代码举例回顾
- 使用JavaScript实现动态表单验证