【C++第三阶段】list容器&排序

以下内容仅为当前认识，可能有不足之处，欢迎讨论！

---

---

list容器在STL中是双向循环链表。

如图所示，每一个节点三个域，前向指针域，后向指针域，数据域。前向指针域指向前一个结点的地址，后向指针域指向后一个结点的地址，数据与存放该结点数据。第一个结点的前向指针指向最后一个结点的地址；最后一个结点的后向指针指向第一个结点的地址。

但是值得注意的是，插入删除操作不会造成list迭代器的失效，而迭代器在vector中是一次性的。

list优点：

采用动态存储分配，不会造成内存浪费和溢出。

链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素。

list缺点：

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

list有一个重要的性质，插入删除操做不会造成list迭代器的失效，这在vector中是不成立的。

总结：STL中list和vector是两个最常使用的容器，各有优缺点。

构造函数

示例代码：

void test0419a() {
	list<int> lst;
	lst.push_back(10);
	lst.push_back(20);
	lst.push_back(30);
	lst.push_back(40);
	print(lst);

	cout << "区间元素拷贝给本身" << endl;
	list<int> lst2(++lst.begin(), lst.end());
	print(lst2);

	cout << "构造函数将n个elem拷贝给本身" << endl;
	list<int> lst3(3, 6);
	print(lst3);

	cout << "拷贝构造函数" << endl;
	list<int> lst4 = lst2;
	print(lst4);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

运行结果：

赋值和交换

赋值和交换，说的是list容器中，给list容器进行赋值，以及交换list容器。

示例代码：

void test0428a() {
	list<int> lst;
	for (int i = 10; i < 14; i++) {
		lst.push_back(i*2/3+1);
		lst.push_front(i * 3 / 2-1);
	}
	cout << "lst为↓" << endl;
	print(lst);

	list<int> lst2;
	lst2.assign(lst.begin(), lst.end());
	cout << "lst2为↓" << endl;
	print(lst2);

	list<int> lst3;
	lst3 = lst;
	cout << "lst3为↓" << endl;
	print(lst3);

	list<int> lst4;
	cout << "lst4为↓" << endl;
	lst4.assign(10, 100);
	print(lst4);

	swap(lst3, lst4);
	cout << "lst3为↓" << endl;
	print(lst3);
	cout << "lst4为↓" << endl;
	print(lst4);

}
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

运行结果：

大小操作

目的：对容器的大小进行操作

示例代码：

void test0429a() {
	list<int> lst;
	for (int i = 1; i < 4; i++) {
		lst.push_back(i * 2 - 3);
		lst.push_front(i * 3 - 2);
	}
	cout << "lst当前为：";
	print(lst);
	cout << "lst的元素个数：" << lst.size() << "." << endl;
	cout << "lst是空list容器吗？" << endl;
	if (lst.empty()) {
		cout << "lst是空容器。" << endl;
	}
	else {
		cout << "lst不是空容器。" << endl;
	}
	cout << "重新lst裁剪大小为4个" << endl;
	lst.resize(4);
	print(lst);
	cout << "扩充lst为7个，以7填充。" << endl;
	lst.resize(7, 7);
	print(lst);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

运行结果：

插入和删除

目的：对list容器进行数据的插入和删除。

示例代码：

void test0429b() {
	list<int> lst;
	list<int> tsl;
	for (int i = 0; i < 4; i++) {
		lst.push_back(i * 2 - 5);
		lst.push_front(i * 5 - 2);
		tsl.push_back(i);
	}
	cout << "lst当前为↓" << endl;
	print(lst);

	cout << "删除lst头部第一个元素后，lst↓" << endl;
	lst.pop_front();
	print(lst);
	cout << "删除lst尾部最后一个元素后，lst↓" << endl;
	lst.pop_back();
	print(lst);

	list<int> ::iterator begin = lst.begin();

	cout << "在第2个位置插入1个3" << endl;
	lst.insert(++begin, 3);
	print(lst);
	
	cout << "在第3个位置插入4个2" << endl;
	lst.insert(++begin, 4, 2);
	print(lst);

	cout << "lst当前为↓" << endl;
	print(lst);
	cout << "tsl当前为↓" << endl;
	print(tsl);

	cout << "lst尾部插入tsl后，lst为↓" << endl;
	lst.insert(lst.end(), tsl.begin(), tsl.end());
	print(lst);

	cout << "lst删除第一个元素的位置，返回下一个数据的位置为" << endl;
	lst.erase(lst.begin());
	print(lst);

	cout << "此时begin的位置对应的元素是" << *begin << endl;

	cout << "lst删除第begin+1个到最后一个元素的数据后，为↓" << endl;
	lst.erase(++begin, lst.end());
	print(lst);
	
}
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

运行结果：

数据存取

目的：对list容器中数据进行存取

示例代码：

void test0429c() {
	list<int> lst;
	for (int i = -2; i < 3; i++) {
		lst.push_back(i * 2 - 2);
	}
	print(lst);
	cout << "第一个元素值为：" << lst.front() << endl;
	cout << "最后一个元素值为：" << lst.back() << endl;

}
1
2
3
4
5
6
7
8
9
10

运行结果：

list不可以用[]访问容器中的元素，也不可以用at()方式访问容器中的元素。

因为list是链表，不是用连续线性空间存储数据，迭代器也是不支持随机访问的。

反转和排序

目的：①反转list容器内元素；②对list容器进行排序。

反转可以直接用容器内方法，排序

所有不支持随机访问迭代器的容器，不可以用标准算法。

所以，要想对这些容器进行排序，可以使用内部提供的对应算法。

排序默认是升序，如果是降序，则需要写一个对应函数。

示例代码：

void test0429d() {
	list<int> lst;
	for (int i = -2; i < 3; i++) {
		lst.push_back(i * 2 - 2);
		lst.push_front(i * i - 2);
	}
	cout << "now lst -->"<<endl;
	print(lst);
	cout << endl;

	cout << "after reverse,the lst ==" << endl;
	lst.reverse();
	print(lst);
	cout << endl;

	cout << "after sort ,lst == " << endl;
	lst.sort();
	print(lst);
	cout << endl;

	cout << "now sort by function compare , lst == " << endl;
	lst.sort(compare<int>);
	print(lst);
	cout << endl;
}
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

运行结果：

排序案例

案例描述：将person自定义数据类型排序，属性有姓名，年龄，身高。

规则：按照年龄进行升序（默认），如果年龄相同，则按照身高进行降序。

疑问：怎么通过某一个属性进行排序？

看视频解决：通过自定义的排序函数。

示例代码：

#include<iostream>

#include<string>

using namespace std;

#include<list>

template<typename T>
void print(list<T>& lst) {
	for (typename list<T>::iterator lst_front = lst.begin(); lst_front != lst.end(); ++lst_front) {
		cout << *lst_front;
		//cout << "  ";
	}
	cout << endl;
}

class Person {
public:
	Person() {};
	Person(string name, int age, double height) :person_name(name), person_age(age), person_height(height) {};
public:
	string person_name;
	int person_age;
	double person_height;
};

ostream& operator<<(ostream& out, Person& person) {
	cout << person.person_name << "年龄为：" << person.person_age << ",\t身高为：" << person.person_height << "." << endl;
	//在实现operator<<时，最好不要直接使用cout，而应该使用传递给函数的ostream对象out，这可以提高代码的可复用性。——GPT4
	return out;
}


//template <typename Person>
bool person_compare(const Person& per, const Person& son) {
	if (per.person_age == son.person_age) {
		return per.person_height > son.person_height;
	}
	return son.person_age > per.person_age;
}

void test0429e() {
	Person person[5];

	Person One("大道", 20, 1.85);
	person[0] = One;

	Person Two("两极", 19, 1.83);
	person[1] = Two;

	Person Three("三眼", 22, 1.84);
	person[2] = Three;

	Person Four("四象", 22, 1.86);
	person[3] = Four;

	Person Five("五行", 24, 1.88);
	person[4] = Five;

	list<Person> lst_ps;
	for (int i = 0; i < (sizeof(person) / sizeof(person[0])); i++) {
		lst_ps.push_back(person[i]);
	}
	cout << "Person 排序前" << endl;
	print(lst_ps);

	cout << "Person 排序后" << endl;
	lst_ps.sort(person_compare);
	print(lst_ps);

}

int main() {

	test0429e();

	system("pause");
	return 0;
}
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

运行结果：

---

以上是我的学习笔记，希望对你有所帮助！
如有不当之处欢迎指出！谢谢！