【C++ 手写 STL 容器】手撕 list 双向循环链表｜迭代器模板复用 + 反向迭代器适配器 庖丁解牛

1. 整体架构预览

STL std::list底层是带头结点双向循环链表。 难点不在于链表增删节点，而在迭代器封装：原生指针Node*不符合迭代器规范，需要封装迭代器类。

为了避免普通迭代器、const 迭代器写两份几乎完全一样的代码，我们利用模板参数Ref、Ptr实现代码复用。

反向迭代器采用适配器模式：不重新实现一套反向遍历逻辑，包装正向迭代器，复用已有所有迭代器运算符。

组件清单：

• list_node<T>：链表节点，数据 + 前驱指针 + 后继指针
• _list_iterator<T,Ref,Ptr>：正向迭代器模板，一份代码生成普通迭代器 /const 迭代器
• li::list<T>：容器本体，封装构造、析构、插入删除等接口
• reverseiterator<Iterator,Ref,Ptr>：迭代器适配器，实现反向遍历

2. list.h

#pragma once
#include<iostream>
#include<list>
#include<vector>
#include"reverse_iterator.h"
using namespace std;

namespace li
{};

2.1 链表节点：list_node

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

// 节点构造函数
list_node(const T& val = T())
:_data(val)
, _next(nullptr)
, _prev(nullptr)
{}
};

解析 有哨兵位的双向链表节点，每个节点保存数据、前驱、后继指针。 构造函数给默认参数T()，头结点就是调用这个构造，头结点不存储有效数据，仅占位，统一头尾操作逻辑。

2.2 正向迭代器 _list_iterator

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)
{}

解析：迭代器本质就是封装节点指针。 模板参数说明：

• T：存储的数据类型
• Ref：引用类型，普通迭代器传T&；const 迭代器传const T&
• Ptr：指针类型，普通迭代器传T*；const 迭代器传const T*

// 解引用重载 *it
Ref operator*()
{
return _node->_data;
}

解析：返回引用，普通迭代器可读可写，const 迭代器只读。

// ->重载 it->
Ptr operator->()
{
return &_node->_data;
}

解析：返回数据指针，支持it->member访问。

// 前置++ ++it
Self& operator++()
{
_node = _node->_next;
return *this;
}

解析：迭代器移动到下一个节点，返回自身引用，支持连续++ ++it。

// 后置++ it++
Self operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}

解析：int 只是占位参数，用来区分前置 / 后置。先保存旧迭代器，节点后移，返回旧状态。

// 前置– –it
Self& operator–()
{
_node = _node->_prev;
return *this;
}

解析：迭代器向前移动到上一个节点。

// 后置– it–
Self operator–(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}

// != 判断
bool operator!=(const Self& it)const
{
return _node != it._node;
}

// == 判断
bool operator==(const Self& it)const
{
return _node == it._node;
}
};

判断的是，两个地址是否相等

2.3 list 容器类，逐个函数拆解

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;

// 反向迭代器类型
typedef reverseiterator<iterator, T&, T*> reverse_iterator;
typedef reverseiterator<const_iterator, const T&, const T*> const_reverse_iterator;

empty_init 初始化函数

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

 作用：创建头结点，构建空双向循环链表，size 置 0。

默认构造

list()
{
empty_init();
}

解析：调用初始化函数，创建空链表。

析构函数

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

解析：先释放全部有效节点，再释放头结点，防止内存泄漏。

拷贝构造函数

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

解析：现代写法，先初始化空链表，遍历原 list 逐个尾插。

initializer_list 构造

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

解析：支持li::list<int> lt{1,2,3,4}这种花括号初始化。

swap 交换函数

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

解析：O (1) 时间复杂度，仅仅交换头结点指针和 size，不拷贝节点。

赋值重载（现代写法）

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

解析：参数传值，自动调用拷贝构造生成临时对象；swap 交换资源；函数结束临时对象销毁，带走旧内存。天然处理自赋值。

clear 清空所有有效节点

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

❌错误写法：

erase(it);
++it;

