[数据结构与算法]C++学习笔记——STL【容器：list】

list 的基本概念

list 链表，是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的。

链表的功能：将数据进行链式存储。

链表的组成：链表由一系列结点组成。

链表的节点由两部分组成：

• 存储数据元素的数据域
• 存储下一个结点地址的指针域

STL中的 list 是一个双向循环链表。

由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于双向迭代器

list 的优点：

• 采用动态存储分配，不会造成内存浪费和溢出
• 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
• 插入操作和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的（STL中list和vector是两个最常被使用的容器，各有优缺点）

list 的缺点：

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

构造函数

功能描述：

• 创建list容器

函数原型：

• list<T> lst; //list采用采用模板类实现,对象的默认构造形式：
• list(beg,end); //构造函数将[beg, end)区间中的元素拷贝给本身。
• list(n,elem); //构造函数将n个elem拷贝给本身。
• list(const list &lst); //拷贝构造函数。

#include<iostream>
#include<string>
#include<list>

using namespace std;

// 打印输出list
void print_list1(const list<int>& mylist) {
	// 通过只读迭代器遍历链表
	for (list<int>::const_iterator ite = mylist.begin(); ite != mylist.end(); ite++) {
		cout << *ite << " ";
	}
	cout << endl;
}

int main() {
	/*无参数构造函数*/
	list<int> list1;
	/*在容器的尾部插入一个元素*/
	list1.push_back(1);
	list1.push_back(2);
	list1.push_back(3);
	list1.push_back(4);
	print_list1(list1); // 1 2 3 4

	/*使用list1迭代器指向区间元素构造list2*/
	list<int> list2(list1.begin(),list1.end());
	print_list1(list2);// 1 2 3 4

	/*使用 5 个888构造 list3*/
	list<int> list3(5, 888);
	print_list1(list3); // 888 888 888 888 888

	/*拷贝构造函数*/
	list<int> list4(list3);
	print_list1(list4); // 888 888 888 888 888

	return 0;
}

赋值和交换

功能描述：

• 给list容器进行赋值，以及交换list容器

函数原型：

• assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。
• assign(n, elem); //将n个elem拷贝赋值给本身。
• list& operator=(const list &lst); //重载等号操作符
• swap(lst); //将lst与本身的元素互换。

#include<iostream>
#include<string>
#include<list>

using namespace std;

void print_list2(const list<int>& mylist) {
	for (list<int>::const_iterator ite = mylist.begin(); ite != mylist.end(); ite++) {
		cout << *ite << " ";
	}
	cout << endl;
}

int main() {
	list<int> list1;
	list1.push_back(1);
	list1.push_back(2);
	list1.push_back(3);
	list1.push_back(4);
	print_list2(list1); // 1 2 3 4

	/*将list1 的第二个至倒数第二个区间内的元素复制到list2中*/
	list<int> list2;
	list2.assign(list1.begin(), list1.end()); 
	print_list2(list2); // 1 2 3 4

	/*将 5 个 999 存入list3中*/
	list<int> list3;
	list3.assign(5,9);
	print_list2(list3); // 9 9 9 9 9

	/*重载赋值操作符*/
	list<int> list4 = list3;
	print_list2(list4); // 9 9 9 9 9

	/*交换 list1 和 list 中的元素*/
	list1.swap(list4);
	print_list2(list1); // 9 9 9 9 9
	print_list2(list4); // 1 2 3 4

	return 0;
}

大小操作

功能描述：

• 对list容器的大小进行操作

函数原型：

• size(); //返回容器中元素的个数

• empty(); //判断容器是否为空

