当前位置：首页 > ops >正文

【C++】 list 容器模拟实现解析

ops 2025/9/6 12:52:51

一、链表节点（list_node）的定义

链表节点是 list 容器的基本组成单元，用于存储数据并维护节点间的连接关系。

template<class T>
struct list_node
{T _data;               // 存储节点数据list_node<T>* _next;   // 指向后一个节点的指针list_node<T>* _prev;   // 指向前一个节点的指针// 构造函数，默认值为T的默认构造list_node(const T& x = T()):_data(x), _next(nullptr), _prev(nullptr){}
};

解析：

节点采用双向链表设计，通过_next和_prev指针维护前后节点关系，支持双向遍历。
构造函数允许通过参数初始化数据，默认参数T()确保即使未提供初始值，也能正确构造（调用 T 的默认构造函数）。

二、迭代器（__list_iterator）的实现

迭代器是容器与算法交互的桥梁，用于遍历容器元素。list 的迭代器需要模拟指针的行为，适配双向链表的特性。

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){}// 前置++：移动到下一个节点，返回自身引用self& operator++(){_node = _node->_next;return *this;}// 前置--：移动到上一个节点，返回自身引用self& operator--(){_node = _node->_prev;return *this;}// 后置++：先记录当前状态，再移动，返回原状态self operator++(int){self tmp(*this);  // 拷贝当前迭代器_node = _node->_next;return tmp;}// 后置--：先记录当前状态，再移动，返回原状态self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}// 解引用：返回节点数据的引用（Ref适配const/非const）Ref operator*(){return _node->_data;}// ->运算符：返回节点数据的指针（Ptr适配const/非const）Ptr operator->(){return &_node->_data;}// 不等比较：判断两个迭代器是否指向不同节点bool operator!=(const self& s){return _node != s._node;}// 相等比较：判断两个迭代器是否指向同一节点bool operator==(const self& s){return _node == s._node;}
};

解析：

模板参数Ref（引用类型）和Ptr（指针类型）用于适配普通迭代器（T&、T*）和 const 迭代器（const T&、const T*），避免重复实现。
迭代器本质是对节点指针的封装，通过重载++、--实现双向移动，重载*、->实现数据访问，重载==、!=实现迭代器比较。
前置 / 后置自增 / 自减的区别：前置返回修改后的自身（效率更高），后置返回修改前的副本（需要额外拷贝）。

三、list 类的核心实现

list 类是对双向链表的封装，提供了容器的各种操作接口，内部通过 “哨兵节点”（头节点）简化边界条件处理。

3.1 类型定义与成员变量

template<class T>
class list
{typedef list_node<T> Node;  // 节点类型别名
public:// 普通迭代器：Ref为T&，Ptr为T*typedef __list_iterator<T, T&, T*> iterator;// const迭代器：Ref为const T&，Ptr为const T*typedef __list_iterator<T, const T&, const T*> const_iterator;private:Node* _head;    // 哨兵节点（头节点，不存储有效数据）size_t _size;   // 容器中有效元素的个数
};

解析：

哨兵节点_head的作用：统一链表的空状态和非空状态处理，避免操作时判断边界（如插入第一个元素或删除最后一个元素时的特殊处理）。
_size记录有效元素个数，避免每次需要大小时遍历链表（O (1) 时间复杂度）。

3.2 迭代器接口（begin/end）

// const版本：返回指向第一个元素的const迭代器
const_iterator begin() const
{return const_iterator(_head->_next);  // 第一个有效元素是_head的下一个节点
}// const版本：返回指向链表末尾的const迭代器（哨兵节点）
const_iterator end() const
{return const_iterator(_head);
}// 普通版本：返回指向第一个元素的迭代器
iterator begin()
{return _head->_next;  // 隐式转换为iterator（利用迭代器构造函数）
}// 普通版本：返回指向链表末尾的迭代器（哨兵节点）
iterator end()
{return _head;
}

解析：

begin()返回指向第一个有效元素的迭代器（_head->_next），end()返回指向哨兵节点的迭代器（作为尾后标记）。
区分普通迭代器和 const 迭代器：const 对象调用 const 版本，确保不能修改元素；非 const 对象调用普通版本，支持读写。

3.3 初始化与构造函数

