深入解析【C++ list 容器】：高效数据管理的秘密武器

devtools/2024/10/16 4:33:40/

 

目录

list%20%E7%9A%84%E4%BB%8B%E7%BB%8D%E5%8F%8A%E4%BD%BF%E7%94%A8-toc" style="margin-left:0px;">1. list 的介绍及使用

list%20%E7%9A%84%E4%BB%8B%E7%BB%8D-toc" style="margin-left:40px;">1.1 list 的介绍

知识点：

小李的理解：

list%20%E7%9A%84%E4%BD%BF%E7%94%A8-toc" style="margin-left:40px;">1.2 list 的使用

list%20%E7%9A%84%E6%9E%84%E9%80%A0-toc" style="margin-left:80px;">1.2.1 list 的构造

知识点：

小李的理解：

代码示例：

list%20%E8%BF%AD%E4%BB%A3%E5%99%A8%E7%9A%84%E4%BD%BF%E7%94%A8-toc" style="margin-left:80px;">1.2.2 list 迭代器的使用

知识点：

小李的理解：

代码示例：

list%20%E7%9A%84%E5%AE%B9%E9%87%8F-toc" style="margin-left:80px;">1.2.3 list 的容量

知识点：

小李的理解：

代码示例：

list%20%E7%9A%84%E5%85%83%E7%B4%A0%E8%AE%BF%E9%97%AE-toc" style="margin-left:80px;">1.2.4 list 的元素访问

知识点：

小李的理解：

代码示例：

list%20%E7%9A%84%E4%BF%AE%E6%94%B9%E6%93%8D%E4%BD%9C-toc" style="margin-left:80px;">1.2.5 list 的修改操作

知识点：

小李的理解：

代码示例：

list%20%E8%BF%AD%E4%BB%A3%E5%99%A8%E5%A4%B1%E6%95%88-toc" style="margin-left:80px;">1.2.6 list 迭代器失效

知识点：

小李的理解：

代码示例：

list%20%E7%9A%84%E6%A8%A1%E6%8B%9F%E5%AE%9E%E7%8E%B0-toc" style="margin-left:0px;">2. list 的模拟实现

知识点：

小李的理解：

代码示例：

list%20%E4%B8%8E%20vector%20%E7%9A%84%E5%AF%B9%E6%AF%94-toc" style="margin-left:0px;">3. list 与 vector 的对比

知识点：

小李的理解：

 总结

专栏：C++学习笔记 

上一卷：【C++ 】-vector：新时代动态数组的革新与未来

C++ 中的 list 是一个强大的容器，特别适用于需要频繁插入和删除元素的场景。本文将详细介绍 list 容器，包括其介绍、使用方法、实现原理以及与 vector 容器的对比。

list%20%E7%9A%84%E4%BB%8B%E7%BB%8D%E5%8F%8A%E4%BD%BF%E7%94%A8">1. list 的介绍及使用

list%20%E7%9A%84%E4%BB%8B%E7%BB%8D">1.1 list 的介绍

知识点：

list 是一种序列式容器，底层实现为双向链表。双向链表中的每个元素存储在独立的节点中，节点通过指针互相连接，可以在常数时间内在任意位置进行插入和删除操作。与 forward_list 的单链表不同，list 支持双向迭代。与其他序列式容器（如 array、vector、deque）相比，list 在插入和删除操作方面表现更优，但不支持随机访问。

小李的理解：

list 就像一条双向街道上的车队，每辆车（节点）都有前后两个链接，指向前后两辆车。你可以轻松地在任何地方插入或删除一辆车，而不需要移动其他车。但是，如果你想找到某辆车，就需要从头或尾开始，一辆辆查找，比较费时。

list%20%E7%9A%84%E4%BD%BF%E7%94%A8">1.2 list 的使用

list%20%E7%9A%84%E6%9E%84%E9%80%A0">1.2.1 list 的构造

知识点：

list 提供多种构造方法，包括创建空的 list，创建包含多个相同元素的 list，使用区间构造 list 以及拷贝构造等。

小李的理解：

构造 list 就像创建不同类型的车队，你可以创建一个空车队，或者一个全是同样车的车队，还可以用现有的车队来创建新的车队。

