✨个人主页： 夜 默
🎉所属专栏： C++修行之路
🎊每篇一句： 图片来源

• A year from now you may wish you had started today.
  • 明年今日，你会希望此时此刻的自己已经开始行动了。

---

---

🌇前言

STL 中的 list 是一个双向带头循环链表，作为链表的终极形态，各项操作性能都很优秀，尤其是 list 中迭代器的设计更是让人拍案叫绝，如此优秀的容器究竟是如何实现的？本文将带你共同揭晓

出自书籍《STL源码剖析》 侯捷著

本文重点： 迭代器类的设计

---

🏙️正文

注意： 本文实现的只是部分基础函数，更多函数将会在后续进行更新

1、基本框架

list 由三个类构建而成：

• 节点类：每个节点必须的三部分（指向前一个节点的指针、指向后一个节点的指针、当前节点存储的数据）
• 迭代器类：此时的迭代器为双向迭代器，比较特殊，需要对其进行封装，如 it++ 并非使迭代器单纯向后移动，而是让其指向下一个节点
• 链表类：实现链表各项功能的类，为主要部分

1.1、节点类

节点类在设计时，需要确定三个成员和构造函数，用来生成类

//节点类
template<class T>
struct __list_node
{__list_node(const T& data = T()):_prev(nullptr),_next(nullptr),_data(data){}__list_node<T>* _prev;	//指向前一个节点__list_node<T>* _next;	//指向后一个节点T _data;	//存储相应数据
};

注意： 节点的创建与销毁，不在 节点类 中进行，因此不需要写析构函数

1.2、迭代器类

迭代器类中的成员为节点类指针，指向单个节点，同样的，迭代器类也需要提供构造函数

//迭代器类
template<class T>
struct __list_iterator
{typedef __list_node<T>* link_type;	//对节点类的指针，进行重命名__list_iterator(link_type node):_node(node){}link_type _node;
};

注意： 迭代器只是一个辅助工具，指向的是节点，同样不需要提供析构函数，析构相关事宜交给链表类处理就好

1.3、链表类

链表类中也只用有一个成员变量：哨兵位节点（头节点）

//list本类
template<class T>
class list
{typedef __list_node<T> node;	//节点typedef T value_type;	//模板参数值typedef T& refence;	//引用typedef const T& const_refence;	//const 引用private:node* _head;	//哨兵位节点（头节点）
};

为了避免变量名过长，这里用到了很多的 typedef

---

2、默认成员函数

默认成员函数中包含了 默认构造、带参构造、拷贝构造、赋值重载和析构函数
析构函数负责 释放链表中的节点，而其他默认成员函数负责 构造/构建出其他对象

因为有很多构造函数中都需要对创建出头节点，所以此时 需要先构建出一个空初始化函数 empty_init()，这个函数只能在类中使用，因此设为 private

private://初始化出头节点void empty_init(){_head = new node;_head->_prev = _head->_tail = _head;}

其他构造函数在构造对象前，可以先调用此函数

比如 默认构造函数， 构成出一个空对象

//默认构造函数
list() { empty_init(); }

对于带参构造函数，在构造对象前，仍需要调用 empty_init() 构建头节点
参数：

• size_t n 对象中包含 n 个数据
• const_reference val 数据值

为了避免与后续的迭代器区间构造起冲突，这里需要再额外提供一个 int n 版本

//带参构造函数(size_t)
list(size_t n, const_refence val = value_type())
{empty_init();while (n--) push_back(val);
}
//为了避免与迭代器区间构造函数冲突，提供额外版本(int)
list(int n, const_refence val = value_type())
{empty_init();while (n--) push_back(val);
}

在实际创建 list 对象时，多使用迭代器区间进行构造，因为是创建新对象，所以可以直接调用尾插进行创建

//迭代器区间构造
template<class InputIterator>
list(InputIterator first, InputIterator last)
{empty_init();while (first != last) push_back(*first++);
}

关于拷贝构造和赋值重载，可以使用现代写法【交换】

//拷贝构造---现代写法
list(const list<T>& x)
{empty_init();list<T> tmp(x.begin(), x.end());swap(tmp);
}
//赋值重载---现代写法
list<T>& operator=(list<T> tmp)
{swap(tmp);return *this;
}

