list的介绍及使用
【写在前面】
在学完 list，大家对 STL 中的迭代器的认知会进一步提高。list 用的虽然不多，但是它的底层有很多经典的东西，尤其是它的迭代器。list 的结构对我们来说应该问题不大，因为在《数据结构》时我们就已经了解过链表了，它的结构是一个带头双向循环链表，之前我们也实现过。
对于 list 没有 reserve 和 resize，因为它的底层不是连续的空间，它是用一个申请一个，不用一个就释放一个。也没有 operator[]，因为它不支持随机访问。同时它有头插、头删、尾插、尾删、任意位置的插入、删除。因为 list 是带头双向循环链表。
有了前面 string 和 vector 的铺垫，我们这里对于 list 的使用就大概过一下即可，因为它们比较类似，重点主要放在 list 的深度剖析及模拟实现。
其实来严格来说 C++ 的 list 有两个：
- <list> 是带头双向循环链表，是我们本章需要学习的知识
- <forward_list> 是单链表，它是 C++11 所增加的，它的使用场景一点也不多，查看文档，可以看到它不支持尾插、尾删，因为对于单链表效率很低。并且它的任意位置插入、删除是在当前位置之后，因为当前位置之前得找前一个，也是一个 O(N) 的实现。单链表对比双向链表的唯一优势就是每个节点少存一个指针。
一、list的介绍及使用
💦 list的介绍
- list 是可以在常数范围内 O(1) 在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代
- list 的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素
- list 与 forward_list 非常相似：最主要的不同在于 forward_list 是单链表，只能往前迭代，已让其更简单高效
- 与其它的序列式容器相比(array，vector，deque)，list 通常在任意位置进行插入、移除元 素的执行效率更好
- 与其它序烈式容器相比，list 和 forward_list 最大的缺陷是不支持任意位置的随机访问，比如：要访问 list 的第 6 个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list 还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大 list 来说这可能是一个重要的因素)
💦 list的使用
1、list的构造
| constructor | 接口说明 |
|---|---|
| list() | 构造空的 list |
| list(size_type n, const value_type& val = value_type()) | 构造 list 中包含 n 个值为 val 的元素 |
| list(const list& x) | 拷贝构造函数 |
| list(InputIterator first, InputIterator last) | 用 (first, last) 区间中的元素构造 list |
#include<iostream>
#include<vector>
#include<list>
using namespace std;
namespace std
{
void test_list1()
{
list<int> lt1;
list<int> lt2(10, 5);
list<int> lt3(lt2.begin(), lt2.end());
//同样支持用其它容器的迭代器区间去构造,因为它是模板,并且它可以支持如下写法
vector<int> v = { 1, 2, 3, 4, 5 };
list<int> lt4(v.begin(), v.end());
list<int> lt5(lt4);
}
}
int main()
{
std::test_list1();
return 0;
}
2、list iterator的使用
| iterator | 接口说明 |
|---|---|
| begin + end | 返回第一个元素的迭代器 + 返回最后一个元素下一个位置的迭代器 |
| rbegin + rend | 返回第一个元素的 reserve_iterator，即 end 位置，返回最后一个元素下一个位置的 reverse_iterator，即 begin 位置 |
#include<iostream>
#include<vector>
#include<list>
using namespace std;
namespace std
{
void test_list1()
{
vector<int> v = { 1, 2, 3, 4, 5 };
list<int> lt(v.begin(), v.end());
list<int>::iterator it1 = lt.begin();
//注意对于string和vector我们可以用小于或不等于做为判断条件,但是list只能用不等于做为判断条件,这时因为不同的容器中空间连续与否的原因
while(it1 != lt.end())
{
cout << *it1 << " ";
++it1;
}
cout << endl;
list<int>::reverse_iterator it2 = lt.rbegin();
while(it2 != lt.rend())
{
cout << *it2 << " ";
++it2;
}
cout << endl;
//list里已经不再支持operator[]
for(auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
}
int main()
{
std::test_list1();
return 0;
}
3、list capacity
| capacity | 接口说明 |
|---|---|
| empty | 检测 list 是否为空，是返回 true，否则返回 false |
| size | 返回 list 中有效节点的个数 |
4、list element access
| element access | 接口说明 |
|---|---|
| front | 返回 list 的第一个节点的中值的引用 |
| back | 返回 list 的最后一个节点中值的引用 |
5、list modifiers
| modifiers | 接口说明 |
|---|---|
| push_front | 在 list 首元素前插入值为 val 的元素 |
| pop_front | 删除 list 中第一个元素 |
| push_back | 在 list 尾部插入值为 val 的元素 |
| pop_back | 删除 list 中最后一个元素 |
| insert | 在 list position 位置中插入值为 val 的元素 |
| erase | 删除 list position 位置的元素 |
| swap | 交换两个 list 中的元素 |
| clear | 清空 list 中的有效元素 |
#include<iostream>
#include<algorithm>
#include<vector>
#include<list>
#include<functional>
#include<time.h>
using namespace std;
namespace std
{
void test_list1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_front(10);
lt.push_front(20);
lt.push_front(30);
lt.push_front(40);
for(auto e : lt)
{
cout << e << " ";
}
cout << endl;
lt.pop_back();
lt.pop_back();
lt.pop_back();
lt.pop_back();
lt.pop_front();
lt.pop_front();
lt.pop_front();
lt.pop_front();
//lt.pop_front();//err,注意在头删、尾删时要保证list里还有数据,否则这里会报断言错误
for(auto e : lt)
{
cout << e << " ";
}
}
void test_list2()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
//list里也没有提供find,所以这里使用algorithm里的
list<int>::iterator pos = find(lt.begin(), lt.end(), 2);
if(pos != lt.end())
{
lt.insert(pos, 20);
}
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
//clear并不会把头节点清除,这里还可以继续push_back
lt.clear();
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
for(auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
void test_list3()
{
list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
list<int> lt2;
lt2.push_back(2);
lt2.push_back(1);
list<int> lt3;
lt3.push_back(5);
lt3.push_back(1);
lt3.push_back(3);
lt3.push_back(3);
//对于swap,在C++98中建议使用容器里的,而不建议使用算法里的。它们效果一样,但是效率不一样,具体见如下说明
lt1.swap(lt2);
//swap(lt1, lt2);
for(auto e : lt1)
{
cout << e << " ";
}
cout << endl;
for(auto e : lt2)
{
cout << e << " ";
}
cout << endl;
//注意所有的排序都满足,>是降序,<是升序,这里默认是升序
//这个也是一个类模板,它是一个仿函数,所在头<functional>后面我们会实现,sort所在头<algorithm>
/*greater<int> g;
lt3.sort(g);*/
lt3.sort(greater<int>());//同上,可以直接写成匿名对象
for(auto e : lt3)
{
cout << e << " ";
}
cout << endl;
//unique的功能是去重,所在头<algorithm>,去重的前提是排序,升序降序都行,如果不排序它只去去相邻的数据
lt3.unique();
for(auto e : lt3)
{
cout << e << " ";
}
cout << endl;
//erase需要先find,而remove可以直接删除,有就全删,没有就不删,所在头<algorithm>
lt3.remove(3);
for (auto e : lt3)
{
cout << e << " ";
}
cout << endl;
//reverse的功能是逆置,对于带头双向循环链表的逆置比单链表简单的多,所在头<algorithm>
lt3.reverse();
for (auto e : lt3)
{
cout << e << " ";
}
cout << endl;
//merge的功能是合并
//splice的功能是转移,它转移的是节点不是数据,很特殊的场景下才会使用到,我们以后在了解LRU可能还会再接触到
}
void test_OP()
{
srand(time(0));
const int N = 10000;
list<int> lt;
vector<int> v;
v.resize(N);
for (int i = 0; i < N; i++)
{
v[i] = rand();
lt.push_back(v[i]);
}
int begin1 = clock();
sort(v.begin(), v.end());//vector用算法里的,它底层使用的是快排的三数取中法
int end1 = clock();
int begin2 = clock();
lt.sort();//list用容器里的
//sort(lt.begin(), lt.end());//err,本质sort会用两个迭代器相减,而list的迭代器不支持减
int end2 = clock();
cout << "vector sort：" << end1 - begin1 << endl;
cout << "list sort：" << end2 - begin2 << endl;
}
}
int main()
{
std::test_list1();
std::test_list2();
std::test_list3();
std::test_OP();
return 0;
}
📝说明
-
List item
为什么 C++98 建议使用各自容器里的 swap，而不建议使用算法里的 swap ❓
如下可以看到算法里 swap 的 C++98 的实现，无论是 string、vector、list 使用它会涉及深拷贝问题，而且这里的深拷贝代价极大，需要深拷贝 3 次 —— 当 lt1 和 lt2 交换，这里会把 lt1 拷贝构造一份 c，然后把 lt2 赋值于 lt1，c 赋值于 lt2，完成交换。
而如果是容器里的 swap，需要交换 lt1 和 lt2，只需要头指针交换即可。假设是 vector，只要把 lt1 和 lt2 对应的 _start、_finish、_endofstorage 交换即可。相比算法里的 C++98 里的 swap，这里可以认为没有任何代价。
所以说，我们为什么在以后工作中多数不会去写数据结构，而还要学《数据结构》这门学科。因为如果你没有自己去实现数据结构，你不了解链表的结构，我跟你说这 2 个 swap 有深拷贝差异，你可能都听不懂，没有学过《数据结构》的人永远不能理解为什么 top-k 问题用了堆好像效率就高很多。所以我们从 C 语言一路走来，各种各样的模拟实现(小的有 strstr、strcmp；大的有二叉树、list)，其实不是为了造更好的轮子，而是能更好的理解并高效的使用。
-
List item
迭代器补充 ❗
容器迭代器的分类：
a) 使用功能的角度可分为，(正向、反向) + const
b) 容器底层结构的角度可分为，单向、双向、随机
比如单链表迭代器、哈希表迭代器就是单向，特征是能 ++，不能 --；双向链表迭代器、map 迭代器就是双向，特征是能 ++、–；string、vector、deque 迭代器就是随机迭代器，特征是能 ++、–、+、-，一般随机迭代器底层都是一个连续的空间。
可以看到算法里的 sort、reverse 的声明，它的模板参数的命名不是 T，也不是 iterator，对于模板参数的命名可以任意，但是它的命名是有含意的。比如说你要用 sort 这个算法，你要用的是随机迭代器；你要用 reverse 这个算法，你要用的是双向迭代器。随机迭代器也可以使用 reverse，因为随机迭代器是一个双向迭代器，因为它满足双向迭代器的所有功能；同理，双向迭代器也是单向迭代器、随机迭代器也是单向迭代器。也就意味着这里模板参数的命令是单向迭代器，那么你的容器可以是单向、双向、随机；模板参数的命令是双向迭代器，那么你的容器可以是双向、随机；模板参数的命令是随机迭代器，那么你的容器可以是随机。后面学了继承，就可以知道它们满足一个继承关系。
所以这里要明白一个关系
6、list迭代器失效
前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点无效，即该节点被删除了。因为 list 的底层结构为带头结点的双向循环链表，因此在 list 中进行插入时是不会导致 list 的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
#include<iostream>
#include<algorithm>
#include<list>
using namespace std;
namespace std
{
void test_list1()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> lt(array, array + sizeof(array) / sizeof(array[0]));
list<int>::iterator pos = find(lt.begin(), lt.end(), 5);
if(pos != lt.end())
{
//不会失效
lt.insert(pos, 45);
}
for(auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
void test_list2()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> lt(array, array + sizeof(array) / sizeof(array[0]));
list<int>::iterator pos = find(lt.begin(), lt.end(), 5);
if(pos != lt.end())
{
//会失效,可以重新指定迭代器pos
lt.erase(pos);
//pos = lt.erase(pos);//ok
}
cout << *pos << endl;
cout << endl;
}
}
int main()
{
std::test_list1();
std::test_list2();
return 0;
}
📝说明
- 点赞
- 收藏
- 关注作者
评论（0）