STL常用容器—list容器（链表）_c++ stl 链表

参考博文1: ＜C++＞ list容器本质|常用接口|自定义排序规则
参考博文2：STL常用容器—— list 容器的使用

  本文主要整理总结C++ STL中list（链表）常用容器的常用方法的操作，关于链表的底层设计与C语言实现请参考博文：【数据结构与算法】——单链表的原理及C语言实现

一、list容器基本概念

  list 容器 的本质是一个双向循环链表，用于存储的每个结点包含数据域和指针域：

示意图：

名词解释：

• begin 和 end 都是迭代器，可以看成指针来操作
  begin 对应的是容器首个元素，而end 对应容器最后一个元素的下一个位置
• prev 和 next 代表前驱指针和后继指针，并不是 list 容器的接口，指针域用来存储下一个结点的地址
• front 和 back 分别是第一个和最后一个结点的数据域
• push_back、push_front、pop_back、pop_front 代表尾插、头插、尾删、头删

通过前驱后继指针可以将每个结点连接起来，头结点的前驱与尾结点后继指针都指向null
由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于双向迭代器

list的优点：

• 采用动态存储分配，不会造成内存浪费和溢出
• 可以对任意位置进行快速插入或删除元素，修改指针即可，不需要移动大量元素

list的缺点：

• 链表灵活，但是空间（指针域）和 时间（遍历）额外耗费较大

STL中List和vector是两个最常被使用的容器，各有优缺点

二、list容器基本操作与常用方法

1. list构造函数

示例：

list<int> list1;
list1.push_back(10);
list1.push_back(20);
list1.push_back(30);

list<int> list2={2,4,6,8};//构造并初始化
list<int> list3(5,100);		//5个100
list<int> list4(list1);		//拷贝list1

//list2的部分区间
list<int> list5(++list2.begin(), --list2.end());		

cout << "list1: ";	showList(list1);
cout << "list2: ";	showList(list2);
cout << "list3: ";	showList(list3);
cout << "list4: ";	showList(list4);
cout << "list5: ";	showList(list5);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

其中showList：

void showList(list<int> &list)
{
	for(int item:list)
		cout << item  << " ";
	cout << endl;
}
1
2
3
4
5
6

2. ☆list 插入和删除

示例：