注意：

• 以上几种构造函数都是在创建新对象，因此在构建前，需要先调用 empty_init() 初始化出头节点
• 为了避免 list(int, int) 匹配上迭代器区间构造，可以再额外提供一个 int 版的带参构造函数
• 拷贝构造的参数必须使用引用，否则会造成 无穷递归 问题

至于 析构函数 的实现就很简单了，直接使用函数 clear() 释放节点，最后再释放头节点即可

//析构函数
~list()
{clear();	//后续会对这个函数的实现进行讲解delete _head;_head = nullptr;
}

对上述函数进行使用

---

3、迭代器设计

迭代器设计是本文的重难点

它是一个单独存在的类

//迭代器类
template<class T, class Ref, class Ptr>
struct __list_iterator
{typedef __list_node<T>* link_type;typedef __list_iterator<T, Ref, Ptr> self;__list_iterator(link_type node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &(operator*());}self& operator++(){_node = _node->_next;return *this;}self& operator--(){_node = _node->_prev;return *this;}self operator++(int){self tmp(_node);//++_node;	//谨防错误写法//_node = _node->_next;	//正确写法1++(*this);	//正确写法2return tmp;}self operator--(int){self tmp(_node);//--_node;	//谨防错误写法//_node = _node->_prev;	//正确写法1--(*this);	//正确写法2return tmp;}bool operator==(const self& tar){return tar._node == _node;}bool operator!=(const self& tar){return tar._node != _node;}link_type _node;
};

注意： 节点类及迭代器类都是使用 struct 定义的，目的是为了开放其中的成员

list 类中的迭代器相关函数也有两种：普通版本与 const 版本

规定：

• begin() 为 list 的头节点的下一个节点
• end() 是 list 的头节点
• 返回类型都为迭代器对象，因此可以使用匿名对象进行构造

//=====迭代器设计=====
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;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); }

3.1、双向迭代器

list 中的迭代器只支持双向操作，在进行随机移动时会报错
以下是 std::list 中对迭代器进行随机移动的情况

void TestStdList()
{std::list<int> slt = { 1, 2, 3 };std::list<int>::iterator it = slt.begin();it++;	//单向移动，支持it--;	//双向移动，支持it + 10;	//随机移动，不支持
}

虽然我们可以通过某些手段实现随机移动（比如 operator+(int n)），但为了更好的符合链表及标准库规定，这里设计为双向移动的迭代器即可

迭代器分类：

• 单向迭代器：支持 ++ 或 -- 其中一种移动方式
• 双向迭代器：支持 ++ 及 -- 两种移动方式
• 随机迭代器：不仅支持 ++ 和 --，还支持迭代器 +n、-n，只有随机迭代器才能使用 std::sort 进行快速排序

目标：实现前置 ++/-- 及后置 ++/--

self& operator++();	//前置++self& operator--();	//前置--self operator++(int);	//后置++self operator--(int);	//后置--

注：具体代码实现在上面

3.2、特殊移动策略

list 中的双向迭代器在进行移动时也比较特殊，不像之前的 string 和 vector 是连续空间（移动直接调用内置 ++/--）， list 为非连续空间，迭代器在移动时为前后节点间的移动，使用内置 ++/-- 会引发严重的迭代器越界问题

因此才需要将迭代器单独封装为一个类，实现我们想要的效果

如何实现不同区域间节点的移动？

• 首先需要先构建出迭代器对象
• 当使用前置 ++ 时，会去调用迭代器类中的 operator++() 重载函数，将迭代器指向当前节点的下一个节点（_node = _node->_next）
• 使用后置 -- 时也是如此，调用 operator--() 即可（_node = _node->_prev）
• 至于后置 ++/--，可以先构造出当前节点的迭代器对象，再复用前置 ++/-- 即可

self& operator++()
{_node = _node->_next;return *this;
}self& operator--()
{_node = _node->_prev;return *this;
}self operator++(int)
{self tmp(_node);//++_node;	//谨防错误写法//_node = _node->_next;	//正确写法1++(*this);	//正确写法2return tmp;
}self operator--(int)
{self tmp(_node);//--_node;	//谨防错误写法//_node = _node->_prev;	//正确写法1--(*this);	//正确写法2return tmp;
}

