C++ list 容器

前言

本文包含list基本概念、list构造函数、list赋值和交换、list大小、list插入和删除、list数据存取、list反转和排序。

1. list 基本概念

（1）、功能： 将数据进行链式存储

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

（3）、链表的组成： 链表由一系列结点组成

（4）、结点的组成： 一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域

（5）、STL中的链表是一个双向循环链表

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

（7）、list的优点：

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

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

（8）、list的缺点： 链表灵活，但是空间（指针域） 和 时间（遍历）额外耗费较大

（9）、list有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的

list的迭代器，比如begin()，只要插入和删除，不在第一个元素上操作，它的begin()迭代器就不会发生改变（指向的内存地址不变）

vector的迭代器，比如begin()，如果插入和删除多个元素，会重新分配一块内存空间，它的begin()迭代器就会发生改变（指向的内存地址发生改变）

（10）、总结： STL中List和vector是两个最常被使用的容器，各有优缺点

2. list 构造函数

功能描述：

创建list容器

函数原型：

（1）、list<T> lst; list采用模板类实现对象的默认构造形式

（2）、list(beg,end); 构造函数将[beg, end)区间中的元素拷贝给本身

（3）、list(n,elem); 构造函数将n个elem拷贝给本身

（4）、list(const list &lst); 拷贝构造函数

// list链表容器构造函数#include <iostream>  // 包含标准输入输出流头文件
using namespace std;  // 使用标准命名空间#include <list>  // 使用list栈容器，需包含头文件listvoid test() {// 1、默认构造，无参构造list<int> L;// 2、将L开始迭代器到结束迭代器之间的元素，赋给L1list<int> L1(L.begin(), L.end());// 3、将10个100拷贝给L2list<int> L2(10, 100);// 4、拷贝构造list<int> L3(L);
}int main() {test();system("pause");  // 相当于在本地 Windows 调试器中的：请按任意键继续...；暂停，方便看清楚输出结果return 0;  // 程序正常退出
}

3. list 赋值和交换

功能描述：

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

函数原型：

（1）、assign(beg, end); 将[beg, end)区间中的数据拷贝赋值给本身

（2）、assign(n, elem); 将n个elem拷贝赋值给本身

（3）、list& operator=(const list &lst); 重载等号操作符

（4）、swap(lst); 将lst与本身的元素互换。

// list链表容器赋值和交换#include <iostream>  // 包含标准输入输出流头文件
using namespace std;  // 使用标准命名空间#include <list>  // 使用list栈容器，需包含头文件list// const对此容器只是只读，不可以修改
void Fun_Print(const list<int>& L) {   // 使用引用方式&，传入list<int>类型的形参L// const_iterator只读迭代器；iterator普通迭代器for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {//*it= 100;  // 报错，容器中数据不可修改：表达式必须是可修改的左值cout << *it << " ";  // it是个迭代器类型，本是是个指针，需使用*解引用}cout << endl;
}void test() {// 创建list容器对象，并且通过模板参数指定容器中存放的数据的类型list<int> L;// push_back()向容器中插入数据L.push_back(30);L.push_back(80);L.push_back(40);L.push_back(20);Fun_Print(L);  // 30 80 40 20list<int> L1;// 1、将L容器开始迭代器到结束迭代器之间的数据元素，拷贝给L1容器L1.assign(L.begin(), L.end());Fun_Print(L1);  // 30 80 40 20list<int> L2;// 2、将10个10拷贝给L2容器L2.assign(10, 10);Fun_Print(L2);  // 10 10 10 10 10 10 10 10 10 10list<int> L3;// 3、重载operator=L3 = L1;Fun_Print(L3);  // 30 80 40 20cout << "L3和L2互换前 -------------------------------" << endl;Fun_Print(L2);  // 10 10 10 10 10 10 10 10 10 10Fun_Print(L3);  // 30 80 40 20cout << "L3和L2互换后 -------------------------------" << endl;// 4、将L2容器中的数据元素与自身L3进行元素互换L3.swap(L2);Fun_Print(L2);  // 30 80 40 20Fun_Print(L3);  // 10 10 10 10 10 10 10 10 10 10
}int main() {test();system("pause");  // 相当于在本地 Windows 调试器中的：请按任意键继续...；暂停，方便看清楚输出结果return 0;  // 程序正常退出
}

4. list 大小操作

功能描述：

对list容器的大小进行操作

函数原型：

（1）、empty(); 判断容器是否为空

（2）、size(); 返回容器中元素的个数

（3）、resize(num);

3.1）、重新指定容器的长度为num，若容器变长，则以默认值填充新位置。 （默认填充0）

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

