0
0

深入探索C++ STL中的list：一份全面指南及实际案例分析

引言

在C++编程中，STL容器是高效和有效管理代码的重要工具。在这些容器中，

  1. list

因其特定的特性而脱颖而出，尤其适合频繁插入和删除的场景。本文将深入探讨

  1. list

容器，分析其结构、用途、优点及与其他STL容器（如

  1. vector

）的区别，并通过丰富的代码示例帮助读者理解相关概念。

1. 理解C++中的

  1. list

1.1 什么是

  1. list

？

C++中的

  1. list

是一个双向链表，允许高效地在列表的开头、结尾及任意位置插入和删除元素。与

  1. vector

不同，

  1. list

不支持随机访问，但在动态内存管理上表现优异，可以最小化重新分配内存的开销。

1.2 使用

  1. list

的原因

  1. list

非常适合频繁插入和删除的场景。例如，在一个待办事项应用中，任务会动态添加和移除，因此使用

  1. list

能够提高效率。了解其核心优势可以帮助你在项目中更好地选择合适的容器。

2. 主要特性与接口

2.1 构造函数

C++为

  1. list

提供了多种构造函数：

  • list() – 构造一个空的列表。
  • list(size_type n, const value_type& val) – 构造一个包含n个元素，值为val的列表。
  • list(InputIterator first, InputIterator last) – 用范围[first, last)中的元素构造列表。

示例：

  1. std::list<int> emptyList;
  2. std::list<int> filledList(5, 10); // 创建一个包含5个元素且每个元素值为10的列表
  3. std::list<int> rangeList(filledList.begin(), filledList.end());

2.2 迭代器

  1. list

中的迭代器类似于指针，用于访问列表中的元素。C++ 

  1. list

支持：

  • begin() 和 end() 用于正向迭代。
  • rbegin() 和 rend() 用于反向迭代。

示例：

  1. std::list<int> mylist = {1, 2, 3, 4, 5};
  2. for (auto it = mylist.begin(); it != mylist.end(); ++it) {
  3.     std::cout << *it << " ";
  4. }

2.3 容量函数

  • empty() – 检查列表是否为空。
  • size() – 返回列表中元素的个数。

示例：

  1. std::list<int> mylist;
  2. if (mylist.empty()) {
  3.     std::cout << "列表为空。\n";
  4. }

2.4 元素访问

  • front() – 访问第一个元素。
  • back() – 访问最后一个元素。

示例：

  1. std::list<int> mylist = {10, 20, 30};
  2. std::cout << "前面元素: " << mylist.front() << ", 后面元素: " << mylist.back() << "\n";

3. 修改函数

  1. list

提供多种用于修改内容的函数：

  • push_front() 和 push_back() 用于添加元素。
  • pop_front() 和 pop_back() 用于删除元素。
  • insert() 和 erase() 用于在特定位置插入和删除元素。

示例：

  1. mylist.push_front(5);
  2. mylist.push_back(40);
  3. mylist.insert(std::next(mylist.begin()), 15); // 在第二个位置插入15

4. 处理迭代器失效

与

  1. vector

不同，

  1. list

的迭代器在插入时仍然有效，只有指向被删除元素的迭代器会失效。这种行为使得

  1. list

在频繁修改结构的场景中更具优势。

示例场景：

  1. auto it = mylist.begin();
  2. mylist.erase(it++); // 正确处理删除元素

5. 自定义实现

  1. list

理解

  1. list

的一个有效方式是自己实现一个基本版本。这个练习可以帮助你深入理解链表的工作原理。

自定义

  1. list

实现示例

  1. class Node {
  2. public:
  3.     int data;
  4.     Node* next;
  5.     Node* prev;
  6.     Node(int val) : data(val), next(nullptr), prev(nullptr) {}
  7. };
  9. class CustomList {
  10. private:
  11.     Node* head;
  12.     Node* tail;
  13. public:
  14.     CustomList() : head(nullptr), tail(nullptr) {}
  15.     
  16.     void push_back(int val) {
  17.         Node* newNode = new Node(val);
  18.         if (!head) {
  19.             head = tail = newNode;
  20.         } else {
  21.             tail->next = newNode;
  22.             newNode->prev = tail;
  23.             tail = newNode;
  24.         }
  25.     }
  26.     
  27.     // 其他功能的实现以展示列表功能
  28. };

6. 探索反向迭代器

反向迭代器允许从尾部向前遍历，适用于在不修改列表的情况下以反向顺序显示元素。

