异常教程

C++ 容器类 <list>（超详细）

更新时间:

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

截止目前， 星球 内专栏累计输出 90w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 3100+ 小伙伴加入学习 ，欢迎点击围观

前言

在 C++ 的标准模板库（STL）中，容器类是数据存储与操作的核心工具。其中 <list> 容器类以双向链表的底层实现，成为处理动态数据的高效选择。本文将从基础概念、核心操作、性能分析到实战案例，系统性讲解 <list> 的使用场景与技巧，帮助开发者理解其优势与局限性。无论是需要频繁插入删除元素的场景，还是对内存连续性要求不高的任务，<list> 都是值得深入掌握的容器之一。

核心概念解析：双向链表的特性与优势

什么是双向链表？

<list> 是基于双向链表结构实现的容器。想象一个由多个“车厢”组成的火车：每个车厢（节点）不仅知道下一个车厢的位置，还知道前一个车厢的位置。这种设计使得：

  • 插入/删除操作高效：在链表中间插入或删除元素时，只需调整相邻节点的指针，无需移动大量数据。
  • 内存不连续：每个节点独立分配内存，因此无法通过索引直接访问元素（与 vector 的连续内存不同）。

与 vector 的对比：适用场景的差异

场景类型<list> 的优势vector 的优势
频繁插入/删除O(1) 时间复杂度（尾部插入）O(n) 时间复杂度（需移动元素）
随机访问不支持（需遍历）O(1) 时间复杂度（通过索引）
内存占用较高（每个节点需存储前后指针）较低（连续内存无额外开销）

比喻：<list> 像一条灵活的蛇，能轻松在任意位置增减身体；而 vector 更像一本精装书，页码固定，但翻页速度极快。

基础操作详解：从创建到遍历

初始化与元素添加

创建 <list> 并添加元素的代码示例如下：

#include <list>  
#include <iostream>  

int main() {  
    // 创建空列表  
    std::list<int> my_list;  

    // 尾部添加元素  
    my_list.push_back(10);  

    // 头部添加元素  
    my_list.push_front(20);  

    // 输出列表元素  
    for (int num : my_list) {  
        std::cout << num << " "; // 输出：20 10  
    }  
    return 0;  
}

迭代器与元素访问

由于 <list> 不支持随机访问，必须通过迭代器逐个访问元素。例如，使用 begin() 和 end() 定义遍历范围：

std::list<std::string> names = {"Alice", "Bob", "Charlie"};  
for (auto it = names.begin(); it != names.end(); ++it) {  
    std::cout << *it << " "; // 输出：Alice Bob Charlie  
}

插入与删除操作

  • 在指定位置插入元素：insert 函数接受迭代器参数，表示插入位置： 
    auto pos = my_list.begin();  
my_list.insert(pos, 30); // 将30插入头部
  • 删除指定元素：erase 函数通过迭代器定位元素并删除： 
    my_list.erase(pos); // 删除第一个元素（30）

进阶功能与技巧

合并列表与排序

<list> 提供高效的合并功能：

std::list<int> list1 = {1, 3, 5};  
std::list<int> list2 = {2, 4};  
list1.merge(list2); // 合并后 list1 变为 {1, 2, 3, 4, 5}  
list1.sort();       // 若元素无序，需先排序才能合并

自定义排序规则

通过 sort 的自定义比较函数，可实现非默认排序：

struct CompareLength {  
    bool operator()(const std::string& a, const std::string& b) {  
        return a.length() < b.length();  
    }  
};  

std::list<std::string> words = {"apple", "banana", "pear"};  
words.sort(CompareLength()); // 按字符串长度升序排列

反转与截断操作

my_list.reverse();    // 反转元素顺序  
my_list.resize(2);    // 截断或扩展列表到指定大小  
my_list.clear();      // 清空所有元素

性能分析与适用场景

时间复杂度对比表

操作<list> 时间复杂度vector 时间复杂度
插入/删除头部O(1)O(n)
插入/删除中间O(1)*（需已知迭代器）O(n)
随机访问O(n)O(1)
空间占用较高较低

*注：若已知迭代器位置，插入/删除效率高；否则需遍历查找，时间复杂度为 O(n)。

适用场景举例

  1. 实时任务队列：如游戏中的待处理事件队列，频繁插入新事件到队列头部。
  2. 数据流处理：需动态添加/删除元素，但无需频繁随机访问的场景。
  3. 内存敏感环境：当数据量极大且频繁修改结构时，<list> 的灵活性可能优于 vector。

实战案例：实现一个任务队列

需求描述

设计一个任务队列，支持以下操作：

  • 添加新任务到队列尾部。
  • 移除并执行队列头部的任务。
  • 在队列中间插入高优先级任务。

代码实现

#include <list>  
#include <functional> // for std::function  

class TaskQueue {  
public:  
    void enqueue(const std::function<void()>& task) {  
        tasks.push_back(task);  
    }  

    void dequeue() {  
        if (!tasks.empty()) {  
            tasks.front()(); // 执行任务  
            tasks.pop_front();  
        }  
    }  

    void insert_high_priority(const std::function<void()>& task) {  
        tasks.insert(tasks.begin(), task); // 插入头部  
    }  

private:  
    std::list<std::function<void()>> tasks;  
};  

int main() {  
    TaskQueue queue;  
    queue.enqueue([]{ std::cout << "Normal Task\n"; });  
    queue.insert_high_priority([]{ std::cout << "High Priority Task\n"; });  
    queue.dequeue(); // 输出：High Priority Task  
    return 0;  
}

代码解析

  • 使用 <list> 的 push_back 和 pop_front 实现高效队列操作。
  • 通过 insert(tasks.begin(), ...) 快速将高优先级任务置于队列头部。

结论

<list> 作为 C++ 中的双向链表容器，凭借其灵活的插入删除能力和稳定的性能，在特定场景下是 vector 或 deque 的理想替代。开发者需根据实际需求权衡：若数据结构频繁变化且无需随机访问，<list> 的 O(1) 操作能显著提升效率；若需要快速访问元素或内存连续性更重要，则应选择其他容器。通过本文的案例与代码示例，读者可以快速掌握 <list> 的核心用法，并在实际项目中合理应用这一工具。

最新发布

查看更多文章