• resize(num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。

  ? //如果容器变短，则末尾超出容器长度的元素被删除。

• resize(num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

#include<iostream>
#include<string>
#include<list>

using namespace std;

void print_list3(const list<int>& mylist) {
	for (list<int>::const_iterator ite = mylist.begin(); ite != mylist.end(); ite++) {
		cout << *ite << " ";
	}
	cout << endl;
}

int main() {
	list<int>list1;
	for (int i = 0; i < 10; i++) {
		list1.push_back(i*i+1);
	}
	print_list3(list1); // 1 2 5 10 17 26 37 50 65 82
	/*判断list是否为空*/
	cout << (list1.empty() ? "为空" : "不为空" )<< endl;
	/*获取list的大小*/
	cout << "list1的大小：" << list1.size() << endl;

	/*重新设置list1的大小，list1变大多余的位置以0填充*/
	list1.resize(15);
	print_list3(list1); // 1 2 5 10 17 26 37 50 65 82 0 0 0 0 0

	/*重新设置list1的大小，list1变大多余的位置以999填充*/
	list1.resize(20,1);
	print_list3(list1); // 1 2 5 10 17 26 37 50 65 82 0 0 0 0 0 1 1 1 1 1

	/*重新设置list1的大小，list1变短，原来超出的部分直接舍弃*/
	list1.resize(5);
	print_list3(list1); // 1 2 5 10 17

	return 0;
}

插入和删除

功能描述：

• 对list容器进行数据的插入和删除

函数原型：

• push_back(elem);//在容器尾部加入一个元素
• pop_back();//删除容器中最后一个元素
• push_front(elem);//在容器开头插入一个元素
• pop_front();//从容器开头移除第一个元素
• insert(pos,elem);//在pos位置插elem元素的拷贝，返回新数据的位置。
• insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
• insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。
• clear();//移除容器的所有数据
• erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
• erase(pos);//删除pos位置的数据，返回下一个数据的位置。
• remove(elem);//删除容器中所有与elem值匹配的元素。

#include<iostream>
#include<string>
#include<list>

using namespace std;

void print_list4(const list<int>& mylist) {
	for (list<int>::const_iterator ite = mylist.begin(); ite != mylist.end(); ite++) {
		cout << *ite << " ";
	}
	cout << endl;
}

int main() {
	list<int> mylist;
	/*在容器尾部插入元素*/
	mylist.push_back(1);
	mylist.push_back(2);
	/*在容器头部插入元素*/
	mylist.push_front(3);
	mylist.push_front(4);
	print_list4(mylist); // 4 3 1 2

	list<int>list2;
	list2.push_back(11);
	list2.push_back(22);
	list2.push_back(33);
	print_list4(list2); // 11 22 33

	/*在迭代器指向位置插入元素*/
	list<int>::iterator p = mylist.begin(); // 此时p指向4
	mylist.insert(p++, 888); // 在第一个元素位置插入888，迭代器后移一个位置
	print_list4(mylist); // 888 4 3 1 2，此时 p 指向 3
	mylist.insert(p++, 999); // 在第三个元素位置插入999，迭代器后移一个位置
	print_list4(mylist); // 888 4 999 3 1 2 ，此时p指向 1
	mylist.insert(p,2, 777); // 在第四个元素位置插入2个777
	print_list4(mylist); // 888 4 999 3 777 777 1 2

	/*此时p指向 元素1*/
	/*将list2的[begin(),end())区间内的元素存入mylist的第7个元素位置*/
	mylist.insert(p, list2.begin(), list2.end());
	print_list4(mylist); // 888 4 999 3 777 777 11 22 33 1 2

	/*删除list2 [begin(),end())区间内的元素*/
	list2.erase(list2.begin(), list2.end());
	cout << list2.size() << endl; // 0

	/*此时 p 指向 元素1*/
	/*删除mylist 中 p 指向的元素1*/
	list<int>::iterator p_next = mylist.erase(p); // 返回被删除元素的下一个元素的位置
	print_list4(mylist); // 888 4 999 3 777 777 11 22 33 2
	cout << "下一个元素是：" << *p_next << endl; // 2

	/*删除指定值*/
	mylist.remove(777); // 删除值为 777 的元素
	print_list4(mylist); // 888 4 999 3 11 22 33 2

	/*清空整个 mylist*/
	mylist.clear();
	cout << mylist.size() << endl; // 0

	return 0;
}

数据存取

功能描述：

• 对list容器中数据进行存取

函数原型：

• front(); //返回第一个元素。
• back(); //返回最后一个元素。

list的双向迭代器
双向迭代器，不支持随机访问，只能以递增或递减的方式逐步向前或者向后访问。

#include<iostream>
#include<string>
#include<list>

using namespace std;

void print_list5(const list<int>& mylist) {
	for (list<int>::const_iterator ite = mylist.begin(); ite != mylist.end(); ite++) {
		cout << *ite << " ";
	}
	cout << endl;
}

int main() {
	list<int> mylist;
	/*在容器尾部插入元素*/
	mylist.push_back(1);
	mylist.push_back(2);
	/*在容器头部插入元素*/
	mylist.push_front(3);
	mylist.push_front(4);
	print_list5(mylist); // 4 3 1 2

	/*获取第一个元素*/
	int first = mylist.front();
	int last = mylist.back();
	cout << first << endl; // 4
	cout << last << endl; // 2

	/*list的迭代器是双向迭代器，不允许跳跃访问，即使是 p = p + 1 的操作*/
	list<int>::iterator p = mylist.begin(); // 指向第一个位置
	// p = p + 1; // 错误
	// p = p - 1; // 错误
	// p = p + 2; // 错误
	p++; // 只能递增，后移一位
	cout << *p << endl; // 3
	p--; // 前移一位
	cout << *p << endl; // 4

	return 0;
}

反转和排序

功能描述：

• 将容器中的元素反转，以及将容器中的数据进行排序

函数原型：

• reverse(); //反转链表
• sort(); //链表排序

#include<iostream>
#include<string>
#include<list>

using namespace std;

void print_list6(const list<int>& mylist) {
	for (list<int>::const_iterator ite = mylist.begin(); ite != mylist.end(); ite++) {
		cout << *ite << " ";
	}
	cout << endl;
}

int main() {
	list<int> mylist;
	/*在容器尾部插入元素*/
	mylist.push_back(1);
	mylist.push_back(2);
	mylist.push_back(3);
	mylist.push_back(4);
	mylist.push_back(5);
	mylist.push_back(6);
	print_list6(mylist); // 1 2 3 4 5 6

	/*list反转*/
	mylist.reverse();
	print_list6(mylist); // 6 5 4 3 2 1

	/*清空list*/
	mylist.clear();

	/*随机种子*/
	srand((unsigned int)time(NULL));
	for (int i = 0; i < 10; i++) {
		// 生成 [99,21] 之间的一个随机整数
		int n = (rand() % (99 - 21 + 1)) + 21;
		mylist.push_back(n);
	}
	print_list6(mylist); // 51 26 47 57 29 28 41 94 53 37

	/*mylist 排序：*/
	mylist.sort();
	print_list6(mylist); // 26 28 29 37 41 47 51 53 57 94

	return 0;
}

排序案例

案例需求：

• 创建一个 Person 类，成员变量：姓名、身高、体重
• 将多个 Pseron 对象存入list容器
• 根据 Person 的身高（先）、体重（后）进行升序排序

#include<iostream>
#include<string>
#include<list>

using namespace std;

void print_list7(const list<int>& mylist) {
	for (list<int>::const_iterator ite = mylist.begin(); ite != mylist.end(); ite++) {
		cout << *ite << " ";
	}
	cout << endl;
}

class Person {
public:
	string name;
	int height;
	int weight;

	Person(string name,int weight,int height) {
		this->name = name;
		this->weight = weight;
		this->height = height;
	}
};
// 两个Person 对象比较大小,先按身高排序，后按体重排序，升序
bool person_conmare(Person& p1, Person& p2) {
	if (p1.height == p2.height) {
		return p1.weight <= p2.weight;
	}
	else {
		return p1.height <= p2.height;
	}
}

/*重写 左移操作符*/
ostream& operator<<(ostream& out, const Person& person) {
	out << "姓名：" << person.name << " 身高：" << person.height << " 体重：" << person.weight;
	return out;
}

// 重载 字符串与int使用加号运算
string operator+(string& content, int number) {
	string temp = "";
	char t = 0;
	while (true) {
		t = number % 10 + '0';
		temp = t + temp;
		number /= 10;
		if (number == 0) {
			return content + temp;
		}
	}
}
// 重载字符串与int使用 += 运算
// 由于+=会调用+号，所以 += 必须写在 + 号重载后面
string& operator+=(string& content, int number) {
	return content = content + number;
}


/*打印输出 list*/
void print_list7(list<Person>& mylist) {
	for (list<Person>::const_iterator p = mylist.begin(); p != mylist.end(); p++) {
		cout << *p << endl;
	}
}

int main() {
	/*随机种子*/
	srand((unsigned int)time(NULL));

	list<Person> ps;
	// 姓名
	
	for (int i = 0; i < 10; i++) {
		// 身高 cm 150到170之间
		int h = (rand() % (170 - 150 + 1)) + 150;
		// 体重 kg 50 到70之间
		int w = (rand() % (70 - 50 + 1)) + 50;
		string name = "Person-";
		name += i;
		Person p(name, w, h);
		ps.push_back(p);
	}
	print_list7(ps);
	cout << "***********" << endl;
	/*排序*/
	ps.sort(person_conmare);
	print_list7(ps);

}

姓名：Person-0 身高：165 体重：60
姓名：Person-1 身高：161 体重：56
姓名：Person-2 身高：159 体重：64
姓名：Person-3 身高：163 体重：55
姓名：Person-4 身高：157 体重：52
姓名：Person-5 身高：155 体重：64
姓名：Person-6 身高：165 体重：69
姓名：Person-7 身高：169 体重：65
姓名：Person-8 身高：168 体重：56
姓名：Person-9 身高：167 体重：50
***********
姓名：Person-5 身高：155 体重：64
姓名：Person-4 身高：157 体重：52
姓名：Person-2 身高：159 体重：64
姓名：Person-1 身高：161 体重：56
姓名：Person-3 身高：163 体重：55
姓名：Person-0 身高：165 体重：60
姓名：Person-6 身高：165 体重：69
姓名：Person-9 身高：167 体重：50
姓名：Person-8 身高：168 体重：56
姓名：Person-7 身高：169 体重：65