list
前言
在C++ STL中，list是一个非常常用的容器，它基于双向循环链表实现，具有高效的插入和删除操作。本文将详细介绍如何模拟实现一个简易版的STL list容器，包括节点结构、迭代器设计以及list类的核心功能实现。
一、list的节点结构设计
list的底层是双向循环链表，因此首先需要设计链表的节点结构。每个节点应包含数据域和两个指针域（前驱和后继）：
template<class T>
struct ListNode
{
typedef ListNode<T> Node;
ListNode(const T& val = T());
~ListNode();
Node* _next; // 指向后继节点
Node* _prev; // 指向前驱节点
T _val; // 节点存储的数据
};
template<class T>
ListNode<T>::ListNode(const T& val)
:_next(nullptr)
, _prev(nullptr)
, _val(val)
{}
template<class T>
ListNode<T>::~ListNode()
{
_next = nullptr;
_prev = nullptr;
_val = T();
}
二、迭代器设计
list的迭代器与vector不同，它不能是简单的指针，因为list的节点在内存中不是连续存储的。我们需要设计一个迭代器类，通过重载运算符来模拟指针的行为。
template<class T, class value_type>
struct ListIterator
{
typedef ListNode<T> Node;
Node* _node; // 指向当前节点
ListIterator(Node* node = nullptr);
// 重载各种运算符
ListIterator<T, value_type>& operator=(const ListIterator<T, value_type>& it);
ListIterator<T, value_type>& operator++(); // 前置++
ListIterator<T, value_type> operator++(int); // 后置++
ListIterator<T, value_type>& operator--(); // 前置--
ListIterator<T, value_type> operator--(int); // 后置--
value_type& operator*(); // 解引用
value_type* operator->(); // 箭头运算符
bool operator==(const ListIterator<T, value_type>& it);
bool operator!=(const ListIterator<T, value_type>& it);
};
迭代器的核心运算符实现：
// 前置++
template<class T, class value_type>
ListIterator<T, value_type>& ListIterator<T, value_type>::operator++()
{
_node = _node->_next;
return *this;
}
// 后置++
template<class T, class value_type>
ListIterator<T, value_type> ListIterator<T, value_type>::operator++(int)
{
ListIterator<T, value_type> tmp = *this;
_node = _node->_next;
return tmp;
}
// 解引用运算符
template<class T, class value_type>
value_type& ListIterator<T, value_type>::operator*()
{
return _node->_val;
}
// 箭头运算符
template<class T, class value_type>
value_type* ListIterator<T, value_type>::operator->()
{
return &(_node->_val);
}
三、list类的实现
list类需要维护一个双向循环链表，我们使用一个头节点（哨兵节点）来简化边界条件的处理。
3.1 类的成员变量和类型定义
template<class T>
class list
{
public:
typedef ListNode<T> Node;
// 定义迭代器类型，普通迭代器和const迭代器
typedef ListIterator<T, T> iterator;
typedef ListIterator<T, const T> const_iterator;
// ... 成员函数声明
private:
Node* _head; // 头节点（哨兵节点）
};
3.2 构造函数与析构函数
// 默认构造函数
template<class T>
list<T>::list()
{
_head = new Node;
_head->_next = _head; // 循环指向自身
_head->_prev = _head;
}
// 范围构造函数
template<class T>
template <class InputIterator>
list<T>::list(InputIterator first, InputIterator last)
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
while (first != last)
{
push_back(*first);
first++;
}
}
// 析构函数
template<class T>
list<T>::~list()
{
Node* cur = _head->_next;
while (cur != _head)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
delete _head;
_head = nullptr;
}
3.3 元素访问与迭代器接口
// 迭代器接口
template<class T>
typename list<T>::iterator list<T>::begin()
{
return iterator(_head->_next); // 第一个元素是头节点的下一个
}
template<class T>
typename list<T>::iterator list<T>::end()
{
return iterator(_head); // 尾后迭代器指向头节点
}
// 元素访问
template<class T>
T& list<T>::front()
{
assert(!empty());
return _head->_next->_val; // 第一个元素
}
template<class T>
T& list<T>::back()
{
assert(!empty());
return _head->_prev->_val; // 最后一个元素
}
3.4 插入与删除操作
list的插入和删除操作是其核心优势，时间复杂度为O(1)：
// 头插
template<class T>
void list<T>::push_front(const T& val)
{
Node* new_node = new Node(val);
// 插入到头节点和第一个元素之间
new_node->_prev = _head;
new_node->_next = _head->_next;
_head->_next->_prev = new_node;
_head->_next = new_node;
}
// 尾插
template<class T>
void list<T>::push_back(const T& val)
{
Node* new_node = new Node(val);
// 插入到最后一个元素和头节点之间
new_node->_prev = _head->_prev;
new_node->_next = _head;
_head->_prev->_next = new_node;
_head->_prev = new_node;
}
// 指定位置插入
template<class T>
typename list<T>::iterator list<T>::insert(iterator position, const T& val)
{
Node* new_node = new Node(val);
// 插入到position之前
new_node->_prev = position._node->_prev;
new_node->_next = position._node;
position._node->_prev->_next = new_node;
position._node->_prev = new_node;
return iterator(new_node); // 返回指向新节点的迭代器
}
// 指定位置删除
template<class T>
typename list<T>::iterator list<T>::erase(iterator position)
{
// 调整前后节点的指针关系
position._node->_prev->_next = position._node->_next;
position._node->_next->_prev = position._node->_prev;
iterator ret = position._node->_next; // 记录下一个位置
delete position._node; // 释放节点内存
return ret; // 返回下一个位置的迭代器
}
3.5 其他常用操作
// 清空链表
template<class T>
void list<T>::clear()
{
Node* cur = _head->_next;
while (cur != _head)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
// 恢复头节点的循环指向
_head->_prev = _head;
_head->_next = _head;
}
// 反转链表
template<class T>
void list<T>::reverse()
{
Node* cur = _head->_next;
while (cur != _head)
{
Node* tmp = cur->_next;
std::swap(cur->_prev, cur->_next); // 交换前后指针
cur = tmp;
}
// 交换头节点的前后指针
std::swap(_head->_prev, _head->_next);
}
// 移除所有值为val的元素
template<class T>
void list<T>::remove(const T& val)
{
iterator cur = begin();
while (cur != end())
{
if (*cur == val)
{
cur = erase(cur); // 删除后自动移动到下一个元素
}
else
{
++cur;
}
}
}
四、总结
本文实现了一个简易版的STL list容器，包含了list的核心功能：
- 基于双向循环链表，使用哨兵节点简化边界处理
- 实现了功能完善的迭代器，支持++、–、*、->等操作
- 提供了插入、删除、反转、移除等常用操作
与vector相比，list的优势在于插入和删除操作的高效性（O(1)时间复杂度），但随机访问性能较差（O(n)时间复杂度）。在实际开发中，应根据具体需求选择合适的容器。
完整代码实现了更多细节，如拷贝构造、赋值运算、区间插入、splice操作等，感兴趣的读者可以参考代码进行深入学习。
如需源码，可在我的gitee上找到，下面是链接：
list
如对您有所帮助，可以来个三连，感谢大家的支持。
每文推荐
陈粒–小半
范玮琪、张韶涵–如果的事
孙燕姿–克卜勒
学技术学累了时可以听歌放松一下。