【C++指南】C++ list容器完全解读（二）：list模拟实现，底层架构揭秘

.

📝Gitee主页：倔强的石头的gitee主页

⏩ 文章专栏：《C++指南》

期待您的关注

文章目录

• • • 引言
    • 一、链表节点设计：双向链表的基石
    • • 1.1 节点类的实现
      • 二、list框架与核心成员函数
      • • 2.1 list类的成员变量
        • 2.2 构造函数与初始化
        • 2.3 深拷贝
        • 2.4 赋值运算符重载：传统写法 vs 现代写法
        • 2.4 构造函数重载与冲突解决
        • 三、修改操作：插入与删除
        • • 3.1 插入操作`insert`
          • 3.2 删除操作`erase`
          • 四、其他关键函数实现
          • • 4.1 容量操作
            • 4.1 交换函数
            • 4.2 自定义swap的高效实现
            • 结语

              引言

              在上一篇文章【C++指南】STL list容器完全解读（一）：从入门到掌握基础操作中，我们深入探讨了list容器的核心特性、使用场景及接口规范。

              本文作为系列第二篇，将聚焦于list的底层模拟实现，通过手写双向链表结构，揭示其高效插入删除的底层逻辑。

              通过本文，您将掌握：

              • 双向链表的节点设计与内存管理
              • list核心成员函数的实现原理
              • 深拷贝与现代C++优化技巧
              • STL容器设计中的关键思想

                一、链表节点设计：双向链表的基石

                1.1 节点类的实现

                list_node是链表的原子单位，需包含数据域和前后指针：

                template 
                struct list_node {
                    T data;            // 数据域
                    list_node* next; // 后继指针
                    list_node* prev; // 前驱指针
                    // 构造函数：支持默认值初始化
                    list_node(const T& x = T()) 
                        : data(x), next(nullptr), prev(nullptr) {}
                };
                

                关键点：

                • 模板化设计支持任意数据类型
                • 默认构造函数初始化指针为nullptr，避免野指针

                  ---

                  二、list框架与核心成员函数

                  2.1 list类的成员变量

                  template 
                  class list {
                  private:
                      typedef list_node Node;
                      Node* _head;    // 头节点（哨兵节点）
                      size_t _size;   // 元素数量
                  public:
                      // 迭代器声明（下篇详解）
                      typedef list_iterator iterator;
                      // ... 其他成员函数
                  };
                  

                  

                  核心设计思想：

                  • 头节点作为哨兵节点，使空链表的begin()和end()统一指向_head
                  • _size记录元素数量，避免遍历统计

                    2.2 构造函数与初始化

                    // 默认构造：创建空链表
                    list() { empty_init(); }
                    // 初始化函数：构建头节点闭环
                    void empty_init() {
                        _head = new Node();
                        _head->next = _head;
                        _head->prev = _head;
                        _size = 0;
                    }
                    

                    注意事项：

                    • 头节点的next和prev均指向自身，形成环形结构

                      2.3 深拷贝

                      拷贝构造：

                      list(const list& s) {
                          empty_init();
                          for (auto& i : s) push_back(i); // 深拷贝
                      }
                      

                      2.4 赋值运算符重载：传统写法 vs 现代写法

                      传统写法（显式深拷贝）

                      list& operator=(const list& s) {  
                          if (this != &s) {          // 防止自赋值  
                              clear();               // 清空当前链表  
                              for (auto& val : s) {  
                                  push_back(val);    // 逐元素深拷贝  
                              }  
                          }  
                          return *this;  
                      }  
                      

                      缺点：代码冗余，需手动处理资源释放与拷贝。

                      现代写法（资源交换）

                      list& operator=(list s) {  
                          swap(s);    // 传递临时对象，利用拷贝构造完成深拷贝  
                          return *this;  
                      }  
                      

                      优势：

                      • 利用拷贝构造函数生成临时对象s，自动完成深拷贝
                      • 通过swap交换资源，临时对象s析构时自动释放旧数据

                        ---

                        2.4 构造函数重载与冲突解决

                        1. 多个val值的构造

                        // 填充构造函数：创建n个值为val的元素  
                        list(size_t n, const T& val = T()) {  
                            empty_init();  
                            for (size_t i=0; i  
                            empty_init();  
                            for (int i=0; i  
                            empty_init();  
                            for (auto& elem : il) push_back(elem);  
                        }  
                          
                            empty_init();  
                            while (first != last) {  
                                push_back(*first);  
                                ++first;  
                            }  
                        }  
                        
                            Node* cur = pos._node;      // 当前节点
                            Node* prev = cur-prev;     // 前驱节点
                            Node* new_node = new Node(val); // 新节点
                            // 链接新节点
                            prev-next = new_node;
                            new_node->prev = prev;
                            new_node->next = cur;
                            cur->prev = new_node;
                            _size++;
                            return iterator(new_node);  // 返回新节点迭代器
                        }
                        

                        复用插入实现push_back/push_front：

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

                        3.2 删除操作erase

                        iterator erase(iterator pos) {
                            assert(pos != end()); // 禁止删除头节点
                            Node* cur = pos._node;
                            Node* prev = cur->prev;
                            Node* next = cur->next;
                            // 跳过被删节点
                            prev->next = next;
                            next->prev = prev;
                            delete cur;
                            _size--;
                            return iterator(next); // 返回下一节点迭代器
                        }
                        

                        复用删除实现pop_back/pop_front：

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

                        四、其他关键函数实现

                        4.1 容量操作

                        // 清空链表（保留头节点）
                        void clear() {
                            iterator it = begin();
                            while (it != end()) it = erase(it);
                        }
                        bool empty()//判空
                        {
                        	return _size == 0;
                        }
                        size_t size()//获取链表元素个数
                        {
                        	return _size;
                        }
                        

                        4.1 交换函数

                        STL的std::swap通过三次拷贝完成交换：

                        template   
                        void swap(T& a, T& b) {  
                            T tmp(a);  
                            a = b;  
                            b = tmp;  
                        }  
                        

                        问题：

                        • 对链表而言，逐节点拷贝效率极低（时间复杂度O(n)）

                          4.2 自定义swap的高效实现

                          类内swap：直接交换头指针与_size

                          void swap(list& other) {  
                              std::swap(_head, other._head); // O(1)交换  
                              std::swap(_size, other._size);  
                          }  
                          

                          全局swap适配：确保ADL正确调用

                          template   
                          void swap(list& a, list& b) {  
                              a.swap(b); // 调用类内swap  
                          }  
                          

                          为何需要全局swap？

                          • 若用户调用swap(lst1, lst2)，编译器优先查找参数关联的命名空间
                          • 全局swap确保调用自定义实现，而非低效的std::swap

                            结语

                            本文从双向链表的节点设计出发，逐步实现了list的核心功能，揭示了STL容器设计中的内存管理与接口复用思想。

                            在下一篇文章中，我们将深入探讨迭代器的封装与类型萃取技术

                            下篇预告：《【C++指南】C++ list容器完全解读（三）：list迭代器的实现与优化》—— 揭秘STL迭代器如何实现“透明访问”与高效遍历！