代码示例：
#include <list>
#include <iostream>int main() {// 创建一个空的 liststd::list<int> empty_list;// 创建一个包含 5 个值为 10 的元素的 liststd::list<int> filled_list(5, 10);// 使用区间构造 listint arr[] = {1, 2, 3, 4, 5};std::list<int> range_list(arr, arr + 5);// 打印 filled_list 的元素for(int n : filled_list) {std::cout << n << " ";}std::cout << std::endl;return 0;
}

这个程序首先创建一个空的 list，然后创建一个包含 5 个值为 10 的 list，接着用数组中的元素构造一个 list。最后打印 filled_list 的元素，显示 5 个 10。

list%20%E8%BF%AD%E4%BB%A3%E5%99%A8%E7%9A%84%E4%BD%BF%E7%94%A8">1.2.2 list 迭代器的使用

知识点：

list 的迭代器类似于指针，指向 list 中的节点。你可以使用迭代器遍历 list，访问或修改元素。

小李的理解：

迭代器就像你走在车队中的一个人，你可以走到每辆车旁边查看里面的东西，或者往回走查看后面的车。

代码示例：
#include <list>
#include <iostream>int main() {std::list<int> my_list = {1, 2, 3, 4, 5};// 正向迭代for (auto it = my_list.begin(); it != my_list.end(); ++it) {std::cout << *it << " ";}std::cout << std::endl;// 反向迭代for (auto rit = my_list.rbegin(); rit != my_list.rend(); ++rit) {std::cout << *rit << " ";}std::cout << std::endl;return 0;
}

这个程序创建一个包含 5 个整数的 list。正向迭代器遍历 list，从头到尾打印元素，反向迭代器遍历 list，从尾到头打印元素。

list%20%E7%9A%84%E5%AE%B9%E9%87%8F">1.2.3 list 的容量

知识点：

你可以使用 empty() 函数检查 list 是否为空，使用 size() 函数获取 list 中的元素个数。

小李的理解：

这就像你检查车队中是否有车，以及数一数车队中有多少辆车。

代码示例：
#include <list>
#include <iostream>int main() {std::list<int> my_list = {1, 2, 3, 4, 5};// 检查是否为空if (my_list.empty()) {std::cout << "List is empty" << std::endl;} else {std::cout << "List is not empty" << std::endl;}// 获取大小std::cout << "List size: " << my_list.size() << std::endl;return 0;
}

 

程序首先检查 list 是否为空，显然 my_list 不为空，然后打印 list 的大小，显示有 5 个元素。

list%20%E7%9A%84%E5%85%83%E7%B4%A0%E8%AE%BF%E9%97%AE">1.2.4 list 的元素访问

知识点：

你可以使用 front() 函数访问 list 的第一个元素，使用 back() 函数访问 list 的最后一个元素。

小李的理解：

这就像你想看看车队的第一辆车和最后一辆车里装了什么东西。

代码示例：
#include <list>
#include <iostream>int main() {std::list<int> my_list = {1, 2, 3, 4, 5};// 访问第一个和最后一个元素std::cout << "First element: " << my_list.front() << std::endl;std::cout << "Last element: " << my_list.back() << std::endl;return 0;
}

程序分别打印 list 的第一个和最后一个元素，显示 1 和 5。

list%20%E7%9A%84%E4%BF%AE%E6%94%B9%E6%93%8D%E4%BD%9C">1.2.5 list 的修改操作

知识点：

list 提供丰富的修改操作，包括在头部和尾部插入和删除元素，插入和删除特定位置的元素，交换两个 list 的内容以及清空 list。

小李的理解：

这就像你可以在车队的任何位置加车或减车，甚至可以交换两队车里的车，或者把整个车队清空。

代码示例：

 

#include <list>
#include <iostream>int main() {std::list<int> my_list = {1, 2, 3, 4, 5};// 插入和删除操作my_list.push_front(0);  // 在前面插入 0my_list.push_back(6);   // 在后面插入 6my_list.pop_front();    // 删除第一个元素my_list.pop_back();     // 删除最后一个元素// 插入和删除特定位置的元素auto it = my_list.begin();++it;  // 指向第二个元素my_list.insert(it, 100);  // 在第二个位置插入 100it = my_list.begin();++it;my_list.erase(it);  // 删除第二个位置的元素// 交换和清空 liststd::list<int> another_list = {10, 20, 30};my_list.swap(another_list);my_list.clear();return 0;
}

