C++序列式容器之List的基本使用介绍

写在前面：

之前已经整理过vector的相关知识了，本次博客主要整理的是List的基本介绍，以及其构造方法，成员函数，迭代器、容器属性以及访问修改元素等函数。

List

官方介绍：

C++序列式容器之List的基本使用介绍

list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效

与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。

与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list 的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

既然说list 的底层是双向链表结构，那我们可以大概想到它的逻辑模型：

C++序列式容器之List的基本使用介绍

而之前学的vector的逻辑模型是一个数组

C++序列式容器之List的基本使用介绍

因此可以想到list在插入数据效率是比vector高的，因为list在插入数据是一个O(1)的时间复杂度，只需要开辟空间，然后链上即可

而vector需要重复的移动数据，有时还需要重新开辟空间拷贝数据等，比较的繁琐，而还有更详细的信息请接着向下看：

一、头文件

<list>

二、容器属性

C++序列式容器之List的基本使用介绍

翻译：

容器属性:

序列

序列容器中的元素按严格的线性顺序排列。各个元素按其在此顺序中的位置进行访问。

双链表

每个元素保存关于如何定位下一个和前两个元素的信息，允许在特定元素(甚至整个范围内)之前或之后进行固定时间的插入和删除操作，但不允许直接随机访问也就是说不能像vector那样使用 [下标] 访问。

分配器

容器使用分配器对象动态处理其存储需求。

三、构造函数

构造函数	接口说明
list<T> l1 ();	构造空的list 对象 l1
list<T> l1(size_type n, const value_type& val = value_type());	构造的list中包含n个值为val的元素
list <T> l1(const list& x);	拷贝构造函数
list<T> l1 (InputIterator ﬁrst, InputIterator last)	用[ﬁrst, last)区间中的元素构造l1

例如：

1.构造一个空的 list 对象

2.用n个值为val 的元素来构造 list 对象

注意：这里的类型要与元素的类型一致否则会报错或者精度丢失

出现错误：

C++序列式容器之List的基本使用介绍

精度丢失：

C++序列式容器之List的基本使用介绍

正确示例：

list<int> l1(5,10);
list<string> l2(5,"hello");

C++序列式容器之List的基本使用介绍

注意这里如果没有指定元素的值的话，编译器会自动使用该类型的默认值进行初始化，

例如：int类型的默认值是： 0 、string 类型是："" 空字符串。

3.拷贝构造函数

用另一个list对象来构造另外一个list对象

list<int> l1(3,10);
list<int> l2(l1);//注意拷贝构造同样也要注意两个list对象的类型是否相同

C++序列式容器之List的基本使用介绍

4.使用一段范围[first,last]构造list对象

这就是使用迭代器来表示一段范围内的元素来构造一个list对象

例如：

list<int> l3(5, 10);
	list<int> l5(l3.begin(), l3.end());//使用l3的开始和结尾之间的元素构造l5
	//当然这里不局限于开始和结尾，也可以是新的区间之间的元素，但是前提是要确定迭代器的正确性
	for (auto e : l5)
	{
		cout << e << " ";
	}

C++序列式容器之List的基本使用介绍

四、迭代器

函数声明	接口说明
begin()	返回第一个元素的迭代器
end()	返回最后一个元素下一个位置的迭代器
rbegin()	返回第一个元素的reverse_iterator,即end位置
rend()	返回最后一个元素下一个位置的reverse_iterator,即begin位置
cbegin() (C++11)	返回第一个元素的cosnt_iterator
cend()(C+ +11)	返回最后一个元素下一个位置的const_iterator
crbegin() (C++11)	即crend()位置
crend() (C++11)	即crbegin()位置

和之前学习学习过的string 和vector 一样 list也是同样支持迭代器的操作的，可以使用迭代器来对list对象进行访问和操作

示例：

1. begin() 和 end() 正向普通迭代器

C++序列式容器之List的基本使用介绍

使用迭代器访问和操作元素：

list<int> li;
	li.push_back(1);
	li.push_back(2);
	li.push_back(3);
	li.push_back(4);
	list<int>::iterator ite = li.begin();
	while (ite != li.end())
	{
		cout << *ite << endl;
		++ite;
	}
	//任何一个容器只要支持迭代器  就可以使用范围for进行遍历 实际上底层还是调用的是迭代器
	//支持的操作接口的角度分迭代器的类型 ：单向  forward_list 双向list 随机vector
	for (auto e : li)
	{
		cout << e << endl;
	}

