跳到主要内容
极客日志极客日志面向AI+效率的开发者社区
首页博客我的书AI学习GitHub 精选镜像AI 生图工具UI配色美学关于
搜索内容 / 工具 / 仓库 / 镜像...⌘K搜索
注册
博客列表
C++算法

C++ STL list 容器详解：使用与模拟实现

深入解析 C++ STL list 容器的原理与实战应用。内容涵盖 list 作为双向循环链表的数据结构特点，重点讲解其 O(1) 插入删除优势及不支持随机访问的限制。详细梳理了常用接口如构造、迭代器操作、容量管理及修改方法，特别强调了迭代器失效的处理策略。此外，文章提供了从节点类、迭代器到容器类的完整模拟实现代码，剖析了头结点设计、模板技巧及资源管理细节，并通过与 vector 的对比表格明确了两者的适用场景。

链路追踪发布于 2026/3/30更新于 2026/9/1051 浏览
C++ STL list 容器详解：使用与模拟实现

C++ STL list 容器详解：使用与模拟实现

1. list 简介及使用

list 是 C++ STL 中基于双向循环链表实现的序列容器。与 vector 不同，它在任意位置插入和删除元素的复杂度均为 O(1)，但不支持随机访问（即无法通过下标直接获取元素）。

1.1 构造方式

常见的构造函数包括默认构造、拷贝构造、区间构造以及指定数量初始化：

构造函数说明
list(size_type n, const value_type& val)创建包含 n 个值为 val 的列表
list()创建空列表
list(const list& x)拷贝构造
list(InputIterator first, InputIterator last)用区间 [first, last) 的元素构造

1.2 迭代器操作

迭代器是对底层节点指针的封装，支持正向和反向遍历。

  • begin() / end()：分别指向首元素和尾后位置。
  • rbegin() / rend()：反向迭代器，rbegin 指向最后一个元素，rend 指向第一个元素前。

注意：正向迭代器 ++ 向后移动，反向迭代器 ++ 向前移动。

1.3 容量与访问

  • empty()：判断是否为空。
  • size()：返回有效节点个数。
  • front() / back()：获取首尾元素的引用。

1.4 修改操作

核心修改接口包括 push_front/back、pop_front/back、insert、erase、swap 和 clear。

1.5 迭代器失效规则

由于底层是双向循环链表，插入操作不会导致现有迭代器失效。只有在删除元素时，指向被删除节点的迭代器才会失效，其他迭代器依然有效。

处理删除时的常见错误写法如下：

while (it != l.end()) { 
    l.erase(it); // it 失效
    ++it;        // 错误，it 已无效
}

正确做法是接收 erase 返回的下一个有效迭代器：

while (it != l.end()) { 
    if (condition) {
        it = l.(it);
    }  {
        ++it;
    }
}
erase
else

2. list 的模拟实现

要实现一个标准的 list，我们需要关注节点结构、迭代器设计以及容器类的逻辑。

2.1 基础结构

节点类

每个节点存储数据及前后指针，采用双向链表设计：

template<class T> class list_node {
public:
    T _data;
    list_node<T>* _next;
    list_node<T>* _prev;

    list_node(const T& data = T()) :_data(data), _next(nullptr), _prev(nullptr) {}
};
迭代器类

迭代器需要支持解引用、箭头操作符以及自增自减。为了同时支持 const 和非 const 迭代器，我们使用模板参数控制返回值类型：

template<class T, class Ref, class Ptr>
struct list_iterator {
    typedef list_node<T> Node;
    typedef list_iterator<T, Ref, Ptr> Self;
    Node* _node;

    list_iterator(Node* node) :_node(node) {}

    Ref operator*() { return _node->_data; }
    Ptr operator->() { return &_node->_data; }

    Self& operator++() { _node = _node->_next; return *this; }
    Self operator++(int) { Self tmp(*this); _node = _node->_next; return tmp; }
    Self& operator--() { _node = _node->_prev; return *this; }
    Self operator--(int) { Self tmp(*this); _node = _node->_prev; return tmp; }

    bool operator!=(const Self& s) { return _node != s._node; }
};

2.2 容器类实现

类型定义

利用迭代器的模板特性，定义普通迭代器和常量迭代器：

