IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		图片批量下载器
↓批量下载图片,美女图库↓ 		图片自动播放器
↓图片自动播放器↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> C++STL详解(五)list的介绍及其使用 -> 正文阅读

[数据结构与算法]C++STL详解(五)list的介绍及其使用

文章目录

list的介绍及使用

list的介绍

  1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
  2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
  3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能向前迭代，已让其更简单高效。
  4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
  5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

list的使用

list的四种初始化方式
构造函数接口说明
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

下面我们通过代码来看一下list的四种初始化方式

template<class Con>
void PrintContainer(const Con& c)
{
	Con::const_iterator it = c.begin();
	while (it != c.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}


int main()
{
	list<int> lt1;//构造一个空的list

	list<int> lt2(5, 10);//构造的list中包含n个值为val的元素

	list<int> lt3(lt2);//利用拷贝构造初始化

	list<int> lt4(3, 3);

	list<int> lt5(lt4.begin(), lt4.end());//使用一段迭代器区间初始化


	PrintContainer(lt1);
	PrintContainer(lt2);
	PrintContainer(lt3);
	PrintContainer(lt5);
}

在这里插入图片描述

list迭代器的使用
begin和end

此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。

函数声明接口说明
begin()返回第一个元素的迭代器
end()返回最后一个元素下一个位置的迭代器

我们使用正向迭代器来遍历一下list：

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	list<int>::iterator it = lt.begin();
	//正向迭代器遍历该list容器
	while (it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

在这里插入图片描述

rbegin和rend
函数声明接口说明
rbegin()返回第一个元素的reverse_iterator,即end位置
rend()返回最后一个元素下一个位置的reverse_iterator,即begin位置

我们使用反向迭代器来遍历一下list：

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	list<int>::reverse_iterator rit = lt.rbegin();
	//正向迭代器遍历该list容器
	while (rit != lt.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;
}

在这里插入图片描述

list的两种遍历方式
方式一：迭代器遍历
        list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);
	
		//遍历方式1
		list<int>::iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
方法二：范围for遍历
        list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);

        //遍历方式2
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

因为list容器中存储节点的空间是不连续的，因此它不能像vector和string那样使用下标的方式去遍历

list的大小
empty和size
函数声明接口说明
empty()检测list是否为空，是返回true，否则返回false
size()返回list中有效节点的个数

接下来我们通过代码来看一下这两个函数的使用

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	list<int>lt1;

	//判断lt与lt1是否为空
	cout << lt.empty() << endl;
	cout << lt.empty() << endl;

	//获取lt与lt1中有效节点的个数
	cout << lt.size() << endl;
	cout << lt1.size() << endl;
}

在这里插入图片描述

list的元素获取
front和back
函数声明接口说明
front()返回list中第一个节点中值的引用
back()返回list的最后一个节点中值的引用
int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	cout << lt.front() << endl;
	cout << lt.back() << endl;
}

在这里插入图片描述

list的修改操作
push_front与pop_front

push_front函数的作用是在list容器的第一个元素前插入一个数据，而pop_front函数的作用则是在删除list中第一个数据（即头删）

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	//头插
	lt.push_front(7);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	//头删
	lt.pop_front();
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
}

在这里插入图片描述

push_back与pop_back

push_back函数的作用是在list的尾部插入一个数据，而pop_back函数的作用是删除list的最后一个数据

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	//尾插
	lt.push_back(5);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	//尾删
	lt.pop_back();
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
}

在这里插入图片描述

insert

list当中insert函数支持三种插入方式：

  • 在指定迭代器位置插入一个数
  • 在指定迭代器位置插入n个值为val的数
  • 在指定迭代器位置插入一段迭代器区间（左闭右开）
int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	list<int>::iterator pos = find(lt.begin(), lt.end(), 3);

	//在3的前面插入7
	lt.insert(pos, 7);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	pos = find(lt.begin(), lt.end(), 2);

	//在2的前面插入2个1
	lt.insert(pos, 2, 1);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	pos = find(lt.begin(), lt.end(), 1);
	vector<int> v(3, 5);
	//在1的前面插入3个5
	lt.insert(pos, v.begin(), v.end());
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
}

在这里插入图片描述

注意：这里的find函数是头文件algorithm里面的一个库函数，该函数在指定迭代器区间里面寻找特定值的位置，找到了就返回该位置的迭代器。

erase

list中的erase函数支持以下两种删除方式：

  • 删除指定迭代器位置的元素
  • 删除指定迭代器区间的所有元素
int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	list<int>::iterator pos = find(lt.begin(), lt.end(), 3);

	//删除3
	lt.erase(pos);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	//删除list中的所有元素
	lt.erase(lt.begin(), lt.end());
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

}

在这里插入图片描述

swap

swap函数的作用是交换两个list中的数据

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	list<int>lt1;
	lt1.push_back(5);
	lt1.push_back(6);
	lt1.push_back(7);
	lt1.push_back(8);

	lt.swap(lt1);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;

}

在这里插入图片描述

clear

clear函数的作用是清空list中的有效数据，清空后容器的size为0

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);

	cout << lt.size() << endl;
	lt.clear();
	cout << lt.size() << endl;

}

在这里插入图片描述

list的操作函数
sort

sort函数的作用可以将list容器当中的数据默认排成升序。但是尽量少用它，因为效率不高，如果真的想使用排序，我们可以将list的数据放到vector里面然后调用库里面的sort排序。