C++序列式容器之List的基本使用介绍

2.rbegin() 和 rend() 反向普通迭代器

例如：

list<int> li;
	li.push_back(1);
	li.push_back(2);
	li.push_back(3);
	li.push_back(4);
	list<int>::reverse_iterator rite = li.rbegin();
	while (rite != li.rend())
	{
		cout << *rite << " ";
		++rite;
	}

C++序列式容器之List的基本使用介绍

相当于就是反向的遍历list对象中的元素注意反向迭代器是：reverse_iterator

当然这两种正向/反向迭代器不仅可以访问元素，而且还可以修改元素的值

例如：

C++序列式容器之List的基本使用介绍

但是下面的const类型的迭代器就不允许修改元素的值，只能对元素进行的访问，也就是可读不可写

3.cbegin() 和 cend() 正向const 迭代器

这种const 迭代器是不允许对迭代器范围内的元素进行修改了，只能访问

例如：

list<int> li;
	li.push_back(1);
	li.push_back(2);
	li.push_back(3);
	li.push_back(4);
	list<int>::const_iterator cite = li.cbegin();
	while (cite != li.cend())
	{
		//*cite = 2;报错
		cout << *cite << " ";
		++cite;
	}

C++序列式容器之List的基本使用介绍

当要对其进行修改时，就会报错显示左值不可修改，这就是const迭代器对其修饰为可读不可写，当有这种需求时可以使用const 迭代器。

4.crbegin() 和 crend() 反向const迭代器

与正向const迭代器一样,只能访问元素，但是不能修改元素。但是是反向遍历的：

list<int> li;
	li.push_back(1);
	li.push_back(2);
	li.push_back(3);
	li.push_back(4);
	list<int>::const_reverse_iterator crite = li.crbegin();//注意这里迭代器的定义
	//const_reverse_iterator  反向const迭代器
	while (crite != li.crend())
	{
		cout << *crite << " ";
		++crite;
	}

C++序列式容器之List的基本使用介绍

注意：

begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动

rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动，而不是所谓的–操作，这样导致只能访问最后一个元素

const迭代器，与普通的如：begin end rbegin rend不同的是：该迭代器指向节点中的元素值不能

修改只能访问

五、容量操作：

C++序列式容器之List的基本使用介绍

1.empty

用来检验容器是不是空的

返回值：

C++序列式容器之List的基本使用介绍

例如：

list<int> l1;
	cout << l1.empty() << endl;
	list<int> l2(5, 1);
	cout << l2.empty() << endl;

C++序列式容器之List的基本使用介绍

可以看到当容器为空时返回为true 当不为空时返回 false

2.size

C++序列式容器之List的基本使用介绍

返回容器中元素的个数

3.max_size

定义：

返回list容器可以容纳的最大元素数。由于已知的系统或库实现限制，这是容器可以达到的最大潜在大小，但容器绝不能保证能够达到该大小：在达到该大小之前，它仍然可能无法在任何点分配存储。

返回值：

C++序列式容器之List的基本使用介绍

对象作为内容可以容纳的元素的最大数量。成员类型size_type是无符号整型

C++序列式容器之List的基本使用介绍

六、元素访问

C++序列式容器之List的基本使用介绍

list 不像 vector 一样支持随机访问因此不能使用 [ ] 进行访问但是可以访问 list的头和尾通过front 和back 来访问。

例如：

C++序列式容器之List的基本使用介绍

七、修改操作函数

函数声明	接口说明
void push_front (const value_type& val)	在list首元素前插入值为 val的元素
void pop_front()	删除list中第一个元素
void push_back (const value_type& val)	在list尾部插入值为val的元素
void pop_back()	删除list中最后一个元素
template <class… Args> void emplace_front (Args&&… args) （C++11）	在list第一个元素前根据参数直接构造元素
template <class… Args> void emplace_back (Args&&… args) （C++11）	在list最后一个元素后根据参数直接构造元素
template <class… Args> iterator emplace( const_iterator position, Args&&… args) （C++11）	在链表的任意位置根据参数直接构造元素
iterator insert (iterator position, const value_type& val)	在list position 位置中插入值为val的元素
void insert (iterator position, size_type n, const value_type& val)	在list position位置插入n 个值为val的元素
void insert (iterator position, InputIterator ﬁrst, InputIterator last)	在list position位置插入 [ﬁrst, last)区间中元素
iterator erase (iterator position)	删除list position位置的元素
iterator erase (iterator ﬁrst, iterator last)	删除list中[ﬁrst, last)区间中的元素
void swap (list& x)	交换两个list中的元素
void resize (size_type n, value_type val = value_type())	将list中有效元素个数改变到n个，多出的元素用val 填充
void clear()	清空list中所有的元素

