@TOC
前言
文章绑定了VS平台下std::list的源码，大家可以下载了解一下😍
前面我们讲了C语言的基础知识，也了解了一些数据结构，并且讲了有关C++的命名空间的一些知识点以及关于C++的缺省参数、函数重载，引用 和 内联函数也认识了什么是类和对象以及怎么去new一个 ‘对象’ ，以及学习了几个STL的结构也相信大家都掌握的不错，接下来博主将会带领大家继续学习有关C++比较重要的知识点—— list（STL）。下面话不多说坐稳扶好咱们要开车了😍
一、list简介
1.概念
std::list是C++标准库中的双向链表容器。(这里有官方介绍链接) 它支持在任意位置进行快速插入和删除操作，并且在需要对元素进行频繁的插入和删除操作时，通常比std::vector更高效。std::list的元素不是在连续内存中存储，而是通过指针相互连接在一起。
2.特点
双向访问：std::list的元素可以通过双向迭代器从前向后或者从后向前进行访问。
插入和删除操作高效：由于std::list的元素是通过指针连接在一起的，插入和删除操作只需要修改相邻元素的指针，因此在任意位置进行插入和删除操作的时间复杂度是O(1)。
不支持随机访问：由于std::list的元素不是在连续内存中存储的，因此不能通过下标来随机访问元素。如果需要随机访问元素，可以考虑使用std::vector或者std::array。
内存占用相对较大：由于每个元素都需要额外的指针来连接其他元素，std::list的内存占用相对较大。
二、list的使用
list 中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口。
1.list的构造
std::list类提供了多个构造函数，用于创建和初始化std::list对象。官方链接点这里跳转 下面是常用的构造函数列表：
默认构造函数：
std::list<T> myList;创建一个空的std::list对象，其中T是元素的类型。
带有容量参数的构造函数：
std::list<T> myList(size, value);创建一个包含size个元素的std::list对象，每个元素的值都是value。
区间构造函数：
std::list<T> myList(first, last);创建一个std::list对象，其中包含[first, last)区间的元素。first和last是输入迭代器，用于指定要拷贝到新std::list中的元素范围。
拷贝构造函数：
std::list<T> myList(otherList);创建一个std::list对象，其中包含与otherList相同的元素。这将执行深拷贝，即将otherList中的元素复制到新的std::list对象中。
移动构造函数：
std::list<T> myList(std::move(otherList));创建一个std::list对象，并从其他std::list对象otherList中移动元素到新的std::list对象中。在移动构造函数后，otherList将为空。
注意：上述构造函数中的T表示元素的类型，可以是任何有效的C++类型。
#include <list>
int main() {
// 默认构造函数
std::list<int> myList;
// 带有容量参数的构造函数
std::list<int> myList2(5, 10); // 包含5个值为10的元素
// 区间构造函数
int arr[] = {
1, 2, 3, 4, 5};
std::list<int> myList3(std::begin(arr), std::end(arr)); // 包含数组arr的元素
// 拷贝构造函数
std::list<int> myList4(myList2);
// 移动构造函数
std::list<int> myList5(std::move(myList4)); // myList4将为空
return 0;
}
这些是std::list常用的构造函数示例。你可以根据自己的需求选择适当的构造函数来创建std::list对象。
2.常见的操作
⭕std::list类型的增、删、查、改
插入元素：
- push_back(value)：在列表的末尾插入一个元素。
- push_front(value)：在列表的开头插入一个元素。
- insert(pos, value)：在指定位置pos之前插入一个元素。
删除元素：
- pop_back()：删除列表末尾的元素。
- pop_front()：删除列表开头的元素。
- erase(pos)：删除指定位置pos处的元素。
- erase(first, last)：删除从[first, last)范围内的所有元素。
访问元素：
- front()：返回列表的第一个元素的引用。
- back()：返回列表的最后一个元素的引用。
迭代器操作：
- begin()：返回指向列表第一个元素的迭代器。
- end()：返回指向最后一个元素之后位置的迭代器。
- rbegin()：返回指向列表最后一个元素的逆向迭代器。
- rend()：返回指向第一个元素之前位置的逆向迭代器。
大小和清空操作：
- size()：返回列表中元素的数量。
- empty()：检查列表是否为空。
- clear()：清除列表中的所有元素。
修改元素：
- assign(first, last)：用[first, last)范围内的元素替换列表的内容。
- assign(n, value)：用n个值为value的元素替换列表的内容。
- resize(count)：改变列表的大小，使其包含count个元素，并根据需要插入或删除元素。
- swap(otherList)：交换当前列表与otherList之间的内容。
查找和排序：
- find(value)：返回指向第一个值为value的元素的迭代器；如果找不到，则返回end()。
- sort()：按升序对列表中的元素进行排序。
- reverse()：反转列表中的元素的顺序。
以上只是std::list的一些常见操作，还有很多其他的成员函数可用于更复杂的操作。这里有官方的链接你可以根据具体的需求选择适当的操作。
以下是一些示例，展示了std::list的常见操作：
#include <list>
#include <iostream>
int main() {
std::list<int> myList;
// 插入元素
myList.push_back(1);
myList.push_front(2);
myList.insert(std::next(myList.begin()), 3);
// 删除元素
myList.pop_back();
myList.pop_front();
myList.erase(std::next(myList.begin()));
// 访问元素
std::cout << "Front element: " << myList.front() << std::endl;
std::cout << "Back element: " << myList.back() << std::endl;
// 迭代器操作
for (auto it = myList.begin(); it != myList.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
// 大小和清空操作
std::cout << "Size: " << myList.size() << std::endl;
std::cout << "Empty: " << (myList.empty() ? "Yes" : "No") << std::endl;
myList.clear();
// 查找和排序
myList.push_back(5);
myList.push_back(2);
myList.push_back(4);
myList.push_back(1);
auto it = myList.find(4);
ifit != myList.end()) {
std::cout << "Found value 4" << std::endl;
}
myList.sort();
std::cout << "Sorted list: ";
for (const auto& element : myList) {
std::cout << element << " ";
}
std::cout << std::endl;
return 0;
}
三、list与vector的对比
数据存储方式：
- vector：使用连续的内存块存储，可以在O(1)时间内访问任意位置的元素。
- list：使用双向链表存储，每个节点存储一个元素，在O(n)时间内访问任意位置的元素。
动态性：
- vector：动态数组，长度可变。能够动态增长和收缩，但在插入和删除操作时可能需要重新分配内存，导致数据的搬移。
- list：由于使用链表存储，插入和删除操作相对快速，不会涉及内存的重新分配和数据的搬移。
访问效率：
- vector：由于数据存储在连续的内存块中，可以通过下标访问元素，提供了O(1)的随机访问效率。
- list：需要遍历链表才能访问到指定位置的元素，访问效率为O(n)。
插入和删除操作：
- vector：在尾部进行插入和删除操作效率高，复杂度为O(1)；在中间或头部进行插入和删除操作会导致后续元素的移动，复杂度为O(n)。
- list：在插入和删除操作时，只需修改相邻节点的指针，复杂度为O(1)，对于任意位置的插入和删除都具有较高效率。
内存使用：
- vector：由于数据存储在连续的内存块，相对于list可能产生更少的内存开销。
- list：由于每个元素需要额外的指针进行连接，相对于vector可能产生更多的内存开销。
综上所述，当需要频繁进行随机访问操作或者需要动态增长和收缩容量时，vector是一个更好的选择。而在需要频繁进行插入和删除操作、对访问效率要求不高或者需要避免数据搬移时，list是一个更合适的选择。
温馨提示
感谢您对博主文章的关注与支持！在阅读本篇文章的同时，我们想提醒您留下您宝贵的意见和反馈。如果您喜欢这篇文章，可以点赞、评论和分享给您的同学，这将对我提供巨大的鼓励和支持。另外，我计划在未来的更新中持续探讨与本文相关的内容。我会为您带来更多关于C++以及编程技术问题的深入解析、应用案例和趣味玩法等。请继续关注博主的更新，不要错过任何精彩内容！
再次感谢您的支持和关注。我们期待与您建立更紧密的互动，共同探索C++、算法和编程的奥秘。祝您生活愉快，排便顺畅！
