list介绍
list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)
list使用
本文介绍的是list的部分常用接口，大佬们想了解更多关于list类的细节，一定要请前往官方文档（点击跳转）查阅学习！
1. 默认成员函数
1.1 构造函数
list支持三种构造方式：
- 默认构造：构造一个
list对象，此时只有一个哨兵位节点 - 带参构造：构造一个
list对象，初始化对象有n个val值的节点 - 迭代器区间构造：根据传入的迭代器区间，构造出目标区间值的
list对象
int main()
{
vector<int> arr = {
1,2,3,4,5,6 };
list<int> l1; //默认构造
list<int> l2(8, 1); //带参构造，8个val值为1的节点
list<int> l3(arr.begin(), arr.end()); //迭代器区间构造
return 0;
}
1.2 拷贝构造
拷贝已有的list对象来构造出一个新的相同值对象
int main()
{
list<int> l1(3, 6);
list<int> l2(l1);
cout << "l1: ";
for (auto e : l1) cout << e << " ";
cout << endl;
cout << "l2: ";
for (auto e : l2) cout << e << " ";
return 0;
}
1.3 赋值重载
将原有list对象的值赋值给另一个已存在的对象
int main()
{
const char* ps = "happy new year";
list<char> l1(ps, ps + strlen(ps)); //源对象
list<char> l2; //目标对象
l2 = l1;
for (auto e : l2) cout << e;
return 0;
}
注意： 即使目标对象比源对象小，也能进行赋值
1.4 析构函数
析构函数会在对象生命周期结束时自动调用，进行内存释放，调用后哨兵位也将被释放
2. 迭代器
由于list的空间不是连续的，所以它的迭代器是不同于string和vector的随机迭代器的，list类中使用的是双向迭代器，只能做单纯的双向移动
list中的迭代器
- 正向迭代器
iterator - 反向迭代器
reveser_iterator const版本正反迭代器
int main()
{
string str = "hello world";
list<char> l1(str.begin(), str.end()); //迭代器区间构造
//正向遍历
list<char>::iterator it = l1.begin();
while (it != l1.end())
{
cout << *it;
it++;
}
cout << endl;
//反向遍历
list<char>::reverse_iterator rit = l1.rbegin();
while (rit != l1.rend())
{
cout << *rit;
rit++;
}
return 0;
}
因为list 的空间不是连续的，所以不支持下标的随机访问，对 list 对象进行遍历时，只能使用迭代器
3. 容量操作
empty()接口：判空
size()接口：查看大小
max_size()接口：检查大小调整时的合法性
int main()
{
list<int> l1(88, 6);
cout << l1.size() << endl;
cout << l1.empty() << endl;
cout << l1.max_size() << endl;
return 0;
}
4. 数据访问
front()接口：访问哨兵位的下一个节点
back()接口：访问链尾数据
int main()
{
vector<int> v = {
4,1,2 };
list<int> l1(v.begin(), v.end()); //迭代器区间构造
cout << "front: " << l1.front() << endl;
cout << "back: " << l1.back() << endl;
return 0;
}
5. 数据修改
5.1 插入删除
assign()接口：赋值
push_front()接口：头插
pop_front()接口：头删
push_back()接口：尾插
pop_back()接口：尾删
int main()
{
vector<int> vs = {
4,1,2 };
list<int> l1(vs.begin(), vs.end());
for (auto e : l1) cout << e << " "; //4 1 2
cout << endl;
l1.assign(3, 6); //赋值为3个6
for (auto e : l1) cout << e << " "; //6 6 6
cout << endl;
l1.push_front(12); //头插12
for (auto e : l1) cout << e << " "; //12 6 6 6
cout << endl;
l1.pop_front(); //头删
for (auto e : l1) cout << e << " "; //6 6 6
cout << endl;
l1.push_back(24); //尾插24
for (auto e : l1) cout << e << " "; //6 6 6 24
cout << endl;
l1.pop_back(); //尾删
for (auto e : l1) cout << e << " "; //6 6 6
cout << endl;
return 0;
}
list对于首尾数据的操作效率很高
insert()接口：任意位置插入
erase()接口：任意位置删除
任意位置的操作需要配合迭代器和全局查找函数find()使用，一段数据中如果有相同值，find()会返回第一次找到的位置
int main()
{
vector<int> vv = {
4,1,2 };
list<int> l1(vv.begin(), vv.end());
for (auto e : l1) cout << e << " "; //4 1 2
cout << endl;
auto poss = find(l1.begin(), l1.end(), 2);
l1.insert(poss, 6); //指定位置插入6
for (auto e : l1) cout << e << " "; //4 1 6 2
cout << endl;
l1.insert(poss, 3, 8); //指定位置插入3个8
for (auto e : l1) cout << e << " "; //4 1 6 8 8 8 2
cout << endl;
l1.insert(poss, vv.begin(), vv.end()); //指定位置插入一段数据
for (auto e : l1) cout << e << " "; //4 1 6 8 8 8 4 1 2 2
cout << endl;
poss = find(l1.begin(), l1.end(), 1);
l1.erase(poss); //删除指定位置的值
for (auto e : l1) cout << e << " "; //4 6 8 8 8 4 1 2 2
cout << endl;
l1.erase(l1.begin(), l1.end()); //全删
for (auto e : l1) cout << e << " ";
return 0;
}
==注意：==
erase后会存在迭代器失效问题，需要及时更新迭代器位置！！！
5.2 交换调整清理
swap()接口：list对象交换
resize()接口：调整大小，若调整后的大小大于原大小，会尾插T()的值
clean()接口：清理
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;
}
int main()
{
vector<int> vc = {
4,1,2 };
list<int> l1(vc.begin(), vc.end());
list<int> l2(vc.rbegin(), vc.rend());
Print(l1, l2);
l1.swap(l2); //交换l13和l14
Print(l1, l2);
l1.resize(1); //调整大小为1
l2.resize(12); //调整大小为12
Print(l1, l2);
l2.clear(); //清理l13
Print(l2, l2);
return 0;
}
6. 其他操作
list类中还有诸如拼接、移除、逆置等操作，特殊场景使用起来很方便
6.1 链表拼接
splice()接口：对原链表中指定区间进行拼接，拼接后，原位置处的节点(区间)不再有，已被拼接到其他地方
void Print(list<int>& l1, list<int>& l2)
{
cout << "l1: ";
for (auto e : l1) cout << e << " ";
cout << endl;
cout << "l2: ";
for (auto e : l2) cout << e << " ";
cout << endl;
cout << "--------------------" << endl;
}
int main()
{
vector<int> vx = {
1, 2, 3, 4, 5, 6 };
list<int> l1(vx.begin(), vx.begin() + 3); //123
list<int> l2(vx.begin() + 3, vx.end()); //456
Print(l1, l2);
l1.splice(l1.end(), l2); //l2拼接到l1的结尾
Print(l1, l2);
l1.splice(l1.end(), l1, l1.begin()); //拼接到结尾
Print(l1, l2);
auto first = l1.begin();
first++; //指向第二个节点
auto last = l1.end(); //指向最后一个节点
l1.splice(l1.begin(), l1, first, last); //拼接到开头
Print(l1, l2);
return 0;
}
6.2 链表移除
remove()接口：这个接口就是find() + erase()的封装版，使用起来非常方便
int main()
{
vector<int> va = {
4,1,2 };
list<int> l1(va.begin(), va.end());
for (auto e : l1) cout << e << " ";
cout << endl;
l1.remove(2); //移除元素2
for (auto e : l1) cout << e << " ";
cout << endl;
return 0;
}
6.3 排序
由于库中的排序std::sort使用的是快排，需要支持下标随机访问，所以list对象不能使用，list类自己也提供了排序算法，不过效率较低，还不如先将数据拷贝到vector中，排序完后再拷贝回来的效率高
下面一段代码就是测试两种排序方法的效率：
int main()
{
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();
int begin2 = clock();
//先拷贝到vector中
for (auto e : l2)
{
tmp.push_back(e);
}
//使用std::sort 排序（快排）
std::sort(tmp.begin(), tmp.end());
//再拷贝回去
int pos = 0;
for (auto& e : l2)
{
e = tmp[pos++];
}
int end2 = clock();
cout << "list::sotr time is: " << end1 - begin1 << endl;
cout << "std::sort time is: " << end2 - begin2 << endl;
return 0;
}
6.4 链表逆置
reverse()接口：将list对象逆置
int main()
{
string ss = "happy";
list<char> l1(ss.begin(), ss.end());
for (auto e : l1) cout << e;
cout << endl;
l1.reverse();
for (auto e : l1) cout << e;
cout << endl;
return 0;
}
C++【STL】之list的使用，到这里就介绍结束了，本篇文章对你由帮助的话，期待大佬们的三连，你们的支持是我最大的动力！
文章有写的不足或是错误的地方，欢迎评论或私信指出，我会在第一时间改正！