template<class T> class list {
    typedef list_node<T> Node;
public:
    typedef list_iterator<T, T&, T*> iterator;
    typedef list_iterator<T, const T&, const T*> const_iterator;

    iterator begin() { return _head->_next; }
    iterator end() { return _head; }
    const_iterator begin() const { return _head->_next; }
    const_iterator end() const { return _head; }

这里 _head 是头结点，begin 返回头结点的下一个节点，end 返回头结点本身，符合 STL 左闭右开的习惯。

初始化与析构

构造时创建一个空的循环链表，析构时清理所有节点：

void empty_init() {
    _head = new Node;
    _head->_next = _head;
    _head->_prev = _head;
    _size = 0;
}

list() { empty_init(); }
~list() { clear(); delete _head; _head = nullptr; }
插入与删除

插入操作的核心在于调整前后指针。insert 函数在给定位置之前插入新节点：

iterator insert(iterator pos, const T& x) {
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* newnode = new Node(x);
    prev->_next = newnode;
    newnode->_prev = prev;
    newnode->_next = cur;
    cur->_prev = newnode;
    ++_size;
    return newnode;
}

删除操作则需断开连接并释放内存，同时返回下一个有效位置的迭代器：

iterator erase(iterator pos) {
    assert(pos != end());
    Node* prev = pos._node->_prev;
    Node* next = pos._node->_next;
    prev->_next = next;
    next->_prev = prev;
    delete pos._node;
    --_size;
    return next;
}
赋值与交换

利用拷贝交换原则实现高效的赋值操作：

list<T>& operator=(list<T> lt) {
    swap(lt);
    return *this;
}

void swap(list<T>& lt) {
    std::swap(_head, lt._head);
    std::swap(_size, lt._size);
}

2.3 测试示例

验证基本功能及迭代器失效情况：

void test_list01() {
    list<int> lt;
    lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4);
    for (auto it = lt.begin(); it != lt.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

void test_list02() {
    list<int> lt;
    lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4);
    // 插入不失效
    auto it = lt.begin();
    lt.insert(it, 10);
    *it += 100;
    
    // 删除偶数
    it = lt.begin();
    while (it != lt.end()) {
        if (*it % 2 == 0) {
            it = lt.erase(it);
        } else {
            ++it;
        }
    }
}

3. list 与 vector 对比

维度vectorlist
底层结构动态顺序表，连续空间带头结点的双向循环链表
随机访问支持 O(1)不支持，O(N)
插入删除任意位置效率低 O(N)，可能增容任意位置效率高 O(1)
空间利用率连续空间，缓存友好节点动态开辟，易碎片
迭代器类型原生指针封装后的迭代器
迭代器失效插入可能导致全部失效仅当前删除的迭代器失效

完整实现参考

以下是整合后的完整代码，包含节点、迭代器及容器类定义：

#pragma once
#include <iostream>
#include <algorithm>
#include <initializer_list>
#include <assert.h>

using namespace std;

template<class T>
class list_node {
public:
    T _data;
    list_node<T>* _next;
    list_node<T>* _prev;

    list_node(const T& data = T()) :_data(data), _next(nullptr), _prev(nullptr) {}
};

template<class T, class Ref, class Ptr>
struct list_iterator {
    typedef list_node<T> Node;
    typedef list_iterator<T, Ref, Ptr> Self;
    Node* _node;

    list_iterator(Node* node) :_node(node) {}

    Ref operator*() { return _node->_data; }
    Ptr operator->() { return &_node->_data; }

    Self& operator++() { _node = _node->_next; return *this; }
    Self operator++(int) { Self tmp(*this); _node = _node->_next; return tmp; }
    Self& operator--() { _node = _node->_prev; return *this; }
    Self operator--(int) { Self tmp(*this); _node = _node->_prev; return tmp; }

    bool operator!=(const Self& s) { return _node != s._node; }
};

template<class T>
class list {
    typedef list_node<T> Node;
public:
    typedef list_iterator<T, T&, T*> iterator;
    typedef list_iterator<T, const T&, const T*> const_iterator;

    iterator begin() { return _head->_next; }
    iterator end() { return _head; }
    const_iterator begin() const { return _head->_next; }
    const_iterator end() const { return _head; }

    void empty_init() {
        _head = new Node;
        _head->_next = _head;
        _head->_prev = _head;
        _size = 0;
    }

    list() { empty_init(); }
    ~list() { clear(); delete _head; _head = nullptr; }

    void clear() {
        auto it = begin();
        while (it != end()) {
            it = erase(it);
        }
    }

    list<T>& operator=(list<T> lt) {
        swap(lt);
        return *this;
    }

    void swap(list<T>& lt) {
        std::swap(_head, lt._head);
        std::swap(_size, lt._size);
    }

    list(list<T>& lt) {
        empty_init();
        for (auto& e : lt) {
            push_back(e);
        }
    }

    list(initializer_list<int> il) {
        empty_init();
        for (auto& e : il) {
            push_back(e);
        }
    }

    void push_back(const T& x) {
        insert(end(), x);
    }

    iterator insert(iterator pos, const T& x) {
        Node* cur = pos._node;
        Node* prev = cur->_prev;
        Node* newnode = new Node(x);
        prev->_next = newnode;
        newnode->_prev = prev;
        newnode->_next = cur;
        cur->_prev = newnode;
        ++_size;
        return newnode;
    }

    void push_front(const T& x) {
        insert(begin(), x);
    }

    void pop_back() {
        erase(--end());
    }

    void pop_front() {
        erase(begin());
    }

    iterator erase(iterator pos) {
        assert(pos != end());
        Node* prev = pos._node->_prev;
        Node* next = pos._node->_next;
        prev->_next = next;
        next->_prev = prev;
        delete pos._node;
        --_size;
        return next;
    }

    size_t size() const { return _size; }
    bool empty() const { return _size == 0; }

private:
    Node* _head;
    size_t _size;
};

总结

实现 list 的关键在于处理好头结点的循环链接以及迭代器的边界条件。通过模板参数统一 const 与非 const 行为，可以大幅减少代码冗余。在实际开发中，若频繁进行中间插入删除且无需随机访问，list 是比 vector 更合适的选择。

目录

  1. C++ STL list 容器详解：使用与模拟实现
  2. 1. list 简介及使用
  3. 1.1 构造方式
  4. 1.2 迭代器操作
  5. 1.3 容量与访问
  6. 1.4 修改操作
  7. 1.5 迭代器失效规则
  8. 2. list 的模拟实现
  9. 2.1 基础结构
  10. 节点类
  11. 迭代器类
  12. 2.2 容器类实现
  13. 类型定义
  14. 初始化与析构
  15. 插入与删除
  16. 赋值与交换
  17. 2.3 测试示例
  18. 3. list 与 vector 对比
  19. 完整实现参考
  20. 总结

更多推荐文章

查看全部
  • 9种降低论文AIGC检测率的工具推荐与使用指南
  • Spring Boot Web 三大核心交互案例：表单、AJAX 及 JSON
  • FPGA 入门：基于 Verilog 的 2 选 1 多路选择器设计
  • Ubuntu 安装 Miniconda 完整指南与环境管理
  • ComfyUI Manager 使用指南：插件与模型管理优化
  • Java 转 AI：经验分享与实战路线
  • Java 位运算算法题目练习
  • AI 产品经理面试指南与职业发展路径分析
  • Linux 环境变量详解：从底层原理到实战操作
  • Pico 4XVR 1.10.13 安装包下载与安装教程
  • Adobe Illustrator 2025 安装配置与高效使用指南
  • 国产 AI 大模型在医疗领域的十大应用场景案例盘点
  • 动态规划基础概念及第 N 个泰波那契数题解 (1)
  • Python 数据可视化：9 种常用图表及实现方法
  • AI 驱动游戏：鸿蒙生态的机会在哪里？
  • MAVROS 安装与基础知识梳理及 ROS C++ 仿真案例
  • Python 发展前景与零基础入门学习路径
  • Android 面试经验复盘与核心知识点梳理
  • Stable Diffusion 数据集标签编辑器使用指南
  • OpenClaw 安全风险全解析：AI 助手部署中的权限与数据隐患

相关免费在线工具

  • 加密/解密文本

    使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online

  • Gemini 图片去水印

    基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印，支持批量处理与下载。 在线工具，Gemini 图片去水印在线工具，online

  • Base64 字符串编码/解码

    将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online

  • Base64 文件转换器

    将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online

  • Markdown转HTML

    将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online

  • HTML转Markdown

    将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online