（4）、resize(num, elem);

4.1）、重新指定容器的长度为num，若容器变长，则以elem值填充新位置。 （指定填充elem）

4.2）、如果容器变短，则末尾超出容器长度的元素被删除

// list链表容器大小#include <iostream>  // 包含标准输入输出流头文件
using namespace std;  // 使用标准命名空间#include <list>  // 使用list栈容器，需包含头文件list// const对此容器只是只读，不可以修改
void Fun_Print(const list<int>& L) {   // 使用引用方式&，传入list<int>类型的形参L// const_iterator只读迭代器；iterator普通迭代器for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {//*it= 100;  // 报错，容器中数据不可修改：表达式必须是可修改的左值cout << *it << " ";  // it是个迭代器类型，本是是个指针，需使用*解引用}cout << endl;
}void test() {// 创建list容器对象，并且通过模板参数指定容器中存放的数据的类型list<int> L;// push_back()向容器中插入数据L.push_back(30);L.push_back(80);L.push_back(40);L.push_back(20);Fun_Print(L);  // 30 80 40 20// 1、empty()判断容器是否为空，返回真，则为空if (L.empty()) {cout << "L链表容器为空" << endl;}else {cout << "L链表容器不为空" << endl;// 2、size()返回容器数据元素个数cout << "L链表容器数据元素个数为：" << L.size() << endl;}// 3.1、resize()指定容器长度为10，默认填充0L.resize(10);Fun_Print(L);  // 30 80 40 20 0 0 0 0 0 0// 3.2、resize()指定容器长度为5，删除超出容器长度的数据元素L.resize(5);Fun_Print(L);  // 30 80 40 20 0// 4.1、resize()指定容器长度为10，默认填充10L.resize(10, 10);Fun_Print(L);  // 30 80 40 20 0 10 10 10 10 10// 4.2、resize()指定容器长度为5，删除超出容器长度的数据元素L.resize(5, 5);Fun_Print(L);  // 30 80 40 20 0
}int main() {test();system("pause");  // 相当于在本地 Windows 调试器中的：请按任意键继续...；暂停，方便看清楚输出结果return 0;  // 程序正常退出
}

5. list 插入和删除

功能描述：

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

函数原型：

（1）、push_back(elem); 在容器尾部加入一个元素

（2）、pop_back(); 删除容器中最后一个元素

（3）、push_front(elem); 在容器开头插入一个元素

（4）、pop_front(); 从容器开头移除第一个元素

（5）、insert(pos,elem); 在pos位置插elem元素的拷贝，返回新数据的位置 （pos迭代器）

（6）、insert(pos,n,elem); 在pos位置插入n个elem数据，无返回值

（7）、insert(pos,beg,end); 在pos位置插入[beg,end)区间的数据，无返回值 （pos,beg,end迭代器）

（8）、remove(elem); 删除容器中所有与elem值匹配的元素

（9）、erase(pos); 删除pos位置的数据，返回下一个数据的位置

（10）、erase(beg,end); 删除[beg,end)区间的数据，返回下一个数据的位置

（11）、clear(); 移除容器的所有数据

// list链表容器插入和删除#include <iostream>  // 包含标准输入输出流头文件
using namespace std;  // 使用标准命名空间#include <list>  // 使用list栈容器，需包含头文件list// const对此容器只是只读，不可以修改
void Fun_Print(const list<int>& L) {   // 使用引用方式&，传入list<int>类型的形参L// const_iterator只读迭代器；iterator普通迭代器for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {//*it= 100;  // 报错，容器中数据不可修改：表达式必须是可修改的左值cout << *it << " ";  // it是个迭代器类型，本是是个指针，需使用*解引用}cout << endl;
}void test() {// 创建list容器对象，并且通过模板参数指定容器中存放的数据的类型list<int> L;// 1、push_back()向容器尾部插入数据元素L.push_back(30);L.push_back(80);Fun_Print(L);  // 30 80// 2、pop_back()删除容器最后一个数据元素L.pop_back();Fun_Print(L);  // 30// 3、push_front()像容器头部插入数据元素L.push_front(90);L.push_front(60);Fun_Print(L);  // 60 90 30// 4、push_front()删除容器开头的第一个数据元素L.pop_front();Fun_Print(L);  // 90 30// 5、insert()在L开始迭代器的下一个位置后，插入10list<int>::iterator it = L.begin();  // list<int>::iterator迭代器L.insert(++it,10);  // ++it，先加1Fun_Print(L);  // 90 10 30// 6、insert()在L开始迭代器的下一个位置后，插入5个0L.insert(it, 5, 0);Fun_Print(L);  // 90 10 0 0 0 0 0 30// 7、insert()在L开始迭代器，插入L容器开始迭代器与结束迭代器区间的数据元素L.insert(L.begin(), L.begin(), L.end());Fun_Print(L);  // 90 10 0 0 0 0 0 30 90 10 0 0 0 0 0 30// 8、remove()删除L容器中数据元素为0的元素L.remove(0);Fun_Print(L);  // 90 10 30 90 10 30// 9、erase()删除L容器开始迭代器中的数据元素L.erase(L.begin());Fun_Print(L);  // 10 30 90 10 30// 10、erase()删除L容器开始迭代器到结束迭代器中的数据元素L.erase(L.begin(), L.end());Fun_Print(L);  //// 11、clear()清空L容器所有数据元素L.clear();Fun_Print(L);  //
}int main() {test();system("pause");  // 相当于在本地 Windows 调试器中的：请按任意键继续...；暂停，方便看清楚输出结果return 0;  // 程序正常退出
}

