【STL学习】（5）list-EW帮帮网

前言

STL它的所有容器都共享公共的接口，不同容器按不同方式对其进行扩展。这个公共接口使容器的学习更加容易——我们基于某种容器所学习的内容也都适合于其他容器。每种容器都提供了不同的性能和功能的权衡。

根据前面学习的vector的接口使用也可以很快迁移到list的接口。

一、list的介绍

list的文档介绍

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

二、list的使用

因为STL它的设计、接口风格是一致的，所以list的操作很多与vector一样，大大降低了我们的学习成本，我们重点记忆list与其他容器的不同点即可。

list中的接口较多，这里我们只需要掌握如何正确的使用，然后再去深入研究背后的原理。以下为list中一些常见的重要接口。

1. list 类模板

在这里插入图片描述

list与vector一样有两个模板参数：

T：元素的数据类型

Alloc：空间配置器（内存池），一般我们都使用库中的默认分配器，所以我们不需要关注该模板参数

使用类模板，我们必须显式实例化

类模板的显式实例化：类模板名字<实例化类型>

显式模板参数实参与模板参数的匹配：

显式模板实参按从左到右的顺序与对应的模板参数匹配

注：只有尾部（最右）参数的显式模板实参才可以忽略，但前提是它们可以从函数参数推断出来或为缺省参数

2. list的构造

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

代码示例：

//list的常用构造
void test_list01()
{
	//1、默认构造函数
	list<int> lt1;//构造一个空的list，最常用

	//2、构造包含n个val的list
	list<int> lt2(5, 1);//构造一个初始化为5个1的list

	//3、使用迭代器[first, last)区间中的元素构造list
	list<int> lt3(lt2.begin(), lt2.end());

	//4、拷贝构造
	list<int> lt4(lt3);
}

list的构造函数设计与使用与vector的构造函数基本一样，会vector的构造就会list的构造！

3. list iterator的使用

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

代码示例：