int main()
{
	list<int> lt;
	lt.push_back(5);
	lt.push_back(9);
	lt.push_back(2);
	lt.push_back(1);
	lt.push_back(4);
	lt.push_back(8);
	lt.push_back(7);

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

	lt.sort();
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

}

在这里插入图片描述

splice

splice函数用于两个容器之间的拼接，有如下三种拼接方式：

  • 将整个容器拼接到另外一个容器的指定迭代器位置
  • 将容器当中的某一数据拼接到另外一个容器的指定迭代器位置
  • 将容器指定迭代器区间的数据拼接到另外一个容器的指定迭代器位置
int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);

	list<int> lt1(3, 2);
	//将容器lt拼接到lt的开头
	lt.splice(lt.begin(), lt1);

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

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

	list<int> lt2(lt);
	list<int> lt3(4, 5);

	//将容器lt3的第一个数据拼接到lt2的开头
	lt2.splice(lt2.begin(), lt3, lt3.begin());
	for (auto e : lt2)
	{
		cout << e << " ";
	}
	cout << endl;

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

	list<int> lt4(3, 3);
	list<int> lt5(2, 6);
	//将容器lt5的所有数据拼接到lt4的末尾
	lt4.splice(lt4.end(), lt5, lt5.begin(), lt5.end());
	for (auto e : lt4)
	{
		cout << e << " ";
	}
	cout << endl;

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

}

在这里插入图片描述

注意：当一个容器的数据被拼接到另一个容器时，该容器的这部分数据在原容器就不存在了（拼接类似于我们windows下剪切的功能）

remove

remove函数的作用是删除容器中的特定元素，并将容器大小缩减为删除的元素数

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);

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

	cout << lt.size() << endl;//5
	//移除容器中等于3的元素
	lt.remove(3);
	cout << lt.size() << endl;//4
	//移除容器中等于30的元素
	lt.remove(30);

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

}

在这里插入图片描述

注意：如果要删除的元素在list容器中不存在，则什么也不做。

unique

unique函数的作用是用于删除容器当中连续的重复元素

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(3);
	lt.push_back(2);
	lt.push_back(4);
	lt.push_back(3);
	lt.push_back(4);

	lt.unique();

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

}

在这里插入图片描述

我们可以看到尽管list中有重复的元素，但是它并没有删除掉这些重复的元素，没有达到去重的效果，因为它只会删除容器中连续的重复元素

因此要想unique函数真正达到去重的效果，我们需要搭配sort来使用才可以达到去重的效果。

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(3);
	lt.push_back(2);
	lt.push_back(4);
	lt.push_back(3);
	lt.push_back(4);

	//搭配sort来使用unique
	lt.sort();
	lt.unique();

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

}

在这里插入图片描述

reverse

reverse函数的作用是将list容器中的元素的位置进行逆置

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	//将容器当中元素的位置进行逆置
	lt.reverse();
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
}

在这里插入图片描述

assin

assin函数的作用是将新的内容分配给容器，替换掉掉容器原来的内容，新内容的分配方式有以下两种：

  • 将n个值为val的数据分配给容器
  • 将一段迭代器区间中的内容分配给容器
int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	//将3个2分配给lt
	lt.assign(3, 2);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	vector<int> v(5, 4);
	//将这段迭代器的内容分配给lt
	lt.assign(v.begin(), v.end());
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

}

在这里插入图片描述

list的迭代器失效问题

我们前面学习了vector，知道vector的insert或者erase可能会导致迭代器失效，那么我们今天所学的list会不会也和vector一样，insert和erase会导致迭代器失效呢？

下面我们就来一起看一下

(insert)插入测试
int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	list<int>::iterator pos = find(lt.begin(), lt.end(), 3);
	//在3的前面插入一个30
	lt.insert(pos, 30);

	cout << *pos << endl;
	cout << endl;

}

运行结果：

在这里插入图片描述

可以看到list的插入是不会导致迭代器失效的。

大家可能会很好奇这里为什么没有导致迭代器失效呢？

前面说过，此处大家可将迭代器暂时理解成类似于指针。既然是指针，只要该指针的指向没变，指针没被释放，那么它都是指向pos位置的值的呀，因此就不会导致迭代器失效。

(erase)删除测试
int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	list<int>::iterator pos = find(lt.begin(), lt.end(), 3);
	//在3的前面插入一个30
	lt.insert(pos, 30);

	//删除3
	lt.erase(pos);

	cout << *pos << endl;

}

运行结果：

在这里插入图片描述

可以看到我们的程序崩溃了，erase会导致list的迭代器失效。

那这个时候可能会又有人问了那这里为什么会导致迭代器失效呢？

前面说过我们这里可以把迭代器当作指针来理解，list的底层结构为带头结点的双向循环链表，我们删除了pos位置的值也就代表我们删除了这个位置的迭代器，删除了指向该结点的指针。那么指向这个结点的指针都被删除了，空间被释放了还给操作系统了，我们再去访问这块空间，程序当然会崩溃。因此这里会导致迭代器的失效，但是失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

总结

list的insert操作不会导致迭代器失效，而erase会导致迭代器失效。迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用：海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题＜有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-02-14 21:25:47  更:2022-02-14 21:26:24 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 17:28:53-

图片自动播放器
↓图片自动播放器↓ 		TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓ 		图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码