// 初始化哨兵节点（空链表状态）
void empty_init()
{_head = new Node;       // 创建哨兵节点（数据为默认值，无实际意义）_head->_next = _head;   // 哨兵节点的next指向自身_head->_prev = _head;   // 哨兵节点的prev指向自身_size = 0;              // 初始元素个数为0
}// 默认构造函数
list()
{empty_init();
}// 拷贝构造函数（深拷贝）
list(const list<T>& lt)
{empty_init();  // 先初始化当前链表为空白状态// 遍历源链表，将每个元素插入到当前链表尾部for (auto e : lt){push_back(e);}
}// 交换两个list的内容
void swap(list<T>& lt)
{std::swap(_head, lt._head);  // 交换哨兵节点指针std::swap(_size, lt._size);  // 交换元素个数
}// 赋值运算符重载（现代写法：利用拷贝构造+交换）
list<T>& operator=(list<T> lt)  // 传值参数，自动拷贝一份源对象
{swap(lt);  // 交换当前对象与拷贝的临时对象return *this;  // 临时对象销毁时自动释放原数据
}// 析构函数
~list()
{clear();         // 清空所有有效元素delete _head;    // 释放哨兵节点_head = nullptr; // 避免野指针
}

解析：

empty_init()：初始化哨兵节点形成 “自环”，使空链表的操作与非空链表统一（无需额外判断_head是否为nullptr）。
拷贝构造：采用 “深拷贝”，通过遍历源链表插入元素，确保新链表与原链表独立（修改新链表不影响原链表）。
赋值运算符：利用 “值传递” 产生临时副本，再通过 swap 交换，既简化实现，又自动处理自赋值问题（临时副本与自身交换不影响）。
析构函数：先调用clear()删除所有有效节点，再删除哨兵节点，避免内存泄漏。

3.4 元素操作：插入与删除

// 在指定位置插入元素
iterator insert(iterator pos, const T& x)
{Node* cur = pos._node;    // 获取迭代器指向的节点Node* newnode = new Node(x);  // 创建新节点Node* prev = cur->_prev;  // 记录当前节点的前一个节点// 调整指针关系：prev <-> newnode <-> curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;  // 元素个数+1return iterator(newnode);  // 返回指向新节点的迭代器
}// 删除指定位置的元素
iterator erase(iterator pos)
{Node* cur = pos._node;    // 获取要删除的节点Node* prev = cur->_prev;  // 前一个节点Node* next = cur->_next;  // 后一个节点delete cur;  // 释放当前节点内存// 调整指针关系：prev <-> nextprev->_next = next;next->_prev = prev;--_size;  // 元素个数-1return iterator(next);  // 返回指向删除节点下一个位置的迭代器
}

解析：

insert：通过调整指针将新节点插入到pos之前，时间复杂度 O (1)（双向链表的优势）。
erase：删除pos指向的节点后，返回下一个节点的迭代器（原迭代器失效，需用返回值更新）。

3.5 首尾操作（push/pop）

基于insert和erase实现的便捷接口：

// 尾插：在end()位置（哨兵节点前）插入
void push_back(const T& x)
{insert(end(), x);
}// 头插：在begin()位置（第一个元素前）插入
void push_front(const T& x)
{insert(begin(), x);
}// 头删：删除begin()位置的元素
void pop_front()
{erase(begin());
}// 尾删：删除end()前一个位置的元素（--end()）
void pop_back()
{erase(--end());
}

解析：

利用已实现的insert和erase简化首尾操作，无需重复编写指针调整逻辑，体现代码复用。

3.6 清空与大小

// 清空所有有效元素（保留哨兵节点）
void clear()
{iterator it = begin();while (it != end()){it = erase(it);  // 循环删除，用返回值更新迭代器（原迭代器失效）}
}// 返回元素个数
size_t size()
{return _size;
}

解析：

clear()只删除有效元素，保留哨兵节点，使链表仍可继续使用（如需完全销毁需调用析构函数）。
size()直接返回_size，效率 O (1)（优于遍历计数的 O (n)）。

四、辅助结构与函数

用于测试 list 容器的示例结构和打印函数：

// 测试用结构体AA
struct AA
{AA(int a1 = 0, int a2 = 0):_a1(a1), _a2(a2){}int _a1;int _a2;
};// 打印容器内容的模板函数（支持所有有const迭代器的容器）
template<typename Container>
void print_container(const Container& con)
{// 注意：需要用typename声明迭代器类型（依赖模板参数）typename Container::const_iterator it = con.begin();while (it != con.end()){cout << *it << " ";++it;}cout << endl;
}

解析：