以下是程序在各步之后的状态：

  1. my_list 初始为 {1, 2, 3, 4, 5}
  2. 插入 0 和 6 后为 {0, 1, 2, 3, 4, 5, 6}
  3. 删除第一个和最后一个元素后为 {1, 2, 3, 4, 5}
  4. 在第二个位置插入 100 后为 {1, 100, 2, 3, 4, 5}
  5. 删除第二个位置的元素后为 {1, 2, 3, 4, 5}
  6. 与 another_list 交换后 my_list 为 {10, 20, 30}
  7. 清空后 my_list 为空

list%20%E8%BF%AD%E4%BB%A3%E5%99%A8%E5%A4%B1%E6%95%88">1.2.6 list 迭代器失效

知识点：

在 list 中，插入操作不会导致迭代器失效，删除操作会使指向被删除节点的迭代器失效。

小李的理解：

就像你从车队中移走一辆车时，那个位置的指示牌（迭代器）也被移走了，但其他位置的指示牌不受影响。

代码示例：
#include <list>
#include <iostream>int main() {std::list<int> my_list = {1, 2, 3, 4, 5};auto it = my_list.begin();while (it != my_list.end()) {it = my_list.erase(it);  // 删除元素后，更新迭代器}return 0;
}

这个程序将删除 list 中的所有元素，最后 my_list 为空。

每次删除一个元素后，迭代器指向下一个元素，直到 list 清空。

list%20%E7%9A%84%E6%A8%A1%E6%8B%9F%E5%AE%9E%E7%8E%B0">2. list 的模拟实现

知识点：

实现一个简化版本的 list，需要理解其底层结构和接口的含义。以下是一个简化的 list 实现示例：

小李的理解：

模拟实现 list 就像你自己动手造一辆汽车，你需要理解汽车的每个部件和它们如何协同工作。

代码示例：

#include <iostream>template<typename T>
class Node {
public:T data;Node* prev;Node* next;Node(T val) : data(val), prev(nullptr), next(nullptr) {}
};template<typename T>
class List {
private:Node<T>* head;Node<T>* tail;public:List() : head(nullptr), tail(nullptr) {}void push_back(T val) {Node<T>* newNode = new Node<T>(val);if (!tail) {head = tail = newNode;} else {tail->next = newNode;newNode->prev = tail;tail = newNode;}}void print() {Node<T>* temp = head;while (temp) {std::cout << temp->data << " ";temp = temp->next;}std::cout << std::endl;}~List() {Node<T>* temp;while (head) {temp = head;head = head->next;delete temp;}}
};int main() {List<int> my_list;my_list.push_back(1);my_list.push_back(2);my_list.push_back(3);my_list.print();return 0;
}

这个程序手动实现了一个简单的 list，并添加了 3 个元素。最终打印出 list 中的所有元素。

list%20%E4%B8%8E%20vector%20%E7%9A%84%E5%AF%B9%E6%AF%94">3. list 与 vector 的对比

知识点：

  • 底层结构：

    • vector：动态顺序表，连续内存空间。
    • list：双向链表，不连续。

  • 随机访问：

    • vector：支持，效率为 O(1)。
    • list：不支持，效率为 O(N)。

  • 插入和删除：

    • vector：效率低，时间复杂度为 O(N)。
    • list：效率高，时间复杂度为 O(1)。

  • 空间利用率：

    • vector：高，连续空间，缓存利用率高。
    • list：低，节点动态分配，容易造成内存碎片。

  • 迭代器：

    • vector：原生指针。
    • list：封装的节点指针。

  • 迭代器失效：

    • vector：插入时可能失效，删除时当前迭代器失效。
    • list：插入不会失效，删除时当前迭代器失效。

  • 使用场景：

    • vector：高效存储，随机访问。
    • list：频繁插入和删除操作。

小李的理解：

vector 就像一块连续的停车场，每辆车（元素）都紧挨着，如果你要在中间插入或删除一辆车，就需要挪动很多车。而 list 就像一列火车，每节车厢（元素）独立，可以随意插入或移除车厢，但要找到某个特定车厢就得一节一节地找。

 总结

