• 【C++】list容器

    目录

    list 基本概念

    list 构造函数

    list 赋值和交换

    list 大小操作

    list 插入和删除

    list 数据存取

    list 反转和排序

    list 排序案例

    list 基本概念

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

    -

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

    -

    链表的组成：链表有一系列结点组成

    -

    结点的组成：两个部分，一部分是存储数据元素的数据域，另一部分是存储下一个地址的指针域

    -

    链表的优点：可以对任意位置进行快速插入和删除的操作

    -

    链表的缺点：遍历速度慢（比数组），占用空间大（比数组）

    -

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

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

    -

    list 优点：

    • 采用动态存储分配，不会造成内存浪费和溢出（vector 容器的容量在创建空间很大时会不等于容器大小，这就是一定的空间浪费）
    • 链表执行插入和删除效率高

    -

    list 缺点：

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

    -

    list 有一个重要的性质，插入操作和删除操作都不会造成原有 list 迭代器的失效，这在 vector 是不成立的（重新分配新空间，将旧数据放到新空间，迭代器也就失效了）

    -

    在 STL 中 list 和 vector 是很常用的容器

    list 构造函数

    功能：

    • 创建 list 容器

    函数原型：

    1. // list采用模板类实现
    2. list lst;
    3.  
    4. // 构造函数将 [beg, end) 区间中的元素拷贝给本身
    5. list(beg, end);
    6.  
    7. // 构造函数将 n 个 elem 拷贝给本身
    8. list(n, elem);
    9.  
    10. 拷贝构造函数
    11. list(const list& lst);

    测试代码：

    1. #include
    2. using namespace std;
    3. #include
    4.  
    5. void PrintList(const list<int>& L) {
    6.     for (list<int>::const_iterator Lit = L.begin(); Lit != L.end(); ++Lit) {
    7.         cout << *Lit << " ";
    8.     }
    9.     cout << endl;
    10. }
    11.  
    12. void test() {
    13.     // 创建 list 容器
    14.     list<int>L1;
    15.  
    16.     // 添加数据
    17.     L1.push_back(10);
    18.     L1.push_back(20);
    19.     L1.push_back(30);
    20.     L1.push_back(40);
    21.     
    22.     PrintList(L1); // 10 20 30 40
    23.  
    24.     // 区间的方式构造
    25.     list<int>L2(L1.begin(), L1.end()); // 双向迭代器只能 ++、--
    26.     PrintList(L2); // 10 20 30 40
    27.  
    28.     // n 个 elem
    29.     list<int>L3(5, 10);
    30.     PrintList(L3); // 10 10 10 10 10
    31.  
    32. }
    33.  
    34. int main() {
    35.     test();
    36.     system("pause");
    37.     return 0;
    38. }

    运行结果：

    list 赋值和交换

    功能：

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

    函数原型：

    1. // 将 [beg, end) 区间中的数据拷贝赋值给本身
    2. assign(beg, end);
    3.  
    4. // 将 n 个 elem 拷贝赋值给本身
    5. assign(n, elem);
    6.  
    7. // 重载 = 操作符
    8. list& operator=(const list& lst);
    9.  
    10. // 将 lst 与本身的元素互换
    11. swap(lst);

    测试代码：

    1. #include
    2. using namespace std;
    3. #include
    4.  
    5. void PrintList(const list<int>& L) {
    6.     for (list<int>::const_iterator Lit = L.begin(); Lit != L.end(); ++Lit) {
    7.         cout << *Lit << " ";
    8.     }
    9.     cout << endl;
    10. }
    11.  
    12. void test() {
    13.     list<int>L1;   
    14.     L1.push_back(10);
    15.     L1.push_back(20);
    16.     L1.push_back(30);
    17.     L1.push_back(40);
    18.  
    19.     list<int>L2;
    20.     // 将 [beg, end) 区间中的数据拷贝赋值给本身
    21.     L2.assign(++L1.begin(), --L1.end()); // 双向迭代器，前置++--才有用
    22.     PrintList(L2); // 20 30
    23.  
    24.     list<int>L3;
    25.     // 重载 = 操作
    26.     L3 = L1;
    27.     PrintList(L3); // 10 20 30 40
    28.  
    29.     list<int>L4;
    30.     // n 个 elem 赋值
    31.     L4.assign(4, 10);
    32.     PrintList(L4); // 10 10 10 10
    33.  
    34.     // swap 交换
    35.     L4.swap(L3);
    36.     PrintList(L3); // 10 10 10 10
    37.     PrintList(L4); // 10 20 30 40
    38. }
    39.  
    40. int main() {
    41.     test();
    42.     system("pause");
    43.     return 0;
    44. }

    运行结果：

    list 大小操作

    功能：

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

    函数原型：

    1. // 返回容器中元素的个数
    2. size();
    3.  
    4. // 判断容器是否为空
    5. empty();
    6.  
    7. // 重新指定容器的长度为 num，若容器变长，则以默认值填充新位置
    8. // 如果容器变短，则末尾超出容器长度的元素被删除
    9. resize(num);
    10.  
    11. // 重新指定容器的长度为 num，若容器变长，则以 elem 填充新位置
    12. // 如果容器变短，则末尾超出容器长度的元素被删除
    13. resize(num, elem);

    测试代码：

    1. #include
    2. using namespace std;
    3. #include
    4.  
    5. void PrintList(const list<int>& L) {
    6.     for (list<int>::const_iterator Lit = L.begin(); Lit != L.end(); ++Lit) {
    7.         cout << *Lit << " ";
    8.     }
    9.     cout << endl;
    10. }
    11.  
    12. void test() {
    13.     list<int>L1;   
    14.  
    15.     // 判断是否为空，为空返回 true
    16.     if (L1.empty()) {
    17.         cout << "L1 为空" << endl;
    18.     }
    19.     else {
    20.         cout << "L1 非空" << endl;
    21.     }
    22.  
    23.     L1.push_back(10);
    24.     L1.push_back(20);
    25.     L1.push_back(30);
    26.     L1.push_back(40);
    27.  
    28.     // 判断是否为空
    29.     if (L1.empty()) {
    30.         cout << "L1 为空" << endl;
    31.     }
    32.     else {
    33.         cout << "L1 非空" << endl;
    34.         cout << "L1 长度：" << L1.size() << endl;
    35.         PrintList(L1); // 10 20 30 40
    36.  
    37.         // resize(num)，超出的用 0 填充
    38.         L1.resize(5);  // 大小从 4 变成 5
    39.         PrintList(L1); // 10 20 30 40 0
    40.  
    41.         // resize(num, elem)，超出的用 elem 填充
    42.         L1.resize(6, 10); // 大小从 5 变成 6
    43.         PrintList(L1);    // 10 20 30 40 0 10
    44.  
    45.         // resize(num)，末尾多的删除
    46.         L1.resize(4);  // 大小从 6 变成 4
    47.         PrintList(L1); // 10 20 30 40
    48.     }
    49. }
    50.  
    51. int main() {
    52.     test();
    53.     system("pause");
    54.     return 0;
    55. }

    运行结果：

    list 插入和删除

    功能：

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

    函数原型：

    1. // 容器末尾添加一个元素
    2. push_back(elem);
    3.  
    4. // 从容器末尾移除一个元素
    5. pop_back();
    6.  
    7. // 从容器开头添加一个元素
    8. push_front(elem);
    9.  
    10. // 从容器开头移除一个元素
    11. pop_front();
    12.  
    13. // 在 pos（迭代器） 位置插 elem 元素的拷贝，返回新数据的位置
    14. insert(pos, elem);
    15.  
    16. // 在 pos（迭代器） 位置插入 n 个 elem 数据，无返回值
    17. insert(pos, n, elem);
    18.  
    19. // 在 pos（迭代器） 位置插入 [beg, end) （迭代器）区间数据，无返回值
    20. insert(pos, beg, end);
    21.  
    22. // 移除容器所有数据
    23. clear();
    24.  
    25. // 删除 [beg, end) （迭代器）区间的数据，返回下一个数据的位置
    26. erase(beg, end);
    27.  
    28. // 删除 pos （迭代器）位置的数据，返回下一个数据的位置
    29. erase(pos);
    30.  
    31. // 删除容器中所有与 elem 值匹配的元素
    32. remove(elem);

    测试代码：

    1. #include
    2. using namespace std;
    3. #include
    4.  
    5. void PrintList(const list<int>& L) {
    6.     for (list<int>::const_iterator Lit = L.begin(); Lit != L.end(); ++Lit) {
    7.         cout << *Lit << " ";
    8.     }
    9.     cout << endl;
    10. }
    11.  
    12. void test() {
    13.     list<int>L1;   
    14.  
    15.     // push_back(elem); 从尾部添加
    16.     L1.push_back(10);
    17.     L1.push_back(20);
    18.  
    19.     // push_front(elem); 从头部添加
    20.     L1.push_front(-10);
    21.     L1.push_front(-20);
    22.  
    23.     PrintList(L1); // -20 -10 10 20
    24.  
    25.     // pop_back(); 从尾部删除一个
    26.     L1.pop_back();
    27.     PrintList(L1); // -20 -10 10
    28.  
    29.     // pop_front(); 从头部删除一个
    30.     L1.pop_front();
    31.     PrintList(L1); // -10 10
    32.  
    33.     // insert(pos, elem); 在 pos 位置插入 elem 的拷贝，返回新数据位置
    34.     L1.insert(L1.begin(), -20); // 开始位置插入 -20
    35.     PrintList(L1); // -20 -10 10
    36.  
    37.     // insert(pos, n, elem); 在 pos 位置插入 n 个 elem 数据，无返回值
    38.     L1.insert(L1.end(), 1, 20); // 最后一个位置插入 1 个 20
    39.     PrintList(L1); // -20 -10 10 20
    40.  
    41.     
    42.     list<int>L2;
    43.     for (int i = 0; i < 5; i++) {
    44.         L2.push_back(i + 1);
    45.     }
    46.     // insert(pos, beg, end); 在 pos 位置插入 [beg, end) 数据，无返回值
    47.     L1.insert(L1.begin(), L2.begin(), L2.end());
    48.     PrintList(L1); // 1 2 3 4 5 -20 -10 10 20
    49.  
    50.     // erase(beg, end); 删除 [beg, end) 区间数据，返回下一个数据的位置
    51.     L1.erase(++L1.begin(), --L1.end()); // 双向迭代器，只能 ++-- ，前置才有效
    52.     PrintList(L1); // 1 20
    53.  
    54.     // erase(pos); 删除 pos 位置数据，返回下一个数据的位置
    55.     L1.erase(L1.begin());
    56.     PrintList(L1); // 20
    57.  
    58.     L1.push_back(30);
    59.  
    60.     // clear(); 清空 list 容器数据
    61.     L1.clear();
    62.     if (!L1.size()) {
    63.         cout << "L1 为空" << endl;
    64.     }
    65.     else {
    66.         cout << "L1 非空" << endl;
    67.     }
    68.     PrintList(L1); // 空
    69.  
    70.     
    71.     list<int>L3;
    72.     L3.push_back(10);
    73.     L3.push_back(20);
    74.     L3.push_back(10);
    75.     L3.push_back(20);
    76.     L3.push_back(10);
    77.     L3.push_back(20);
    78.  
    79.     // remove(num); 移除 list 容器中与 num 匹配的数据
    80.     L3.remove(10);
    81.     PrintList(L3); // 20 20 20
    82. }
    83.  
    84. int main() {
    85.     test();
    86.     system("pause");
    87.     return 0;
    88. }

    运行结果：

    list 数据存取

    功能：

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

    函数原型：

    1. // 返回第一个元素
    2. front();
    3.  
    4. // 返回最后一个元素
    5. back();

    不可以使用 [ ] 方式访问 list 容器

    不可以使用 at 方式访问 list 容器

    原因：本质是链表，每个数据不是用连续的线性空间存储的，迭代器也不支持随机访问

    测试代码：

    1. #include
    2. using namespace std;
    3. #include
    4.  
    5. void PrintList(const list<int>& L) {
    6.     for (list<int>::const_iterator Lit = L.begin(); Lit != L.end(); ++Lit) {
    7.         cout << *Lit << " ";
    8.     }
    9.     cout << endl;
    10. }
    11.  
    12. void test() {
    13.     list<int>L1;
    14.  
    15.     L1.push_back(10);
    16.     L1.push_back(20);
    17.     L1.push_back(30);
    18.     L1.push_back(40);
    19.  
    20.     cout << "第一个元素：  " << L1.front() << endl;
    21.     cout << "最后一个元素：" << L1.back()  << endl;
    22.  
    23.     // 迭代器不支持随机访问
    24.     list<int>::iterator it = L1.begin();
    25.  
    26.     //it = it + 1;  // × 没有与操作符 + 匹配的运算符
    27.     //it = it++;    // √
    28.     //it = it++;    // 只能这样一步一步加
    29.     //it = it--;    // √，支持双向
    30. }
    31.  
    32. int main() {
    33.     test();
    34.     system("pause");
    35.     return 0;
    36. }

    运行结果：

    list 反转和排序

    功能：

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

    函数原型：

    1. // 反转链表
    2. reverse();
    3.  
    4. // 链表排序
    5. sort();

    测试代码：

    1. #include
    2. using namespace std;
    3. #include
    4.  
    5. void PrintList(const list<int>& L) {
    6.     for (list<int>::const_iterator Lit = L.begin(); Lit != L.end(); ++Lit) {
    7.         cout << *Lit << " ";
    8.     }
    9.     cout << endl;
    10. }
    11.  
    12. bool myCompare(int a, int b) {
    13.     return (a > b);
    14. }
    15.  
    16. void test() {
    17.     list<int>L1;
    18.     L1.push_back(9);
    19.     L1.push_back(5);
    20.     L1.push_back(8);
    21.     L1.push_back(6);
    22.     L1.push_back(7);
    23.  
    24.     
    25.     cout << "反转前：";
    26.     PrintList(L1); // 9 5 8 6 7
    27.  
    28.     cout << "反转后：";
    29.     L1.reverse();    
    30.     PrintList(L1); // 7 6 8 5 9
    31.  
    32.     cout << "排序前：";
    33.     PrintList(L1); // 7 6 8 5 9
    34.     
    35.     cout << "排序后：";
    36.     L1.sort();     // 从小到大，想要降序再 reverse 一下
    37.     PrintList(L1); // 5 6 7 8 9
    38.  
    39.     // sort() 还有一个重载的版本，可以降序
    40.     cout << "降序：  ";
    41.     L1.sort(myCompare);
    42.     PrintList(L1); // 9 8 7 6 5
    43.     
    44.     // 所有不支持随机访问迭代器的容器，不可以使用标准算法
    45.     // sort(L1.begin(), L1.end()); // 错误
    46. }
    47.  
    48. int main() {
    49.     test();
    50.     system("pause");
    51.     return 0;
    52. }

    运行结果：

    list 排序案例

     案例：将 Person 自定义数据类型进行排序，Person 中属性有 name、age、high 

    -

    排序规则：按 age 进行升序，如果 age 相等就按 high 进行降序

    代码实例：

    1. #include
    2. using namespace std;
    3. #include
    4. #include
    5.  
    6. class Person {
    7.  
    8.     friend void PrintList(list& P_List);
    9.     friend bool comparePerson(Person& p1, Person& p2);
    10. public:
    11.     Person(string name, int age, int high) :m_Name(name), m_Age(age), m_High(high) { }
    12. private:
    13.     string m_Name;
    14.     int m_Age;
    15.     int m_High;
    16. };
    17.  
    18. void PrintList(list& P_List) {
    19.     for (list::iterator it = P_List.begin(); it != P_List.end(); ++it) {
    20.         cout << "姓名:" << (*it).m_Name << " 年龄:" << it->m_Age << " 身高:" << (*it).m_High << endl;
    21.     }
    22. }
    23.  
    24. // 指定排序规则
    25. bool comparePerson(Person& p1, Person& p2) {
    26.     if (p1.m_Age == p2.m_Age) {
    27.         return p1.m_High > p2.m_High;
    28.     }
    29.     else {
    30.         return p1.m_Age < p2.m_Age;
    31.     }
    32. }
    33.  
    34. void test() {
    35.     listPerson_List;
    36.     Person p1("李华", 18, 180);
    37.     Person p2("张三", 19, 170);
    38.     Person p3("王五", 20, 175);
    39.     Person p4("赵六", 20, 170);
    40.     Person p5("李四", 20, 180);
    41.  
    42.     Person_List.push_back(p1);
    43.     Person_List.push_back(p2);
    44.     Person_List.push_back(p3);
    45.     Person_List.push_back(p4);
    46.     Person_List.push_back(p5);
    47.  
    48.     cout << "排序前：" << endl;
    49.     PrintList(Person_List);
    50.     cout << "----------------------" << endl;
    51.  
    52.     cout << "排序后：" << endl;
    53.     Person_List.sort(comparePerson);
    54.     PrintList(Person_List);
    55. }
    56.  
    57. int main() {
    58.     test();
    59.     system("pause");
    60.     return 0;
    61. }

    运行结果：

  • 相关阅读:
    vs-debugger远程调试卡死解决
    MySQL库表占用空间排序
    基于事件驱动的任务分布式调度消费方案
    nginx php-fpm swoole
    java毕业生设计校园一卡通管理系统计算机源码+系统+mysql+调试部署+lw
    体育场馆LED显示屏的分类及应用
    金仓数据库KStudio使用手册（3. 数据库管理）
    第十四届蓝桥杯第一期模拟赛 python
    一、项目整合管理
    软文如何打动用户，媒介盒子教你几招
  • 原文地址：https://blog.csdn.net/xuan3215/article/details/126108747