6. list 数据存取

功能描述：

对list容器中数据进行存取

函数原型：

（1）、front(); 返回第一个元素

（2）、back(); 返回最后一个元素

不支持[]和at：list是链表，链表不是连续的空间，所以不能直接利用[]和at方式访问里面的数据元素，而且list不支持随机访问，跳跃式访问

// list链表容器数据存取#include <iostream>  // 包含标准输入输出流头文件
using namespace std;  // 使用标准命名空间#include <list>  // 使用list栈容器，需包含头文件list// const对此容器只是只读，不可以修改
void Fun_Print(const list<int>& L) {   // 使用引用方式&，传入list<int>类型的形参L// const_iterator只读迭代器；iterator普通迭代器for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {//*it= 100;  // 报错，容器中数据不可修改：表达式必须是可修改的左值cout << *it << " ";  // it是个迭代器类型，本是是个指针，需使用*解引用}cout << endl;
}void test() {// 创建list容器对象，并且通过模板参数指定容器中存放的数据的类型list<int> L;// push_back()向容器尾部插入数据元素L.push_back(30);L.push_back(80);L.push_back(10);L.push_back(40);Fun_Print(L);  // 30 80 10 40// 原因：list本质是链表，不是用连续线性空间存储数据，迭代器也是不支持随机访问的//cout << L1.at(0) << endl;  // 错误 不支持at访问list容器中的数据元素；没有成员"at"//cout << L1[0] << endl;  //错误  不支持[]方式访问list容器中的数据元素；没有与这些操作符匹配的"[]"运算符// 1、front()返回容器的第一个数据元素cout << "L容器第一个元素为： " << L.front() << endl;  // 30// 2、back()返回容器的最后一个数据元素cout << "L容器最后一个元素为： " << L.back() << endl;  // 40// list容器的迭代器是双向迭代器，不支持随机访问list<int>::iterator it = L.begin();it++;  // 正确，*it++ = 80（第二个数据元素），解引用后是80；支持双向++、--//it = it + 1;  // 错误，不可以跳跃访问，即使是+1（+2、+3...跳着加减）（只能使用++、--）；没有与这些操作符匹配的"+"运算符// 判断迭代器是否支持随机访问：写一个迭代器list<int>::iterator it，如果支持+/— 1、2、3...，迭代器支持随机访问，否则反之// 判断迭代器是否支持双向：写一个迭代器list<int>::iterator it，如果支持++、--，没报错，说明支持双向；如果只支持++，使用--报错，则只支持向前
}int main() {test();system("pause");  // 相当于在本地 Windows 调试器中的：请按任意键继续...；暂停，方便看清楚输出结果return 0;  // 程序正常退出
}

7. list 反转和排序

功能描述：

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

函数原型：

（1）、reverse(); 反转链表

（2）、sort(); 链表排序