C++ 中的 list 容器是一个基于双向链表的序列式容器，适用于需要频繁插入和删除操作的场景，但不支持随机访问。list 提供了多种构造方法和丰富的操作接口，包括插入、删除、访问等。与 vector 相比，list 在插入和删除操作上更高效，但在随机访问和空间利用率上较差。


http://www.ppmy.cn/devtools/58733.html

相关文章

自动驾驶决策和控制系统的研究

自动驾驶决策和控制系统的研究

摘要 自动驾驶汽车的决策和控制系统是实现自主驾驶的核心部分。本文详细探讨了自动驾驶系统中决策和控制的基本原理、主要方法及其在实际应用中的挑战与前景。通过对路径规划、行为决策、运动控制等关键环节的分析&#xff0c;本文旨在为自动驾驶技术的发展提供理论基础和实践指…
阅读更多...
新手教学系列——高效管理MongoDB数据：批量插入与更新的实战技巧

新手教学系列——高效管理MongoDB数据：批量插入与更新的实战技巧

前言 在日常开发中，MongoDB作为一种灵活高效的NoSQL数据库，深受开发者喜爱。然而，如何高效地进行数据的批量插入和更新，却常常让人头疼。今天，我们将一起探讨如何使用MongoDB的bulk_write方法，简化我们的数据管理流程，让代码更加简洁高效。 常规做法：find、insertone…
阅读更多...
SpringBoot+Vue（2）excel后台管理页面

SpringBoot+Vue（2）excel后台管理页面

一、需求 SpringBootVue写excel后台管理页面&#xff08;二级页面打开展示每一个excel表&#xff0c;数据库存储字段为“下载、删除、文件详情、是否共享、共享详情”&#xff09; 二、解答 后端(Spring Boot) 1. 项目设置 使用Spring Initializr创建一个新的Spring Boot项目…
阅读更多...
springboot零食盒子-计算机毕业设计源码50658

springboot零食盒子-计算机毕业设计源码50658

目 录 1 绪论 1.1 研究背景 1.2研究意义 1.3论文结构与章节安排 2 微信小程序的零食盒子系统分析 2.1 可行性分析 2.2 系统流程分析 2.2.1 数据流程 3.3.2 业务流程 2.3 系统功能分析 2.3.1 功能性分析 2.3.2 非功能性分析 2.4 系统用例分析 2.5本章小结 3 微信…
阅读更多...
mac ssh连接工具

mac ssh连接工具

在Mac上&#xff0c;有多个SSH连接工具可供选择&#xff0c;这些工具根据其功能和适用场景的不同&#xff0c;可以满足不同用户的需求。以下是一些推荐的SSH客户端软件&#xff1a;12 iTerm2&#xff1a;这是一款功能强大的终端应用程序&#xff0c;提供了丰富的功能和定制选项…
阅读更多...
【android 9】【input】【10.发送按键事件4——View的分发流程】

【android 9】【input】【10.发送按键事件4——View的分发流程】

系列文章目录 可跳转到下面链接查看下表所有内容https://blog.csdn.net/handsomethefirst/article/details/138226266?spm1001.2014.3001.5501文章浏览阅读2次。系列文章大全https://blog.csdn.net/handsomethefirst/article/details/138226266?spm1001.2014.3001.5501 目录…
阅读更多...
自动驾驶---Perception之Occupancy

自动驾驶---Perception之Occupancy

1 背景 在阐述Occupancy之前&#xff0c;先理解为什么要使用Occupancy&#xff1f; 如果自动驾驶车辆在行驶过程中看到的物体不是数据集的一部分&#xff0c;这个时候容易出现误判。 而在基于激光雷达的系统中&#xff0c;由于检测到点云&#xff0c;可以确定障碍物的存在&…
阅读更多...
数据结构——考研笔记（一）绪论

数据结构——考研笔记（一）绪论

目录 数据结构一、绪论1.1 数据结构的基本概念1.1.1 什么是数据&#xff1f;1.1.2 数据元素——描述一个个体1.1.3 什么是数据对象1.1.4 什么是数据机构 1.2 数据结构的三要素1.2.1 逻辑结构1.2.2 数据的运算1.2.3 物理结构1.2.4 数据类型、抽象数据类型1.2.5 知识回顾与重要考…
阅读更多...
最新文章

Copyright @ 2022~2023