【C++】容器list常用接口详解

目录

一.基本介绍

二.list的使用

1.构造函数

2.迭代器

3.遍历方式

4.容量相关操作

5.增删改查

三.list迭代器失效问题

四.算法库函数和list关系

一.基本介绍

1. list是一个带头双向循环链表
2. 由于是链表，物理空间不连续，不支持随机访问数据，因此和vector相比，少了[]访问和resize、reserve等容量相关的函数
3. 与其他序列式容器相比(array,vector,deque），list通常在任意位置进行插入、移除元素的执行效率更好

二.list的使用

1.构造函数

list<int> l1;//无参构造
list<int> l2(10, 1);//用10个1初始化链表

vector<int> v{ 1,2,3,4,5 };
list<int> l3(v.begin(), v.end());//用迭代器区间初始化

2.迭代器

list不支持随机访问， 其底层就不是指针了，但迭代器的底层我们并不关心，只需要将其视为指针使用就行。

 这四个函数都是老朋友了，不多介绍了，但是在带头双向循环链表中，它的位置值得注意不妨用这个代码测试一下：

 当然也有begin()就是rend()，end()是rbegin()这种，这个在后续实现反向迭代器的时候再谈。 

3.遍历方式

迭代器遍历

vector<int> v{ 1,2,3,4,5,6,7,8 };
list<int> l(v.begin(), v.end());
//list<int> l{ 1,2,3,4,5,6,7,8 };

auto it = l.begin();
while (it != l.end())
{
	cout << *it << " ";
	++it;
}
cout << endl;

 范围for遍历

vector<int> v{ 1,2,3,4,5,6,7,8 };
list<int> l(v.begin(), v.end());
//list<int> l{ 1,2,3,4,5,6,7,8 };

for (auto e : l)
{
	cout << e << " ";
}
cout << endl;

注意：list不支持随机访问，因此不能使用[ ] ，也就少了一种普通下标循环遍历 

4.容量相关操作

5.增删改查

大致都和之前的string，vector差不多，不过由于list不像vector一样具有size和capacity，list的clear就是直接清空链表（除头结点外）

三.list迭代器失效问题

由于list底层是带头双向循环链表，因此在插入操作时，pos指向的始终是同一个位置，它们只改变链接关系，并不连续，因此插入操作并不会导致list迭代器失效

但在erase删除操作时list迭代器会失效。erase删除的位置在空间上是唯一的，这个位置的数据被删除后，只是改变了原有的链接关系，此位置已经不在原链表中了，再次使用就会出错 

STL库中的erase使用返回值来解决迭代器失效，返回被删除位置的下一个位置的迭代器 

list<int> l{ 1,2,3,4,5,6,7,8,9 };
auto it = l.begin();
while (it != l.end())
{
	if (*it % 2 == 0)
	{
		it = l.erase(it);
	}
	else
	{
		++it;
	}
}
for (auto e : l)
{
	cout << e << " ";
}
cout << endl;

 四.算法库函数和list关系

迭代器从功能角度可以分为三种：

1. 正向迭代器：forward_iterator ，只支持++
2. 双向迭代器：bidirectional_iterator ，支持++和--
3. 随机迭代器：random_iterator ，支持++，--，+，-

在算法库中常见的函数，例如sort，它的函数模板支持的就是随机迭代器，reverse支持双向迭代器

三类迭代器支持向上兼容，也就是说

• 函数模板给的随机迭代器：只允许随机迭代器
• 函数模板给的双向迭代器：允许随机和双向迭代器 
• 函数模板给的单向迭代器：允许随机、双向和单向迭代器

可见list是双向迭代器，那么它就不能使用库里的sort函数（要求随机迭代器），因此list类自己实现了一个不同于算法库的排序,专门用来排序list的数据 虽然list有自己的sort函数来排序，但当数据很多时，效率低得惊人，因此有了另一种排序list的方法：先将list的数据导入vector容器，再在vector容器中使用算法库的sort排序，排完再导回list中

本文就到这里，下一章将对list进行模拟实战，欢迎持续关注