1.头删、头插、尾插、尾删

这就是list的优点，在头删、头插、尾插、尾删效率会比vector高很多

C++序列式容器之List的基本使用介绍

2.insert 在 pos 位置插入元素

注意这里的位置不是像vector那样的数组的下标，而是要通过迭代器来确定要插入的位置

例如：

list < int> l1;
	l1.push_back(1);
	l1.push_back(2);
	l1.push_back(3);
	l1.push_back(4);
	l1.push_back(5);
	auto pos = find(l1.begin(),l1.end(), 3);//这里使用auto 关键字对变量的类型进行自动推导
	//这里的find实际上也就是通过遍历找到该元素的位置并返回该位置的迭代器
	l1.insert(pos,10);
	for (auto e : l1)
	{
		cout << e << " ";
	}

C++序列式容器之List的基本使用介绍

3.删除pos位置的元素

先来看一段代码：

list < int> l1;
	l1.push_back(1);
	l1.push_back(2);
	l1.push_back(3);
	l1.push_back(4);
	l1.push_back(5);
	auto ite = l1.begin();
	while (ite != l1.end())
	{
		if (*ite % 2 == 0)//这道题的本意是想删除偶数元素
		{
			l1.erase(ite);
		}
		++ite;
	}

但是在运行的时候却发生了错误

C++序列式容器之List的基本使用介绍

先思考一下这里为什么会出现错误：

C++序列式容器之List的基本使用介绍

当我们删除这个位置的迭代器之后，这个迭代器也就已经失效了，不再指向原来的元素，这时候再对其进行 ++ 的操作就是非法操作了，这就是典型的迭代器失效。

那么应该如何正确使用erase 进行删除操作呢？

注意erase的返回值：

C++序列式容器之List的基本使用介绍

指向函数调用删除的最后一个元素后面的元素的迭代器。这是容器如果操作删除了序列中的最后一个元素。

注：这里说的最后一个元素是因为删除的还可能是一段区间之间的元素

因此上面的代码只要在删除元素之后再保存返回的后一个元素的迭代器就可以了：

C++序列式容器之List的基本使用介绍

4.swap 、resize、clear功能

C++序列式容器之List的基本使用介绍

其他常用操作

1.void remove (const value_type& val);

删除具有特定值的元素，从容器中移除所有与Val相等的元素这将调用这些对象的析构函数，并将容器大小缩减为删除的元素数。

和erase不同的是，erase是通过元素的位置(使用迭代器)删除元素，而该函数(list：：Remove)根据元素的值删除元素。一个类似的函数List：：Remove_if存在，它允许一个除相等比较之外的条件来确定是否删除了一个元素。

例如：

C++序列式容器之List的基本使用介绍

2. void unique();删除重复值

C++序列式容器之List的基本使用介绍

3.void sort(); list排序与 void reverse(); 逆置list对象中的元素

C++序列式容器之List的基本使用介绍

C++序列式容器之List的基本使用介绍

List

一、头文件

二、容器属性

三、构造函数

四、迭代器

五、容量操作：

六、元素访问

七、修改操作函数

其他常用操作

继续阅读

面试题:vector和map的区别，异同。空间分布，100万数据存哪个比较合适。一、迭代器区别二、vector三、Map、Set四、vector_map 为什么比map效率高五、如何选择六、容器选择原则七、效率对比

C++ 多线程用条件变量确定线程的执行顺序而不是使用 sleep(1)

POJ 1284 Primitive Roots (欧拉函数&原根定理)

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

成员函数初始化列表

2021-08-13c++——类之操作符重载

swmm与lisflood-fp源码如何一起编译 CMake命令

Windows下VS开发环境环境安装工程项目设置关于Debug和Release的提示

一文看懂字符串的加减乘除

C++ 第十五周报告1--《冒泡法排序》

C++实现简单顺序表

C经典书籍笔记——C陷阱与缺陷②(语法陷阱之优先级)一、错误案列二、优先级规律

线性表之顺序表的实现

C++判断素数、求最大公约数代码判断一个数是否为素数求两个数的最大公约数

SequoiaDB巨杉数据库C++驱动概述

Linux设备模型（中）之上层容器