手撕C++ STL list容器：从指针缠绕到迭代器封装的实践笔记

前言

最近在学习STL容器的底层实现，发现双向链表（list）的设计非常巧妙。为了深入理解其原理，我决定从零实现一个简化版list。本文将分享我的实现思路、踩坑记录以及关键代码解析，完整代码已上传至Gitee仓库Gitee仓库https://gitee.com/roaring-black-fertilizer/cpp/commit/a927d1cad5eb1f9227b6f1b374221a6faef7d608

一、整体设计思路

1.1 选择双向链表的原因

插入/删除高效：时间复杂度O(1)
支持双向遍历：每个节点保存前后指针
环形结构：通过哨兵节点(_head)统一处理边界

1.2 三大核心组件

节点结构体(list_node)：数据域+双指针
迭代器(_list_iterator)：解引用与遍历的封装
链表类(list)：容器功能的具体实现

二、关键实现细节

2.1 节点结构设计

template<class T>
struct list_node {list_node<T>* _next;list_node<T>* _prev;T _val;// 构造函数统一初始化list_node(const T& val = T()): _next(nullptr), _prev(nullptr), _val(val) {}
};

采用模板支持泛型
默认构造生成匿名对象T()

2.2 迭代器封装的精髓

template<class T, class Ref, class Ptr>
struct _list_iterator {typedef list_node<T> Node;Node* _node;// 重载关键运算符Ref operator*() { return _node->_val; }  // 解引用Ptr operator->() { return &_node->_val; } // 成员访问// 前置++返回引用，后置++返回值self& operator++() {_node = _node->_next;return *this;}
};

模板参数三件套：T（元素类型）、Ref（引用类型）、Ptr（指针类型）
运算符重载：使迭代器能像指针一样操作
const迭代器：通过模板参数自动生成

2.3 链表类的核心实现

初始化与内存管理

void empty_init() {_head = new Node; // 哨兵节点_head->_prev = _head;_head->_next = _head;_size = 0;
}

环形结构初始化：头节点的前后指针都指向自己
RAII原则：构造函数初始化，析构函数释放内存

插入删除操作

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;
}

异常安全：先创建新节点再修改链接
size维护：手动计数代替遍历统计

三、踩坑与解决方案

3.1 迭代器失效问题

现象：在遍历时删除元素导致崩溃

解决：erase()返回下一个有效迭代器

iterator erase(iterator pos) {assert(pos != end());Node* next = pos._node->_next;// ...执行删除操作return next; // 返回后续迭代器
}

3.2 深拷贝难题

原始问题：默认拷贝构造导致浅拷贝

解决方案：重写拷贝构造和赋值运算符

list(const list<T>& lt) {empty_init();for (auto& e : lt) push_back(e);
}list<T>& operator=(list<T> lt) {swap(lt); // 利用拷贝交换技法return *this;
}

四、测试验证示例

4.1 基础功能测试

void test_list1() {fertilizer::list<int> lt;lt.push_back(1);lt.push_front(0); // 头部插入auto it = lt.begin();while (it != lt.end()) {*it += 1; // 修改元素值cout << *it << " ";++it;}// 输出：1 2
}

4.2 自定义类型支持

struct A { int _a1, _a2; };void test_list3() {list<A> lt;lt.push_back(A(1,1));list<A>::iterator it = lt.begin();cout << it->_a1; // 通过->访问成员
}

五、与STL list的对比

特性	本实现	STL list
迭代器类别	双向迭代器	双向迭代器
异常安全	基本保证	强异常保证
内存分配器	未实现	支持自定义
算法复杂度	O(1)操作	同左