20. C++STL 6(详解list的使用,vector和list的比较和优缺点)

发布于:2024-12-06 ⋅ 阅读:(104) ⋅ 点赞:(0)

⭐本篇重点:list的使用,list和vector的比较

⭐本篇代码:c++学习 · 橘子真甜/c++-learning-of-yzc - 码云 - 开源中国 (gitee.com)

目录

一. list介绍

二. list的使用

2.1 构造函数

2.2 list的迭代器和遍历访问

2.3 list的增删查改 

2.4 list迭代器失效的问题

三. vector和list的比较 


一. list介绍

list文档:list文档

        1 list是STL中的一个序列式容器,它在任意位置的插入和删除的时间复杂度都是O(1),并且可以支持双向迭代。

        2 list的底层是一个双向链表,数据存储在节点中,每一个节点还存在指向前一个元素和指向后一个元素的指针。更准确的说,list是带头双向循环链表

        3 list和forward_list非常相似,不过forword是单向链表,只能单方向迭代。

        4 list和其他序列式容器(vector,queue)相比,优点是在任意位置插入和删除元素的时间复杂度都是O(1),list最大的缺点是不能够支持任意位置的随机访问,访问list中的元素时间复杂度为O(n)。

二. list的使用

2.1 构造函数

构造函数 接口说明
list() 构造空的list
list (const list& x) list的拷贝构造函数
list (size_type n, const value_type& val = value_type()) 构造的list中包含n个值为val的元素
list (InputIterator first, InputIterator last) 用迭代器[first, last)区间中的元素构造list

2.2 list的迭代器和遍历访问

iterator 解释
begin() 获取第一个数据位置 iterator/ const_iterator
end() 获取最后一个数据位置 iterator/ const_iterator
rbegin() 获取最后一个数据位置 reverse_iterator
rend() 获取最后一个数据位置 reverse_iterator

其中begin()和end()是正向迭代器,++迭代器向后移动

rbegin()和rend()是正向迭代器,++迭代器向前移动

list的迭代器的使用非常像指针

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <list>
using namespace std;

//遍历
void test1()
{
	list<int> l;
	for (int i = 0; i < 10; i++)
		l.push_back(rand());

	//1.迭代器遍历
	list<int>::iterator it = l.begin();
	while (it != l.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	//2.迭代器逆向遍历
	auto rit = l.rbegin();
	while (rit != l.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;


	//2. C++11 for循环
	for (const auto& e : l)
		cout << e << " ";
	cout << endl;
}

int main()
{
	test1();
}

运行结果如下:

 2.3 容量和获取元素接口

容量接口 说明
size() 返回list中元素的个数
empty() 判断list是否为空

list可以获取第一个元素和最后一个元素

获取元素接口 说明
front() 获取第一个元素
back() 获取最后一个元素

测试代码:

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <list>
using namespace std;

void test()
{
	list<string> l = { "YZC","yzc","Hello world!"};
	cout << l.size() << endl;
	cout << l.empty() << endl;

	cout << l.front() << endl; //YZC
	cout << l.back() << endl;  //Hello world!
}

int main()
{
	test();
	return 0;
}

 测试结果:

2.3 list的增删查改 

函数接口的声明 解释
push_back 在list尾元素的后面插入一个数据
push_front 在list首元素的前面插入一个数据
pop_back 删除list的尾数据
pop_front 删除list的首数据
insert 在给定的pos位置插入数据val
erase 删除给定的pos位置的数据
swap 交换两个list中的元素
clear 清空所有的元素

这些接口较为简单,不一一举例

2.4 list迭代器失效的问题

和vector一样,list也有迭代器失效的问题。但是list问题没有那么严重

例如:

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <list>
using namespace std;

//遍历
void test()
{
	list<string> l = { "YZC","yzc","abc","def","123","Hello world!" };
	auto pos = find(l.begin(), l.end(), "123");
	cout << "插入数据之前:" << *pos << endl;
	l.insert(pos, "456");
	//这里插入数据后,迭代器并没有失效。
	//因为list开辟空间不会销毁旧的空间,而是开辟空间后和其前后节点链接在一起	
	cout << "插入数据之后:" << *pos << endl;
}

int main()
{
	test();
	return 0;
}

运行结果 

如果使用erase删除一个元素,则这个位置的迭代器失效。但不会影响其他数据

比如我们删除数列中的偶数

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <list>
using namespace std;

//迭代器失效,迭代器失效没啥事,但是不能继续访问该迭代器
void test()
{
	list<int> l = { 1,2,3,4,5 ,6,7,8,9,10 };
	auto it = l.begin();
	while (it != l.end())
	{
		if (*it % 2 == 0)
		{
			l.erase(it);//迭代器失效
			//要改成
			//it = l.erase(it);//会返回删除位置的下一个位置的迭代器
		}
		else
		{
			++it;
		}	
	}

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

int main()
{
	test();
	return 0;
}

如果直接删除而不更新it的话,迭代器会失效

需要使用it = l.erase(it) 获取下一个位置的迭代器防止失效

更改代码

三. vector和list的比较 

1. 既然有了vector,为什么会有list?

        vector和list就像数组和链表的比较。list的目的就是弥补vector的缺点

vector的缺点:

        1 在头部和中部插入删除数据效率低。

        2 插入数据如果要扩容,会开辟新空间,移动数据,销毁旧空间。消耗大

        3 有一部分的空间浪费

vector的优点:

        可以支持随机访问,所以能够支持排序,二分,堆算法等

list的优点

        1 在任意位置插入删除数据效率高,时间复杂度O(1)

        2 list插入数据,只需要开辟新节点。不需要销毁旧空间,挪动数据

list的缺点

        不支持随机访问,所以访问和查找数据效率低。

所以:在实际中,list和vector是搭配使用的!


网站公告

今日签到

点亮在社区的每一天
去签到