erase 之后 pos 迭代器直接失效，++it 是未定义行为。

✅正确：it = erase(it) erase 返回下一个有效迭代器。

rbegin /rend 反向迭代器接口

reverse_iterator rbegin()
{
return reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}

const_reverse_iterator rbegin()const
{
return const_reverse_iterator(end());
}
const_reverse_iterator rend()const
{
return const_reverse_iterator(begin());
}

解析：反向迭代器适配器，rbegin 包装正向 end，rend 包装正向 begin。

begin /end 正向迭代器接口

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

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

解析：

• begin ()：指向第一个有效节点
• end ()：指向头结点，尾后迭代器，不能解引用

push_back 尾插

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

解析：复用 insert，在 end 前面插入节点，就是尾插。

push_front 头插

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

pop_back 尾删

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

解析：–end()拿到最后一个有效节点迭代器，直接 erase 删除。

pop_front 头删

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

insert 插入函数

iterator insert(iterator pos, T val)
{
Node* newnode = new Node(val);
Node* pcur = pos._node;
Node* prev = pcur->_prev;

newnode->_next = pcur;
pcur->_prev = newnode;
newnode->_prev = prev;
prev->_next = newnode;

++_size;
return iterator(newnode);
}

解析：STL 规定 insert 是在 pos 迭代器前面插入节点。 四步指针链接，insert不会让任何迭代器失效。返回新节点迭代器。

erase 删除函数

iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;

prev->_next = next;
next->_prev = prev;

delete cur;
–_size;
return iterator(next);
}

解析：删除 pos 指向节点，pos 迭代器失效，其他迭代器保持有效。返回下一个节点迭代器。

size 获取元素个数

size_t size()const
{
return _size;
}
private:
Node* _head;
size_t _size = 0;
};
} //namespace li

3. reverse_iterator.h 反向迭代器适配器，逐函数拆分

设计思路：

#pragma once
template<class Iterator, class Ref, class Ptr>
struct reverseiterator
{
typedef reverseiterator<Iterator, Ref, Ptr> Self;
Iterator _it;

// 构造函数
reverseiterator(Iterator it)
:_it(it)
{}

// 解引用
Ref operator*()
{
Iterator tmp = _it;
–tmp;
return *tmp;
}

解析：底层正向迭代器是尾后迭代器，不能直接解引用，拷贝临时迭代器向前挪一位取值。

// ->重载
Ptr operator->()
{
return &(operator*());
}

// 反向迭代器 ++
Self& operator++()
{
–_it;
return *this;
}

解析：反向迭代器 ++ 等价底层正向迭代器 –。

// 反向迭代器 —
Self& operator–()
{
++_it;
return *this;
}

解析：反向迭代器 — 等价底层正向迭代器 ++。

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

核心原理：反向迭代器不维护节点指针，仅仅包装正向迭代器。 ❗面试考点：为什么拷贝 tmp，不能直接–_it？ 如果直接修改_it，会破坏反向迭代器底层保存的迭代器状态，遍历逻辑错乱。只能临时拷贝一份再自减。

4. main.cpp 测试代码

#include"list.h"
int main()
{
li::list<int> lt{ 1,2,3,4,5 };
//正向遍历
li::list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;

//反向遍历
li::list<int>::reverse_iterator rit = lt.rbegin();
while (rit != lt.rend())
{
cout << *rit << " ";
++rit;
}
cout << endl;

lt.push_back(6);
lt.push_front(0);
lt.pop_back();
lt.pop_front();
for (auto x : lt)
{
cout << x << " ";
}
return 0;
}

5、list 优缺点总结

优点：

缺点：

注意

总结

成员变量：Node* _head; 哨兵头结点

• 默认构造：创建哨兵 head，head->_next = head; head->_prev = head;（自循环）
• 析构：先 clear，再 delete _head；不能漏删哨兵节点
• clear：遍历删除所有有效节点，不要删哨兵 head
• 拷贝构造：深拷贝，新建哨兵，循环把原链表每个元素 push_back 到新 list
• 赋值重载：现代写法（swap）简单安全，注意自赋值问题