目录
list 基本概念
功能：将数据进行链式存储
-
链表（list）：是一种物理存储单位上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的
-
链表的组成：链表有一系列结点组成
-
结点的组成：两个部分，一部分是存储数据元素的数据域，另一部分是存储下一个地址的指针域
-
链表的优点：可以对任意位置进行快速插入和删除的操作
-
链表的缺点：遍历速度慢（比数组），占用空间大（比数组）
-
STL中的链表是一个双向循环链表
由于链表的存储方式并不是连续的内存空间，因此链表 list 中的迭代器只支持前移和后移，属于双向迭代器
-
list 优点：
- 采用动态存储分配，不会造成内存浪费和溢出（vector 容器的容量在创建空间很大时会不等于容器大小，这就是一定的空间浪费）
- 链表执行插入和删除效率高
-
list 缺点：
- 链表灵活，但是空间（指针域）和时间（遍历）额外消耗大
-
list 有一个重要的性质，插入操作和删除操作都不会造成原有 list 迭代器的失效，这在 vector 是不成立的（重新分配新空间，将旧数据放到新空间，迭代器也就失效了）
-
在 STL 中 list 和 vector 是很常用的容器
list 构造函数
功能：
- 创建 list 容器
函数原型：
// list采用模板类实现 list<T> lst; // 构造函数将 [beg, end) 区间中的元素拷贝给本身 list(beg, end); // 构造函数将 n 个 elem 拷贝给本身 list(n, elem); 拷贝构造函数 list(const list& lst);
测试代码：
#include<iostream>
using namespace std;
#include<list>
void PrintList(const list<int>& L) {
for (list<int>::const_iterator Lit = L.begin(); Lit != L.end(); ++Lit) {
cout << *Lit << " ";
}
cout << endl;
}
void test() {
// 创建 list 容器
list<int>L1;
// 添加数据
L1.push_back(10);
L1.push_back(20);
L1.push_back(30);
L1.push_back(40);
PrintList(L1); // 10 20 30 40
// 区间的方式构造
list<int>L2(L1.begin(), L1.end()); // 双向迭代器只能 ++、--
PrintList(L2); // 10 20 30 40
// n 个 elem
list<int>L3(5, 10);
PrintList(L3); // 10 10 10 10 10
}
int main() {
test();
system("pause");
return 0;
}运行结果：
list 赋值和交换
功能：
- 给 list 容器进行赋值，以及交换 list 容器
函数原型：
// 将 [beg, end) 区间中的数据拷贝赋值给本身 assign(beg, end); // 将 n 个 elem 拷贝赋值给本身 assign(n, elem); // 重载 = 操作符 list& operator=(const list& lst); // 将 lst 与本身的元素互换 swap(lst);
测试代码：
#include<iostream>
using namespace std;
#include<list>
void PrintList(const list<int>& L) {
for (list<int>::const_iterator Lit = L.begin(); Lit != L.end(); ++Lit) {
cout << *Lit << " ";
}
cout << endl;
}
void test() {
list<int>L1;
L1.push_back(10);
L1.push_back(20);
L1.push_back(30);
L1.push_back(40);
list<int>L2;
// 将 [beg, end) 区间中的数据拷贝赋值给本身
L2.assign(++L1.begin(), --L1.end()); // 双向迭代器，前置++--才有用
PrintList(L2); // 20 30
list<int>L3;
// 重载 = 操作
L3 = L1;
PrintList(L3); // 10 20 30 40
list<int>L4;
// n 个 elem 赋值
L4.assign(4, 10);
PrintList(L4); // 10 10 10 10
// swap 交换
L4.swap(L3);
PrintList(L3); // 10 10 10 10
PrintList(L4); // 10 20 30 40
}
int main() {
test();
system("pause");
return 0;
}运行结果：
list 大小操作
功能：
- 对 list 容器的大小进行操作
函数原型：
// 返回容器中元素的个数 size(); // 判断容器是否为空 empty(); // 重新指定容器的长度为 num，若容器变长，则以默认值填充新位置 // 如果容器变短，则末尾超出容器长度的元素被删除 resize(num); // 重新指定容器的长度为 num，若容器变长，则以 elem 填充新位置 // 如果容器变短，则末尾超出容器长度的元素被删除 resize(num, elem);
测试代码：
#include<iostream>
using namespace std;
#include<list>
void PrintList(const list<int>& L) {
for (list<int>::const_iterator Lit = L.begin(); Lit != L.end(); ++Lit) {
cout << *Lit << " ";
}
cout << endl;
}
void test() {
list<int>L1;
// 判断是否为空，为空返回 true
if (L1.empty()) {
cout << "L1 为空" << endl;
}
else {
cout << "L1 非空" << endl;
}
L1.push_back(10);
L1.push_back(20);
L1.push_back(30);
L1.push_back(40);
// 判断是否为空
if (L1.empty()) {
cout << "L1 为空" << endl;
}
else {
cout << "L1 非空" << endl;
cout << "L1 长度：" << L1.size() << endl;
PrintList(L1); // 10 20 30 40
// resize(num)，超出的用 0 填充
L1.resize(5); // 大小从 4 变成 5
PrintList(L1); // 10 20 30 40 0
// resize(num, elem)，超出的用 elem 填充
L1.resize(6, 10); // 大小从 5 变成 6
PrintList(L1); // 10 20 30 40 0 10
// resize(num)，末尾多的删除
L1.resize(4); // 大小从 6 变成 4
PrintList(L1); // 10 20 30 40
}
}
int main() {
test();
system("pause");
return 0;
}运行结果：
list 插入和删除
功能：
- 对 list 容器进行数据的插入和删除
函数原型：
// 容器末尾添加一个元素 push_back(elem); // 从容器末尾移除一个元素 pop_back(); // 从容器开头添加一个元素 push_front(elem); // 从容器开头移除一个元素 pop_front(); // 在 pos（迭代器） 位置插 elem 元素的拷贝，返回新数据的位置 insert(pos, elem); // 在 pos（迭代器） 位置插入 n 个 elem 数据，无返回值 insert(pos, n, elem); // 在 pos（迭代器） 位置插入 [beg, end) （迭代器）区间数据，无返回值 insert(pos, beg, end); // 移除容器所有数据 clear(); // 删除 [beg, end) （迭代器）区间的数据，返回下一个数据的位置 erase(beg, end); // 删除 pos （迭代器）位置的数据，返回下一个数据的位置 erase(pos); // 删除容器中所有与 elem 值匹配的元素 remove(elem);
测试代码：
#include<iostream>
using namespace std;
#include<list>
void PrintList(const list<int>& L) {
for (list<int>::const_iterator Lit = L.begin(); Lit != L.end(); ++Lit) {
cout << *Lit << " ";
}
cout << endl;
}
void test() {
list<int>L1;
// push_back(elem); 从尾部添加
L1.push_back(10);
L1.push_back(20);
// push_front(elem); 从头部添加
L1.push_front(-10);
L1.push_front(-20);
PrintList(L1); // -20 -10 10 20
// pop_back(); 从尾部删除一个
L1.pop_back();
PrintList(L1); // -20 -10 10
// pop_front(); 从头部删除一个
L1.pop_front();
PrintList(L1); // -10 10
// insert(pos, elem); 在 pos 位置插入 elem 的拷贝，返回新数据位置
L1.insert(L1.begin(), -20); // 开始位置插入 -20
PrintList(L1); // -20 -10 10
// insert(pos, n, elem); 在 pos 位置插入 n 个 elem 数据，无返回值
L1.insert(L1.end(), 1, 20); // 最后一个位置插入 1 个 20
PrintList(L1); // -20 -10 10 20
list<int>L2;
for (int i = 0; i < 5; i++) {
L2.push_back(i + 1);
}
// insert(pos, beg, end); 在 pos 位置插入 [beg, end) 数据，无返回值
L1.insert(L1.begin(), L2.begin(), L2.end());
PrintList(L1); // 1 2 3 4 5 -20 -10 10 20
// erase(beg, end); 删除 [beg, end) 区间数据，返回下一个数据的位置
L1.erase(++L1.begin(), --L1.end()); // 双向迭代器，只能 ++-- ，前置才有效
PrintList(L1); // 1 20
// erase(pos); 删除 pos 位置数据，返回下一个数据的位置
L1.erase(L1.begin());
PrintList(L1); // 20
L1.push_back(30);
// clear(); 清空 list 容器数据
L1.clear();
if (!L1.size()) {
cout << "L1 为空" << endl;
}
else {
cout << "L1 非空" << endl;
}
PrintList(L1); // 空
list<int>L3;
L3.push_back(10);
L3.push_back(20);
L3.push_back(10);
L3.push_back(20);
L3.push_back(10);
L3.push_back(20);
// remove(num); 移除 list 容器中与 num 匹配的数据
L3.remove(10);
PrintList(L3); // 20 20 20
}
int main() {
test();
system("pause");
return 0;
}运行结果：
list 数据存取
功能：
- 对 list 容器中数据进行存取
函数原型：
// 返回第一个元素 front(); // 返回最后一个元素 back();不可以使用 [ ] 方式访问 list 容器
不可以使用 at 方式访问 list 容器
原因：本质是链表，每个数据不是用连续的线性空间存储的，迭代器也不支持随机访问
测试代码：
#include<iostream>
using namespace std;
#include<list>
void PrintList(const list<int>& L) {
for (list<int>::const_iterator Lit = L.begin(); Lit != L.end(); ++Lit) {
cout << *Lit << " ";
}
cout << endl;
}
void test() {
list<int>L1;
L1.push_back(10);
L1.push_back(20);
L1.push_back(30);
L1.push_back(40);
cout << "第一个元素： " << L1.front() << endl;
cout << "最后一个元素：" << L1.back() << endl;
// 迭代器不支持随机访问
list<int>::iterator it = L1.begin();
//it = it + 1; // × 没有与操作符 + 匹配的运算符
//it = it++; // √
//it = it++; // 只能这样一步一步加
//it = it--; // √，支持双向
}
int main() {
test();
system("pause");
return 0;
}运行结果：
list 反转和排序
功能：
- 将容器中的元素反转，以及将容器中的数据进行排序
函数原型：
// 反转链表 reverse(); // 链表排序 sort();
测试代码：
#include<iostream>
using namespace std;
#include<list>
void PrintList(const list<int>& L) {
for (list<int>::const_iterator Lit = L.begin(); Lit != L.end(); ++Lit) {
cout << *Lit << " ";
}
cout << endl;
}
bool myCompare(int a, int b) {
return (a > b);
}
void test() {
list<int>L1;
L1.push_back(9);
L1.push_back(5);
L1.push_back(8);
L1.push_back(6);
L1.push_back(7);
cout << "反转前：";
PrintList(L1); // 9 5 8 6 7
cout << "反转后：";
L1.reverse();
PrintList(L1); // 7 6 8 5 9
cout << "排序前：";
PrintList(L1); // 7 6 8 5 9
cout << "排序后：";
L1.sort(); // 从小到大，想要降序再 reverse 一下
PrintList(L1); // 5 6 7 8 9
// sort() 还有一个重载的版本，可以降序
cout << "降序： ";
L1.sort(myCompare);
PrintList(L1); // 9 8 7 6 5
// 所有不支持随机访问迭代器的容器，不可以使用标准算法
// sort(L1.begin(), L1.end()); // 错误
}
int main() {
test();
system("pause");
return 0;
}运行结果：
list 排序案例
案例：将 Person 自定义数据类型进行排序，Person 中属性有 name、age、high
-
排序规则：按 age 进行升序，如果 age 相等就按 high 进行降序
代码实例：
#include<iostream>
using namespace std;
#include<list>
#include<string>
class Person {
friend void PrintList(list<Person>& P_List);
friend bool comparePerson(Person& p1, Person& p2);
public:
Person(string name, int age, int high) :m_Name(name), m_Age(age), m_High(high) { }
private:
string m_Name;
int m_Age;
int m_High;
};
void PrintList(list<Person>& P_List) {
for (list<Person>::iterator it = P_List.begin(); it != P_List.end(); ++it) {
cout << "姓名:" << (*it).m_Name << " 年龄:" << it->m_Age << " 身高:" << (*it).m_High << endl;
}
}
// 指定排序规则
bool comparePerson(Person& p1, Person& p2) {
if (p1.m_Age == p2.m_Age) {
return p1.m_High > p2.m_High;
}
else {
return p1.m_Age < p2.m_Age;
}
}
void test() {
list<Person>Person_List;
Person p1("李华", 18, 180);
Person p2("张三", 19, 170);
Person p3("王五", 20, 175);
Person p4("赵六", 20, 170);
Person p5("李四", 20, 180);
Person_List.push_back(p1);
Person_List.push_back(p2);
Person_List.push_back(p3);
Person_List.push_back(p4);
Person_List.push_back(p5);
cout << "排序前：" << endl;
PrintList(Person_List);
cout << "----------------------" << endl;
cout << "排序后：" << endl;
Person_List.sort(comparePerson);
PrintList(Person_List);
}
int main() {
test();
system("pause");
return 0;
}运行结果：