注意： _node 是迭代器中的节点指针，包含在迭代器对象中

在这里分享一个我在模拟迭代器类时遇到的小问题：根据一个 list 对象构造出另一个 list 对象，调用后置 ++/-- 并解引用后，出现内存问题（越界访问）

原因分析：调用后置 ++ 后，因 operator++(int) 编写不当，导致当前节点指针没有正确指向下一个节点，而是指向当前位置的下一块空间（非法空间），导致迭代器失联，引发后续的越界访问

//以下是后置++的错误写法
self operator++(int)
{self tmp(_node);++_node;	//错误写法return tmp;
}

根本原因：_node 是一个节点指针，非迭代器对象，++_node 不是在调用 operator++()，而是在调用内置的前置 ++ （节点指针没有像迭代器一样进行重载），直接 ++ 就指向了非法空间

解决方案：

1. 手动实现节点的移动：_node = _node->_next
2. 调用迭代器类的前置 ++：++(*this)

两种解决方法都可以，推荐使用第二种（库中的解决方案）

self operator++(int)
{self tmp(_node);//++_node;	//谨防错误写法//_node = _node->_next;	//正确写法1++(*this);	//正确写法2return tmp;
}

补充：假设构造对象为内置的数组或其他库中的容器，++_node 不会出错，因为此时会调用正确的移动方法；而当构造对象为自己模拟实现的 list 时，会出现上述的报错问题

3.3、多参数模板

list 的模拟实现精华在于迭代器类的设计，而迭代器类中的精华在于多参数模板，这种传多模板参数的方法，巧妙的解决了 正常对象 与 const 对象的冗余设计问题

迭代器分为 iterator 和 const_iterator，不同的对象调用不同的迭代器类型，假设不使用多参数模板，就需要实现两份相差不大的迭代器类（完全没有必要）

优雅、巧妙的解决方案 多参数模板

• T：节点中值的普通类型
• Ref：节点中值的引用类型(可为 const)
• Ptr：节点中值的指针类型(可为 const)

//迭代器类
template<class T, class Ref, class Ptr>
struct __list_iterator
{typedef __list_node<T>* link_type;typedef __list_iterator<T, Ref, Ptr> self;//……link_type _node;
};//=====迭代器设计=====（list 类中）
typedef __list_iterator<T, T&, T*> iterator;	//声明两种不同的迭代器
typedef __list_iterator<T, const T&, const T*> const_iterator;

迭代器类中的模板参数是一对二的

多参数模板的使用，使得 list 的迭代器设计更加优雅，下面是实际使用演示（在 operator*() 中添加信息区分）

Ref operator*()
{cout << "当前的模板参数为: " << typeid(*this).name() << endl;return _node->_data;
}

void TestList()
{int arr[] = { 1,2,3,4,5 };list<int> lt(arr, arr + sizeof(arr) / sizeof(arr[0]));	//普通对象const list<int> rlt(arr, arr + sizeof(arr) / sizeof(arr[0]));	//const 对象auto it = lt.begin();auto rit = rlt.begin();cout << *it << endl;cout << *++rit << endl;
}

使用不同的迭代器类型，可以使迭代器类中的模板参数变为对应类型
这正是 泛型编程 思想之一

3.4、其他功能

关于迭代器类中的其他功能：

• 解引用 operator*()
• 取当前节点指针 operator->()
• 迭代器比较 operator==() 和 operator!=()

详细实现代码可以查看本文的 章节3 开头

这里简单说一下 operator->()

适用场景：当 list 中的对象为自定义类型时，想直接通过 it-> 访问其中的成员

struct A
{A(int a = int(), double b = double(), char c = char()):_a(a),_b(b),_c(c){}int _a;double _b;char _c;
};void TestList()
{list<A> lt;lt.push_back(A(1, 2.2, 'A'));auto it = lt.begin();cout << (*it)._a << endl;	//不使用 operator->() 比较别扭cout << it.operator->()->_b << endl;	//这种写法是真实调用情况cout << it->_c << endl;	//编译器直接优化为 it->
}