//list的遍历
void test_list02()
{
	list<int> lt;
	for (size_t i = 1; i < 5; ++i)
	{
		lt.push_back(i);
	}
	//正向遍历
	auto it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	//反向遍历
	auto rit = lt.rbegin();
	while (rit != lt.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;
	//范围for
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
}

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

rbegin与rend为反向迭代器，对迭代器执行++操作，迭代器向前移动

list的遍历相较于vector就不适用下标+[]了，因为它的空间不连续，实现代价高，所以list使用迭代器来遍历。（迭代器是通用，任何容器都支持迭代器并且用法类似）

范围for：只要支持迭代器，就可以使用范围for

4. list capacity

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

相较于vector容量操作，list没有提供reserve操作，因为list是链表，它是按需申请空间的，它不需要我们提前开空间了。

因为vector扩容是有代价的，所以vector中提供reserve，避免多次扩容！

5. list element access

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

代码示例：

//list的访问
void test_list04()
{
	list<int> mylist;
	for (size_t i = 0; i < 4; i++)
	{
		mylist.push_back(i);
	}
	for (auto e : mylist)
	{
		cout << e << " ";
	}
	cout << endl;
	//访问链表的首元素
	cout << mylist.front() << endl;
	//访问链表的尾元素
	cout << mylist.back() << endl;
}

6. list modifiers

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

代码示例：

//list的增删查改
void test_list05()
{
	list<int> lt;
	//尾插
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	//头插
	lt.push_front(0);
	//头删
	lt.pop_front();
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	//insert
	//在list第3个位置插入30
	auto it = lt.begin();
	for (size_t i = 0; i < 2; i++)
	{
		it++;
	}
	lt.insert(it, 30);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	//find+insert
	//在3前面插入一个30
	auto pos = find(lt.begin(), lt.end(), 3);
	if (pos != lt.end())
	{
		lt.insert(pos, 30);
		//insert之后不存在迭代器失效问题
		*pos *= 100;
	}
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	//find+erase
	//删除2
	pos = find(lt.begin(), lt.end(), 2);
	if (pos != lt.end())
	{
		lt.erase(pos);
		//erase之后存在迭代器失效问题
		//*pos *= 100;
	}
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	//如何解决erase之后迭代器失效的问题——接收erase的返回值
	it = lt.begin();
	while (it != lt.end())
	{
		//删除list的所有偶数
		if (*it % 2 == 0)
		{
			it = lt.erase(it);
		}
		else
		{
			++it;
		}
	}
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
}

在vector中头插头删的代价比较高所以没有直接提供头插头删，但是在list中可以在常数时间内对任意位置插入和删除，所以list直接提供的头插和头删。

insert：在position位置之前插入值为val的元素

从string之后，insert就变了，之前string我们以下标来插入，但容器是以迭代器来插入

list迭代器与vector迭代器还是有差异的，比如我要在第5个位置插入数据，vector可以直接insert(v.begin + 5，val)；而list不可以直接+5，只能从头开始向后迭代5次。因为vector的底层是一个连续的空间，所以它的迭代器支持‘+’；而list的底层不是一个连续的空间，它的迭代器不支持‘+’，实现代价太高了。

list的insert不存在迭代器失效的问题，因为它插入数据不存在野指针问题（扩容）和位置变了（向后挪动数据）的问题。

find：查找，例如：在3的前面插入一个30

vector和list都没有提供find，find是算法（algorithm）提供的

STL中把容器（存数据）和算法（处理数据）分开，通过迭代器将其关联

迭代器不关心容器的底层结构，操作统一，是通用的

算法中find是一个函数模板，其功能是在一个迭代器区间[first，last)中查找一个值，找到了就返回它的迭代器（范围中与该值相等的第一个元素的迭代器），没有找到就返回last

erase：删除list position位置的元素

erase之后存在iterator失效（野指针）

如何解决erase之后迭代器失效的问题——接收erase的返回值

7. list的其他操作

函数声明	接口说明
reverse	逆置链表
sort	链表排序
merge	归并两个有序链表
unique	去重，删除重复的值
remove	删除与val相等的所有元素
splice	转移：将链表结点转移到另一个链表

代码示例1：逆置链表

void test_list06()
{
	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;
	//1.reverse链表逆置，该设计有些冗余，因为调用算法库中的reverse也可以实现逆置，并且他们的设计是基本一样的
	//硬要说优点的话，就是使用便捷了一些
	//①调用list中的reverse
	lt.reverse();
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	//②调用算法库中的reverse
	reverse(lt.begin(), lt.end());
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
}

reverse：逆置链表容器中元素的顺序

reverse链表逆置，该设计有些冗余，因为调用算法库中的reverse也可以实现逆置，并且他们的设计是基本一样的

硬要说优点的话，就是使用便捷了一些

代码示例2：链表排序

//list的其他操作
void test_list06()
{
	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;

	//2、sort：list排序
	//①调用list中的sort
	lt.sort();
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	//②调用算法库中的sort——报错
	/*sort(lt.begin(), lt.end());
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;*/
}
//测试list和vector排序的效率
void test_op()
{
	srand(time(0));
	const int N = 100000;
	vector<int> v;
	v.reserve(N);
	list<int> lt1;
	list<int> lt2;

	for (int i = 0; i < N; ++i)
	{
		auto e = rand();
		lt2.push_back(e);
		lt1.push_back(e);
	}

	// 拷贝到vector排序，排完以后再拷贝回来
	int begin1 = clock();
	// 先拷贝到vector
	for (auto e : lt1)
	{
		v.push_back(e);
	}

	// 排序
	sort(v.begin(), v.end());

	// 拷贝回去
	size_t i = 0;
	for (auto& e : lt1)
	{
		e = v[i++];
	}

	int end1 = clock();

	int begin2 = clock();
	lt2.sort();
	int end2 = clock();

	printf("vector sort:%d\n", end1 - begin1);
	printf("list sort:%d\n", end2 - begin2);
}

sort：对链表中的元素进行排序，改变它们在容器中的位置

链表排序不可以调用算法库中的sort来排序，因为算法库中的sort是使用快排来排序的，快排有三数取中，不适合链表这种不连续的空间

list的底层结构决定了它的迭代器属于双向迭代器，而算法库中sort的使用的是随机迭代器，所以list排序不能调用算法库中的sort

算法使用的迭代器类型就决定了什么容器可以调用！

iterator从性质（即容器底层结构决定）分类：

单向迭代器，只支持++，例如单链表forward_list/unordered_mapunor

双向迭代器，支持++/–，例如带头双向循环链表list/map/set

随机迭代器，支持++/–/+/-，例如vector/string/deque

他们本质上是一个继承关系：双向继承单向，随机继承双向

子类满足父类的所有性质

他们的调用关系，类似引用的使用相反，可以权限放大，但是不可以权限缩小。例如：算法他要求你传单向迭代器，你可以传单向、双向、随机迭代器（可以权限放大）；算法他要求你传随机迭代器，你就只可以传随机迭代器，不可以传单向、双向迭代器（不可以权限缩小）

list中的sort可以认为有意义，也可以认为没有意义

在实际开发中，list就不应该用来排序，应该使用vector排序

list中的sort是使用归并来排序，而vector中是调用算法库中的sort（快排）来排序的，在数据量越大时快排的效率相较于归并的效率越快！

在数据量小的时候可以使用list中的sort排序，方便。但是在实际开发中需要排序的数据量都是较大的，所以list排序意义不大

如果非要使用list排序的话，可以先将数据拷贝到vector，在vector中排好序之后，在拷贝回list即可。

总结：平时练习时数据量少（即一万左右）可以使用list排序方便，但在实际开发中数据量大尽量不要使用list排序！

代码示例3：归并&去重&删除

//list的其他相关操作(了解)
void test_list07()
{
	//1、merge：将second归并到first(前提：两个链表有序)
	list<double> first, second;

	first.push_back(3.1);
	first.push_back(2.2);
	first.push_back(2.9);

	second.push_back(3.7);
	second.push_back(7.1);
	second.push_back(1.4);

	first.sort();
	second.sort();

	first.merge(second);

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

	//2、unique：去重，删除重复的值(前提：链表有序)
	double mydoubles[] = { 12.15,  2.72, 73.0,  12.77,  3.14,
					   12.77, 73.35, 72.25, 15.3,  72.25 };
	std::list<double> mylist(mydoubles, mydoubles + 10);

	mylist.sort();             //  2.72,  3.14, 12.15, 12.77, 12.77,
							   // 15.3,  72.25, 72.25, 73.0,  73.35

	mylist.unique();           //  2.72,  3.14, 12.15, 12.77
							   // 15.3,  72.25, 73.0,  73.35
	for (auto e : mylist)
	{
		cout << e << " ";
	}
	cout << endl;

	//3、remove：删除与val相等的所有值(相当于find+erase，find找到就删，找不到就不删)
	int myints[] = { 17,89,7,14 };
	std::list<int> mylist1(myints, myints + 4);

	mylist1.remove(89);

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

merge：将second归并到first(前提：两个链表有序)

unique：去重，删除重复的值(前提：链表有序)

remove：删除与val相等的所有值(相当于find+erase，find找到就删，找不到就不删)

代码示例4：链表转移

//list的其他操作
void test_list08()
{
	std::list<int> mylist1, mylist2;
	std::list<int>::iterator it;

	// set some initial values:
	for (int i = 1; i <= 4; ++i)
		mylist1.push_back(i);      // mylist1: 1 2 3 4

	for (int i = 1; i <= 3; ++i)
		mylist2.push_back(i * 10);   // mylist2: 10 20 30

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

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

	it = mylist1.begin();
	++it;                         // points to 2

	// 1、全部转移
	mylist1.splice(it, mylist2);

	//2、转移一个
	//mylist1.splice(it, mylist2, ++mylist2.begin());

	// 3、部分转移(注：可以自己转移自己，但是不要形成闭环！)
	//mylist1.splice(mylist1.begin(), mylist1, ++mylist1.begin(), mylist1.end());

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

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

splice：将链表结点转移到另一个链表

第一个版本(1)将x的所有元素传输到容器中。

第二个版本(2)只将x指向i的元素传输到容器中。

第三个版本(3)将范围[first,last]从x传输到容器中。

链表的使用现在我们了解这些常见的接口即可！

【STL学习】（5）list

前言

一、list的介绍

二、list的使用

1. list 类模板

2. list的构造

3. list iterator的使用

4. list capacity

5. list element access

6. list modifiers

7. list的其他操作

网站公告

今日签到

热门文章

最新发布