【C++】list（上）

s-little-monster

发布于 2024-09-09 10:14:10

590

发布于 2024-09-09 10:14:10

文章被收录于专栏：乐意学点小编程

一、list的介绍和使用

1、list的介绍

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

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

list的优点是在任意位置进行插入和移除元素执行效率高，缺点就是不能支持随机访问

2、list的使用

（1）list的构造

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

void test1()
{
	list<int> lt1(10, 1);
	list<int> lt2;
	list<int> lt3(lt1);
	list<int> lt4(lt1.begin(), lt1.end());

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

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

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

构造函数、拷贝构造函数正常

这里的lt2还有原始视图是空构造

（2）list 迭代器的使用

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

值得注意的是，rbegin和rend为反向迭代器，对迭代器执行++操作，迭代器向前移动，也就是说forward_list也就是单链表是没有rbegin和rend迭代器的

void test2()
{
	list<int> lt1(10, 0);
	auto it = lt1.begin();
	int i = 1;

	for (auto& e : lt1)
	{
		e += i;
		i++;
	}

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

（3）list 容量的使用

函数声明	接口说明
empty	检测list是否为空
size	返回list中节点的有效个数

void test3()
{
	list<int> lt1(10, 0);
	list<int> lt2;
	cout << lt1.empty() << " ";
	cout << lt1.size() << endl;
	cout << lt2.empty() << " ";
	cout << lt2.size() << endl;
}

（4）list元素访问

函数声明	接口说明
front	返回list第一个节点值的引用
back	返回list最后一个节点值的引用

void test4()
{
	list<int> lt1(10, 0);
	lt1.front() = 1;
	lt1.back() = 2;

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

（5）list修改

函数声明	接口说明
push_front	在list第一个元素之前插入一个元素
pop_front	删除list第一个元素
push_back	在list最后一个元素之后插入一个元素
pop_back	删除list最后一个元素
insert	在pos位置插入一个元素
erase	删除pos位置的元素
swap	交换两个list中的元素
clear	清空list中的有效元素

void test5()
{
	list<int> lt1(10, 0);
	//插入
	lt1.push_front(1);
	lt1.push_back(2);
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
	//删除
	lt1.pop_front();
	lt1.pop_back();
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;

	int i = 1;
	for (auto& e : lt1)
	{
		e += i;
		i++;
	}
	//insert/erase
	auto it = find(lt1.begin(), lt1.end(), 5);
	lt1.insert(it, 11);
	lt1.erase(it);

	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
	//swap
	list<int> lt2(10, 1);
	lt1.swap(lt2);
	for (auto e : lt2)
	{
		cout << e << " ";
	}
	cout << endl;
	//clear
	lt1.clear();
	cout << lt1.empty() << endl;
}

使用方面都挺简单的，不再叙述了，参数直接查cplusplus就行

（6）list迭代器失效

因为list的底层结构为带头节点的双向循环链表，所以在list中进行插入是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他的迭代器不受影响

二、list与vector的对比

list和vector都是STL中重要的序列式容器，二者在接口上基本相同，但在底层实现上有巨大的差异，我们来对比一下

对比	vector	list
底层结构	动态顺序表，一段连续空间	带头节点的双向循环列表
随机访问	支持随机访问，访问某个元素效率O(1)	不支持随机访问，访问某个元素效率O(N)
插入和删除	任意位置插入和删除效率低，需要移动元素，时间复杂度为O(N)，插入时有可能需要增容，开辟新空间，拷贝元素，释放旧空间，导致效率更低	任意位置插入和删除效率高，不需要移动元素，时间复杂度为O(1)
空间利用率	底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高	底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低
迭代器	原生态指针	对原生态指针进行封装
迭代器失效	在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效	插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响
使用场景	需要高效存储，支持随机访问，不关心插入删除效率	大量的插入和删除操作，不关心随机访问

两者使用场景不同，各有千秋，在使用的时候合理搭配，就可以发挥最大价值

三、list其他接口

在图中可以看到，list除了常用的几种接口以外，还有其他的功能的接口，这里简单介绍一下，学习还需要到cplusplus网站上详细参考参数返回值以及一系列的内容

1、splice

将某个list移动到另一个容器当中，有三种方式：一是将list中的所有元素都传输到容器中，二是仅将迭代器指向的元素从list传输到另一个容器当中，第三个就是迭代器范围传输，从first迭代器到last迭代器的元素传输到另一个容器当中

void test6()
{
	list<int> lt1(10, 0);
	list<int> lt2(10, 1);
	lt1.splice(lt1.begin(),lt2);
	for (auto e : lt1)
	{
		cout << e << " ";
	}
}

2、remove

与erase可以相比较，它们都是删除接口，而erase的参数是一个迭代器，而remove的参数是一个值，它的作用是删除所有等于某个值的元素，然后调整容器大小

void test7()
{
	list<int> lt1(10, 0);
	int i = 1;
	for (auto& e : lt1)
	{
		e += i;
		i++;
	}
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
	lt1.remove(5);
	for (auto e : lt1)
	{
		cout << e << " ";
	}
}

3、unique

删除连续相等的除了一个以外的元素

void test8()
{
	list<int> lt1(10, 0);
	list<int> lt2(10, 1);
	lt1.splice(lt1.begin(), lt2);
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
	lt1.unique();
	for (auto e : lt1)
	{
		cout << e << " ";
	}
}

4、sort

void test9()
{
	list<int> lt1(10, 0);
	int i = 10;
	for (auto& e : lt1)
	{
		e += i;
		i--;
	}
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
	lt1.sort();
	for (auto e : lt1)
	{
		cout << e << " ";
	}
}