operator->() 存在的意义：使得 迭代器 访问自定义类型中的成员时更加方便
如果没有这个函数，只能通过 (*迭代器).成员 的方式进行成员访问，很不方便

注意： 编译器将 迭代器.operator->()->成员 直接优化为 迭代器->成员

---

4、容量相关

list 中的容量访问有：判空和大小

实现判空：判断当前的 begin() 与 end() 是否相同
统计大小：利用迭代器将整个 list 遍历一遍，计数统计即可

//=====容量相关=====
bool empty() const { return begin() == end(); }
size_t size() const 
{int cnt = 0;auto it = begin();	//使用 auto 自动推导迭代器类型while (it != end())++it, ++cnt;return cnt;
}

---

5、数据访问

STL 库中给 list 提供了两种数据访问方式：访问首个数据和访问最后一个数据

//=====数据访问=====
refence front() { return *begin(); }
const_refence front() const { return *begin(); }refence back() { return *(--end()); }
const_refence back() const { return *(--end()); }

---

6、数据修改相关

数据修改是 list 的拿手好戏（双向循环链表），只需要找到对应节点的位置，插入/删除 本质上就是在进行前后节点的链接关系修改

出自《STL源码剖析》

6.1、头尾插删

头尾插删是在对 begin() 和 --end() 所指向的节点进行操作，尾部插入/头部删除 逻辑一致，尾部删除/头部删除 逻辑一致，学会其中一个就够用了

尾部插入步骤：

• 根据传入的数值，构建出新尾节点 new_back
• 找到原链表中的尾节点 old_back
• 在 old_back、new_back、_head 间建立链接关系即可
• 头部插入逻辑与尾部插入基本一致，不过找的是 old_front 头节点

//尾插
void push_back(const_refence val)
{node* new_back = new node(val);node* old_back = _head->_prev;old_back->_next = new_back;	//原尾节点的 _next 指向新尾节点new_back->_prev = old_back;	//新尾节点的 _prev 指向原尾节点new_back->_next = _head;	//新尾节点的 _next 指向头节点_head->_prev = new_back;	//头节点的 _prev 指向新尾节点
}

尾部删除步骤：

• 断言当前 list 不为空，如果为空，就报错
• 选择原来的尾节点 old_back->_head->_prev
• 确定新的尾节点 new_back->old_back->prev
• 在 new_back 与 _head 之间建立链接关系
• 最后在释放原来的尾节点 old_back
• 头删时，逻辑基本一致，不过选择的是 old_front 与 new_front

//尾删
void pop_back()
{assert(!empty());node* old_back = _head->_prev;	//选择原尾节点node* new_back = old_back->_prev;	//确定新尾节点new_back->_next = _head;	//新尾节点的 _next 指向头节点_head->_prev = new_back;	//头节点的 _prev 指向新尾节点delete old_back;
}

类似于 push_back() 还有一个函数 assign() 分配，相当于构造函数构造出对象，不过此时是赋值的方式

//=====数据修改=====
//赋值
void assign(size_t n, const_refence val = value_type())
{clear();while (n--) push_back(val);
}
void assign(int n, const_refence val = value_type())
{assign((size_t)n, val);
}
template<class InputIterator>
void assign(InputIterator first, InputIterator last)
{list<T> tmp(first, last);swap(tmp);
}

注意：

• 为了避免 assign(int, int) 与 assign(first, last) 起冲突，需要再额外提供一个 assign(int n, const_refence val) 版本
• assign 行为类似于创建出一个新的对象，因此在赋值(分配)前需要先清空 clear()
• assign 本质上是在调用 push_back

6.2、任意位置插删

任意位置插入就是在插入操作的基础上添加了迭代器 pos 进行定位

• 约定：在 pos 位置前插入
• 根据传入值，创建出新节点 new_node
• 确定当前 pos 位置的节点 pos_cur
• 确定当前 pos 位置的上一个节点 pos_prev
• 在 pos_prev、new_node、pos_cur 间建立链接关系
• 最后返回当前插入新节点的位置