示例：

  1. std::list<int> mylist = {1, 2, 3, 4, 5};
  2. for (auto rit = mylist.rbegin(); rit != mylist.rend(); ++rit) {
  3.     std::cout << *rit << " ";
  4. }

7.迭代器失效概述

什么是迭代器失效？

迭代器失效是指某个迭代器在执行某些操作后，指向的元素不再有效。例如，若一个元素被删除或容器的结构发生了变化，迭代器可能会指向一个已经不存在的元素，从而导致程序错误。

  1. list

的迭代器失效特点

在C++ STL的

  1. list

中，迭代器的失效行为与其他容器（如

  1. vector

）有所不同。由于

  1. list

是一个双向链表，其迭代器在插入操作时不会失效，但在删除操作时，指向被删除元素的迭代器会失效，而其他迭代器则保持有效。这使得

  1. list

在频繁进行插入和删除操作时比其他容器更为安全。

1. 迭代器的有效性

插入操作

当在

  1. list

中插入元素时（如使用

  1. push_front()

、

  1. push_back()

或

  1. insert()

），原有的迭代器不会失效。这是因为

  1. list

的底层结构允许在任何位置添加新节点，而不会影响其他节点的指向。

示例：

  1. std::list<int> mylist = {1, 2, 3};
  2. auto it = mylist.begin();
  3. mylist.insert(it, 0); // 在开头插入0
  4. // 此时，it依然有效，指向原来的第一个元素1
  5. std::cout << *it; // 输出1
删除操作

然而，当删除元素时，指向被删除元素的迭代器会失效。其他迭代器则不受影响。为了安全地使用迭代器，在删除元素后，应注意更新迭代器的值。

示例：

  1. std::list<int> mylist = {1, 2, 3};
  2. auto it = mylist.begin();
  3. mylist.erase(it); // 删除当前元素1
  4. // 此时，it已经失效，使用it会导致未定义行为
  5. // std::cout << *it; // 不安全的操作

2. 正确处理迭代器失效

为了避免迭代器失效带来的问题，我们可以在删除操作后重新赋值迭代器。通常，我们可以在删除操作的同时使用返回值来更新迭代器。

示例：

  1. std::list<int> mylist = {1, 2, 3, 4, 5};
  2. auto it = mylist.begin();
  4. while (it != mylist.end()) {
  5.     if (*it % 2 == 0) { // 如果元素是偶数
  6.         it = mylist.erase(it); // 删除元素并更新it
  7.     } else {
  8.         ++it; // 只在没有删除时才移动迭代器
  9.     }
  10. }

在上述示例中，

  1. erase

函数返回一个指向被删除元素后一个元素的迭代器，从而确保了迭代器的有效性。

3. 反向迭代器的处理

反向迭代器（

  1. rbegin()

和 

  1. rend()

）的使用和正向迭代器相似，但需要注意的是，在进行删除操作后，同样需要更新迭代器。

示例：

  1. std::list<int> mylist = {1, 2, 3, 4, 5};
  2. auto rit = mylist.rbegin();
  4. while (rit != mylist.rend()) {
  5.     if (*rit % 2 != 0) { // 如果元素是奇数
  6.         rit = std::prev(mylist.erase(std::next(rit.base()))); // 更新反向迭代器
  7.     } else {
  8.         ++rit; // 只在没有删除时才移动迭代器
  9.     }
  10. }

8.

  1. list

与

  1. vector

的比较

一个常见的问题是使用

  1. list

还是

  1. vector

。选择取决于对内存管理、插入/删除效率和访问速度的需求：

  • vector 更适合随机访问，且内存使用高效。
  • list 在需要频繁插入和删除的场景中表现更佳。

特性

  1. vector
  1. list

内存连续的非连续的随机访问O(1)不支持插入/删除效率较低（O(n)）在任何位置插入/删除效率高（O(1)）

9. 结论

理解

  1. list

为在C++中管理数据结构打开了新的可能性。通过利用

  1. list

独特的属性，你可以设计高效且响应迅速的应用程序。尝试文中提供的示例，考虑实现你自己的链表，以获得更深入的理解。祝你编程愉快！

标签： c++ list
本文转载自: https://blog.csdn.net/2406_83947720/article/details/143495415
版权归原作者 想成为高手499 所有， 如有侵权，请联系我们删除。
登录后发布评论

“深入探索C++ STL中的list：一份全面指南及实际案例分析”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？

文章导航
没有找到文章内容分段。。。