void test()
{
	
	list<int> list1;
	//尾插
	list1.push_back(2);	
	list1.push_back(4);
	//头插
	list1.push_front(10);
	list1.push_front(30);
	cout << "list1 push back + front: ";
	showList(list1);			//30 10 2 4

	//尾删
	list1.pop_back();
	cout << "pop back: ";	
	showList(list1);			//30 10 2

	//头删
	list1.pop_front();
	cout << "pop front: ";	
	showList(list1);			//10 2

	//头+1插
	list1.insert(++list1.begin(), 666);
	cout << "front insert: ";	
	showList(list1);			//10 666 2

	//头+1删
	list1.erase(++list1.begin());
	cout << "front+1 erase: ";	
	showList(list1);			//10  2
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

3. list 获取头尾数据

  list 容器不支持随机访问，不提供下标操作符 [] 和 at() 成员函数，也没有提供 data() 成员函数。
  只能使用 front() 和 back() 成员函数，或者使用 list 容器迭代器访问或修改元素的值。

使用 front() 和 back() 成员函数

int main()
{
	list<int> list1 = {2,4,6,8,10};
	
	//获取元素引用
	int& first = list1.front();
	int& last  = list1.back();
	cout << first << " " << last << endl;
	
	//修改元素
	first = 100;
	last  = 200;
	cout << list1.front() << " " << list1.back() << endl;
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

注意：

• list容器中不可以通过[]或者at方式访问数据
• 返回第一个元素 — front
• 返回最后一个元素 — back

使用 list 容器迭代器

int main()
{
	list<int> list1 = {2,4,6,8,10};
	auto it = list1.begin();	//迭代器指向头
	while(it != list1.end())	//迭代遍历
	{
		cout << *it << " ";
		it++;					//迭代器自增
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11

注意： list容器的迭代器类型为双向迭代器，而不是和之前的array、vector容器一样是随机访问迭代器。

双向迭代器特性：假如it1，it2都是双向迭代器，那么：

支持：++it1、 it1++、 it1- -、 it1++、 *it1、 it1 == it2 以及 it1 != it2
不支持：it1[i]、it1-=i、 it1+=i、 it1+i 、it1-i、it1 < it2、it1 > it2、 it1 <= it2、 it1 >= it2

4. list 大小操作

示例程序：

void test()
{
	list<int> list1 = {10,20,30};
	list<int> list2 = {2,4,6,8,10};
	
	if(!list1.empty())
	{
		cout << "size: " << list1.size() << endl;
		list1.resize(5);	//重置大小为5个，以默认值填充
		cout << "resize: " << list1.size() << endl;
		showList(list1);
	}
	else
		cout << "容器为空" << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

5. list赋值和交换

示例：

list<int> list1 = {10,20,30};
list<int> list2 = {2,4,6,8,10};

list1 = list2;			
showList(list1);	//2,4,6,8,10

list1.assign(5,100);	
showList(list1);	//5个100

list1.assign(++list2.begin(),--list2.end());	
showList(list1);	//4,6,8

list1.swap(list2);
showList(list1);	//2,4,6,8,10
showList(list2);	//4,6,8
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

6. list 反转和排序

示例：

//用于降序排序
bool myCompare(int v1, int v2)
{
	//降序：让第一个数 > 第二个数
	return v1 > v2;
}

void test03()
{
	list<int> list1 = {6,4,2,10,3};
	cout << "src data: ";	showList(list1);
	
	//降序排序
	list1.sort(myCompare);
	cout << "sort: "; 		showList(list1);
	
	//反转
	list1.reverse();
	cout << "reverse: ";	showList(list1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

sort 是 list 容器内部的排序方法，默认为升序排列，需要通过自己编写函数（仿函数）来决定排序的规则。

三、排序案例

案例描述： 将Person自定义数据类型进行排序，Person中属性有姓名、年龄、身高
排序规则： 按照年龄进行升序，如果年龄相同按照身高进行降序

示例程序：

/******************自定义Person类****************/
class Person {
public:
	Person(string name, int age , int height)
	{
		this->name = name;
		this->age = age;
		this->height = height;
	}

public:
	string name;  //姓名
	int age;      //年龄
	int height;   //身高
};
/*****************定义仿排序顺序 仿函数**************/
bool PersonCompare(Person &p1, Person &p2)
{
	if(p1.age == p2.age)	//年龄相同 按身高降序
	{
		if(p1.height > p2.height)
			return true;
		else
			return false;
	}
	else	//按年龄升序
	{
		if(p1.age < p2.age)
			return true;
		else
			return false;
	}		
}
/****************遍历容器函数**************/
void showPersonList(list<Person> &list)
{
	auto it = list.begin();
	for( ; it != list.end(); it++)
	{
		cout << "name: " << it->name << "\tage: " << it->age;
		cout << "\t\theight: " << it->height << endl;
	}
}
/*****************主程序 测试程序*************/
void test04()
{
	Person p1("张三", 22, 170);
	Person p2("李四", 21, 173);
	Person p3("王五", 20, 168);
	Person p4("陈六", 25, 177);
	Person p5("赵七", 22, 180);
	list<Person> list1 = {p1,p2,p3,p4,p5};

	//排序前
	cout << "before sort: " << endl; 
	showPersonList(list1);
	
	//自定义排序
	list1.sort(PersonCompare);
	//显示排序后结果
	cout << "after sort: " << endl; 
	showPersonList(list1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

程序输出：

总结：

• 对于自定义数据类型，必须要指定排序规则，否则编译器不知道如何进行排序
• 高级排序只是在排序规则上再进行一次逻辑规则制定，并不复杂