//任意位置插入
iterator insert(iterator pos, const_refence val = value_type())
{node* new_node = new node(val);	//创建新节点node* pos_cur = pos._node;	//当前 pos 位置的节点node* pos_prev = pos_cur->_prev;	//pos 的前一个节点pos_prev->_next = new_node;	new_node->_prev = pos_prev;new_node->_next = pos_cur;pos_cur->_prev = new_node;return iterator(new_node);	//最后返回的是一个迭代器对象
}

任意位置删除逻辑与 尾删/头删 基本一致

• 首先断言 list 是否为空
• 分别确定当前节点 pos_cur，上一个节点 pos_prev，下一个节点 pos_next
• 在上下节点 pos_prev 和 pos_next 间建立链接关系
• 删除当前节点 pos_cur
• 返回已删除节点下一个节点，即 pos_next

//任意位置删除
iterator erase(iterator pos)
{assert(!empty());node* pos_cur = pos._node;node* pos_prev = pos_cur->_prev;node* pos_next = pos_cur->_next;pos_prev->_next = pos_next;pos_next->_prev = pos_prev;delete pos_cur;return iterator(pos_next);
}

注意： list 的插入操作没有迭代器失效问题，删除操作也仅仅是影响被删除节点的迭代器，返回值是为了更好的进行操作

之前提到的 尾部插入/删除、头部插入/删除 可以复用 任意位置插入/删除

//尾插
void push_back(const_refence val)
{insert(end(), val);
}//尾删
void pop_back()
{erase(--end());
}//头插
void push_front(const_refence val)
{insert(begin(), val);
}//头删
void pop_front()
{erase(begin());
}

复用后，之前的代码也能正常运行

6.3、交换、调整、清理

接下来是一些比较简单函数实现

• 交换 swap：不同于 std::swap，list::swap 是直接交换两个链表的头节点，效率是极高的
• 调整 resize：传入 n 及值 val，对 list 进行大小调整，只有 n > size() 才进行大小调整，具体调整就是 push_back() 尾插 n - size() 次
• 清理 clear：通过迭代器对 list 进行遍历， erase 除头节点外的所有节点

//交换
void swap(list<T>& tmp)
{std::swap(_head, tmp._head);
}//大小调整
void resize(size_t n, const_refence val = value_type())
{if (n > size()){while (size() < n)push_back(val);}
}//清理
void clear()
{iterator it = begin();while (it != end())it = erase(it);
}

简单写一个小 demo 测试一下这些函数

void Print(list<int>& lt1, list<int>& lt2)
{cout << "lt1：" << "empty()：" << lt1.empty() << "   size()：" << lt1.size() << endl;for (auto e : lt1)cout << e << " ";cout << endl;cout << "lt2：" << "empty()：" << lt2.empty() << "   size()：" << lt2.size() << endl;for (auto e : lt2)cout << e << " ";cout << endl;cout << "============================" << endl;
}void TestList()
{int arr[] = { 1,2,3,4,5 };list<int> lt1(arr, arr + sizeof(arr) / sizeof(arr[0]));list<int> lt2(3, 1);cout << "original" << endl;Print(lt1, lt2);cout << "swap(lt1, lt2)" << endl;lt1.swap(lt2);Print(lt1, lt2);cout << "lt1 resize()" << endl;lt1.resize(10, 2);Print(lt1, lt2);cout << "clear()" << endl;lt1.clear();lt2.clear();Print(lt1, lt2);
}

---

7、源码

关于本文中涉及到的所有代码都在这个仓库中 《list_4_8》

---

🌆总结

以上就是本次关于 STL 学习之 list 的模拟实现的全部内容了，对于本文来说，最核心的内容莫过于迭代器类的设计，而其中的精华在于多参数模板的使用，只要把迭代器类设计好了，list 中的其他部分都不成问题

如果你觉得本文写的还不错的话，可以留下一个小小的赞👍，你的支持是我分享的最大动力！

如果本文有不足或错误的地方，随时欢迎指出，我会在第一时间改正

---

相关文章推荐
STL 之 list 类

C++ STL学习之【list的使用】

===============

STL 之 vector 类

C++ STL学习之【vector的模拟实现】

C++ STL学习之【vector的使用】

===============

STL 之 string 类

C++ STL学习之【string类的模拟实现】

C++ STL 学习之【string】