// list链表容器反转和排序#include <iostream>  // 包含标准输入输出流头文件
using namespace std;  // 使用标准命名空间#include <list>  // 使用list栈容器，需包含头文件list//#include <algorithm>// const对此容器只是只读，不可以修改
void Fun_Print(const list<int>& L) {   // 使用引用方式&，传入list<int>类型的形参L// const_iterator只读迭代器；iterator普通迭代器for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {//*it= 100;  // 报错，容器中数据不可修改：表达式必须是可修改的左值cout << *it << " ";  // it是个迭代器类型，本是是个指针，需使用*解引用}cout << endl;
}bool Fun_Sort(int num1, int num2) {// 降序，就让第一个数 > 第二个数return num1 > num2;
}void test() {// 创建list容器对象，并且通过模板参数指定容器中存放的数据的类型list<int> L;// push_back()向容器尾部插入数据元素L.push_back(30);L.push_back(80);L.push_back(10);L.push_back(40);Fun_Print(L);  // 30 80 10 40// 1、reverse()反转容器的元素L.reverse();Fun_Print(L);  // 40 10 80 30// 所有不支持随机访问迭代器的容器，不可以用标准算法// 不支持随机访问迭代器的容器，内部会提供对应一些算法；使用内部的sort()//sort(L.begin(), L.end());  // 这个sort()函数是全局函数，需引用algorithm头文件// 2、sort()默认的排序规则 从小到大，升序；这个sort()函数是成员函数L.sort();Fun_Print(L);  // 10 30 40 80// 指定规则，从大到小；参数为一个函数或者一个仿函数L.sort(Fun_Sort);  // Fun_Sort函数Fun_Print(L);  // 10 30 40 80
}int main() {test();system("pause");  // 相当于在本地 Windows 调试器中的：请按任意键继续...；暂停，方便看清楚输出结果return 0;  // 程序正常退出
}

8. 排序案例：自定义类型排序

案例描述：

将Person自定义数据类型进行排序，Person中属性有姓名、年龄、身高

排序规则：

按照年龄进行升序，如果年龄相同按照身高进行降序

// list链表容器反转和排序#include <iostream>  // 包含标准输入输出流头文件
using namespace std;  // 使用标准命名空间#include <list>  // 使用list栈容器，需包含头文件list//#include <algorithm>// const对此容器只是只读，不可以修改
void Fun_Print(const list<int>& L) {   // 使用引用方式&，传入list<int>类型的形参L// const_iterator只读迭代器；iterator普通迭代器for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {//*it= 100;  // 报错，容器中数据不可修改：表达式必须是可修改的左值cout << *it << " ";  // it是个迭代器类型，本是是个指针，需使用*解引用}cout << endl;
}// 定义一个Person类
class Person {public:Person(string name, int age, int height) {  // 构造函数，赋初值m_Name = name;m_Age = age;m_Height = height;}public:string m_Name;  // 姓名int m_Age;      // 年龄int m_Height;   // 身高
};// 指定排序规则
bool ComparePerson(Person& p1, Person& p2) {// 按照年龄，升序if (p1.m_Age == p2.m_Age) {// 年龄相同，按照身高降序return p1.m_Height > p2.m_Height;}else{// 年龄不同，升序return  p1.m_Age < p2.m_Age;}
}void test() {// 创建list容器对象，并且通过模板参数指定容器中存放的数据的类型list<Person> L;// 准备数据Person p1("刘备", 35, 175);Person p2("曹操", 45, 180);Person p3("孙权", 40, 170);Person p4("赵云", 25, 190);Person p5("张飞", 35, 160);Person p6("关羽", 35, 200);// push_back()向容器尾部插入数据元素L.push_back(p1);L.push_back(p2);L.push_back(p3);L.push_back(p4);L.push_back(p5);L.push_back(p6);// 遍历L容器，打印数据for (list<Person>::iterator it = L.begin(); it != L.end(); it++) {cout << "姓名： " << it->m_Name << " 年龄： " << it->m_Age << " 身高： " << it->m_Height << endl;}cout << "---------------------------------" << endl;// 自定义排序规则L.sort(ComparePerson);  // 排序for (list<Person>::iterator it = L.begin(); it != L.end(); it++) {cout << "姓名： " << it->m_Name << " 年龄： " << it->m_Age << " 身高： " << it->m_Height << endl;}
}int main() {test();system("pause");  // 相当于在本地 Windows 调试器中的：请按任意键继续...；暂停，方便看清楚输出结果return 0;  // 程序正常退出
}

总结

（1）、list 判断是否为空 — empty；

（2）、list 返回元素个数 — size；

（3）、list 重新指定个数 — resize；

（4）、list 尾插 — push_back；

（5）、list 尾删 — pop_back；

（6）、list 头插 — push_front；

（7）、list 头删 — pop_front；

（8）、list 插入 — insert；

（9）、list 删除 — erase；

（10）、list 移除 — remove；

（11）、list 清空 — clear；

（12）、list 容器中不可以通过[]或者at方式访问数据 （不支持随机访问）；

（13）、list 返回第一个元素 — front；

（14）、list 返回最后一个元素 — back；

（15）、list 反转 — reverse；

（16）、list 排序 — sort （成员函数）；

（17）、对于自定义数据类型，必须要指定排序规则，否则编译器不知道如何进行排序；

（18）、高级排序只是在排序规则上再进行一次逻辑规则制定，并不复杂。