C++ list的基本使用
目录
1.list简要介绍
2. list的构造
3. list中迭代器的使用
(1). 双向迭代器与随机访问迭代器使用区别
4.判空、获取元素个数
5. list头、尾元素的访问
6. 插入与删除操作
(1). 头插头删，尾插尾删
(2). 插入，删除与清空
(3). 交换
7. list容器迭代器失效问题
1.list简要介绍
在C++标准库中list是基于双向链表实现的
其特点主要包括
- 双向链表结构，插入和删除元素时非常高效，因为不需要移动元素
- 内存分配并不是连续的，和vector不同
- 不支持随机访问的迭代器，提供的迭代器是双向迭代器(下文会详细介绍)
- 可以动态增容，不受容量的限制
- 由于每个元素都需要额外的内存来存储指向相邻元素的指针(或引用)，因此list可能会比基于数组的容器(如vector)使用更多的内存
2. list的构造
| 构造函数 | 接口说明 |
| list(size_type n, const val_type& val = value_type() ) | 构造的list中包含n个值为val的元素 |
| list() | 构造空的list |
| list(const list& x) | 拷贝构造函数 |
| list(InputIterator first,InputIterator last) | 用[first,last)区间中的元素构造list (左闭右开) |
演示代码如下
#include<iostream>
#include<list>using namespace std;int main()
{list<int> l1(10);for (auto ll : l1){cout << ll << " ";}cout << endl;list<int> l2(10, 3);for (auto ll : l2){cout << ll << " ";}cout << endl;list<int> l3(l1);for (auto ll : l3){cout << ll << " ";}cout << endl;list<int> l4(l2.begin(), l2.end());for (auto ll : l4){cout << ll << " ";}cout << endl;}3. list中迭代器的使用
| 函数 | 接口说明 |
| begin+end | 返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器 |
| rbegin+rend | 返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一位的reverse_iterator，即begin位置 |
演示代码如下
#include<iostream>
#include<list>using namespace std;int main()
{list<int> l1(10);l1.push_back(1);list<int>::iterator il = l1.begin();while (il != l1.end()){cout << *il << " ";il++;}cout << endl;list<int>::reverse_iterator it = l1.rbegin();while(it!=l1.rend()){cout << *it << " ";it++;}cout << endl;}输出结果为
这里的迭代器是双向迭代器（Bidirectional Iterator），vector与string等支持随机访问迭代器（Random Access Iterator）存在差异
(1). 双向迭代器与随机访问迭代器使用区别
双向迭代器可以使用++向前，使用--向后移动。支持基本迭代器操作如解引用( * )、自增自减(++ , --)和比较操作( == , != )
随机访问迭代器除了支持双向迭代器所有的功能外，还提供了快速随机访问容器中任意元素的能力。这意味着它支持指针算数运算，(假设v是一个对象)如v.begin()+n (向前移动n个位置)，v.end()-n (向后移动n个位置)，以及比较操作(< , <= , > , >=)
4.判空、获取元素个数
| 函数声明 | 接口说明 |
| empty | 检测list是否为空，是返回true，否则返回false |
| size | 返回list中有效节点的个数 |
简单演示代码如下
#include<iostream>
#include<list>using namespace std;int main()
{list<int> l1(10);list<int> l2;cout << "l1元素个数为：" << l1.size() << endl;cout << "l2元素个数为：" << l2.size() << endl;cout << "l1是否为空?" << endl;if (l1.empty())cout << "yes" << endl;elsecout << "no" << endl;cout << "l2是否为空?" << endl;if (l2.empty())cout << "yes" << endl;elsecout << "no" << endl;l1.push_back(1);l2.push_back(66);cout << "l1元素个数为：" << l1.size() << endl;cout << "l2元素个数为：" << l2.size() << endl;cout << "l1是否为空?" << endl;if (l1.empty())cout << "yes" << endl;elsecout << "no" << endl;cout << "l2是否为空?" << endl;if (l2.empty())cout << "yes" << endl;elsecout << "no" << endl;}输出结果如下
5. list头、尾元素的访问
| 函数声明 | 接口说明 |
| front | 返回list第一个节点中值的引用 |
| back | 返回list的最后一个节点中值的引用 |
演示代码如下
#include<iostream>
#include<list>using namespace std;int main()
{list<int> l1(10);list<int> l2;cout<<l1.front()<<endl;int& f = l1.front();//可用引用接收l1.push_front(4);cout << f<<endl;cout << l1.front() << endl;cout << l1.back() << endl;int& t = l1.back();cout << t << endl;l1.push_back(6);cout << l1.back();//cout << l2.front();//cout << l2.back();return 0;
}特别注意如果list为空使用会报错
6. 插入与删除操作
| 函数 | 接口说明 |
| push_front | 在list首元素前插入值为val的元素 |
| pop_front | 删除list中第一个元素 |
| push_back | 在list尾部插入值为val的元素 |
| pop_back | 删除list中最后一个元素 |
| insert | 在list 中的指定位置pos插入值为val的元素 |
| erase | 删除list指定位置pos的元素 |
| clear | 清空list中的有效元素 |
| swap | 交换两个list中的元素 |
(1). 头插头删，尾插尾删
代码简单演示
#include<iostream>
#include<list>using namespace std;int main()
{list<int> ll;ll.push_back(8);ll.push_back(5);ll.push_back(2);ll.push_front(9);ll.push_front(6);ll.push_front(3);for (auto l : ll){cout << l << " ";}cout << endl;ll.pop_back();ll.pop_front();for (auto l : ll){cout << l << " ";}cout << endl;
}(2). 插入，删除与清空
演示代码如下
#include<iostream>
#include<list>
#include<vector>
using namespace std;template<class T>
void print_list(list<T> ll)
{for (auto l : ll){cout << l << " ";}cout << endl;
}
int main()
{int array1[] = { 1, 2, 3 };list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));// 获取链表中第二个节点auto pos = ++L.begin();cout << *pos << endl;print_list(L);
// 在pos前插入值为4的元素L.insert(pos, 4);print_list(L);
// 在pos前插入5个值为5的元素L.insert(pos, 5, 5);print_list(L);// 在pos前插入[v.begin(), v.end)区间中的元素vector<int> v{ 7, 8, 9 };L.insert(pos, v.begin(), v.end());print_list(L);// 删除pos位置上的元素L.erase(pos);print_list(L);list<int> LL(L);
// 删除list中[begin, end)区间中的元素，即删除list中的所有元素L.erase(L.begin(), L.end());print_list(L);cout << "LL元素个数为: " << LL.size() << endl;LL.clear();cout << "LL元素个数为: " << LL.size() << endl;}
输出结果为
(3). 交换
演示代码如下
#include<iostream>
#include<list>
#include<vector>
using namespace std;template<class T>
void print_list(list<T> ll)
{for (auto l : ll){cout << l << " ";}cout << endl;
}
int main()
{int array1[] = { 1, 2, 3 };list<int> L1(array1, array1 + sizeof(array1) / sizeof(array1[0]));list<int> L2;cout << "L1: ";print_list(L1);cout << "L2: ";print_list(L2);L1.swap(L2);cout << "L1: ";print_list(L1);cout << "L2: ";print_list(L2);return 0;
}输出结果如下
list提供的swap成员函数优化了交换操作，使其可以在常数时间内完成std::swap 也可以交换list对象，但不如list自己的成员函数，实际上它只用交换两个list对象的头指针和尾指针时间复杂度通常为O(1)，不涉及元素的实际移动或复制
7. list容器迭代器失效问题
迭代器失效即迭代器所指向的节点无效，即该节点被删除了。因为list底层结构为带头节点的双向循环链表，所以在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响(与vector不同，list每个节点存储不是连续的)。
eraser比较容易触发
#include<iostream>
#include<list>
using namespace std;
int main()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));auto it = l.begin();while (it != l.end()){// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给//其赋值cout << *it << " ";l.erase(it);++it;}return 0;
}输出结果如下
在执行删除后迭代器就失效了
解决方法1
#include<iostream>
#include<list>
using namespace std;
int main()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));auto it = l.begin();while (it != l.end()){cout << *it << " ";l.erase(it++); }return 0;
}利用后置++先使用，在迭代器失效前提前改变了迭代器的值
解决方法2
while (it != l.end()){cout << *it << " ";it=l.erase(it); // it = l.erase(it);}使用it来接收删除数据后的返回的迭代器
8. list与vector的区别
| vector | list | |
| 底层结构 | 动态顺序表，一段连续空间 | 带头节点的双向循环链表 |
| 随机访问 | 支持随机访问，访问某个元素效率O(1) | 不支持随机访问，访问某个元素效率O(N) |
| 插入和删除 | 任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N),插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低 | 任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1) |
| 空间利用率 | 底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高 | 底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低 |
| 迭代器 | 原生态指针 | 对原生态指针(节点指针)进行了封装 |
| 迭代器失效 | 在插入元素时，要给所有迭代器重新赋值，因为插入元素有可能会导致重新扩容，导致原来迭代器失效。删除时，当前迭代器需要重新赋值否则会失效 | 插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效需要重新赋值，其他迭代器不受影响 |
| 使用场景 | 需要高效存储，支持随机访问，不关心插入删除的效率 | 大量插入和删除操作，不关心随机访问 |
这篇就到这里啦，感谢阅读
(๑′ᴗ‵๑)Ｉ Lᵒᵛᵉᵧₒᵤ❤