✨个人主页： 北 海
🎉所属专栏： C++修行之路
🎊每篇一句： 图片来源
- A year from now you may wish you had started today.
- 明年今日，你会希望此时此刻的自己已经开始行动了。
🌇前言
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); //大小为100
cout << "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个 9
cout << "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); //移除元素2
cout << "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::sort
int begin1 = clock();
l1.sort();
int end1 = clock();
//使用 std::sort
int 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的模拟实现》中讲解
如果你觉得本文写的还不错的话，可以留下一个小小的赞👍，你的支持是我分享的最大动力！
如果本文有不足或错误的地方，随时欢迎指出，我会在第一时间改正
文章来源地址https://www.toymoban.com/news/detail-415439.html
相关文章推荐
C++ STL学习之【vector的模拟实现】 文章来源：https://www.toymoban.com/news/detail-415439.html
C++ STL学习之【vector的使用】
===============
STL 之 string 类
C++ STL学习之【string类的模拟实现】
C++ STL 学习之【string】
===============
内存、模板
C++【模板初阶】
C/C++【内存管理】 
到了这里，关于C++ STL学习之【list的使用】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
