C++STL--list底层实现，迭代器分类，模拟list的迭代器封装、实现

博主名称：deM0one

⭐️C++专栏：
C++

文章目录

• C++ STL list 容器底层原理：从零实现一个类 STL 的 list
• • 一、引言
  • 二、迭代器类型与性能特性
  • • 2.1 迭代器类型
    • 2.2 性能特点
    • 2.3 支持双向迭代器的容器
  • 三、vector 的成员类型详解
  • 四、迭代器分类体系
  • 五、list 的内部结构设计
  • • 5.1 循环双向链表 + 哨兵节点
    • 5.2 push_back 实现
  • 六、迭代器的封装与实现
  • • 6.1 普通人的写法（不封装迭代器）
    • 6.2 仿 STL 的迭代器封装
  • 七、总结
  • 附录：参考资料

C++ STL list 容器底层原理：从零实现一个类 STL 的 list

一、引言

• C++ STL（Standard Template Library）是 C++ 标准库的核心组件
• list 作为双向链表容器，与 vector 等顺序容器有本质区别
• 本文将从迭代器类型、内部结构、关键操作实现、迭代器封装四个维度，深度解析 list 的工作原理

二、迭代器类型与性能特性

2.1 迭代器类型

2.2 性能特点

• 支持双向遍历：可通过 ++ 和 — 操作前后移动
• 不支持随机访问：无 operator[]，不能通过下标直接访问元素
• 时间复杂度：
  • 插入/删除：O(1)（已知位置）
  • 查找：O(n)

2.3 支持双向迭代器的容器

• list、map、multimap
• set、multiset
• vector、string、deque（这些支持随机访问迭代器）

注意：STL 从 C++98 起就支持上述迭代器类型。

三、vector 的成员类型详解

以 std::vector<T, Alloc> 为例，其成员类型定义如下：

关键点：vector 的迭代器是随机访问迭代器，而 list 的迭代器仅为双向迭代器。

四、迭代器分类体系

Input ← Output ← Forward ← Bidirectional ← Random Access

五、list 的内部结构设计

5.1 循环双向链表 + 哨兵节点

list 内部采用循环双向链表结构，并设置一个**哨兵节点（sentinel）**作为头节点。

protected:
link_type node; // 哨兵节点指针

public:
list() { empty_initialize(); }

void empty_initialize() {
node = get_node(); // 分配哨兵节点
node->next = node; // 自循环
node->prev = node;
}

设计意义：哨兵节点简化了边界处理，使得空链表和非空链表的处理逻辑保持一致。

5.2 push_back 实现

void push_back(const T& x) {
Node* newnode = new Node(x);
Node* tail = _head->prev; // 当前尾节点
tail->next = newnode; // 原尾部指向新节点
newnode->prev = tail; // 新节点指回原尾部
newnode->next = _head; // 新节点指向哨兵
_head->prev = newnode; // 哨兵指回新节点
}

插入过程图示：

tail newnode
↓ ↓
[head] ←── 1 ←── 2 ←── 3 ←── 4
↑ ↑
head newnode

• 在链表尾部插入新节点 newnode
• 更新原尾节点 tail 的 next 指向新节点
• 新节点的 prev 指回 tail
• 新节点的 next 指向 head
• head 的 prev 指向新节点 → 形成闭环

六、迭代器的封装与实现

6.1 普通人的写法（不封装迭代器）

typedef list_iterator<T> iterator;

iterator begin() {
iterator it(_head->next);
return iterator(_head->next);
}

iterator end() {
return _head; // 返回哨兵节点
}

问题：直接暴露底层节点指针，缺乏封装，不符合 STL 规范。

6.2 仿 STL 的迭代器封装

template<class T>
struct list_iterator {
typedef list_node<T> Node;
typedef list_iterator<T> Self;
Node* _node;

list_iterator(Node* node) : _node(node) {}

// 解引用操作
T& operator*() {
return _node->_data;
}

// 前置递增
Self& operator++() {
_node = _node->next;
return *this;
}

// 不等比较
bool operator!=(const Self& s) {
return _node != s._node;
}
};

迭代器遍历图示：

pos
↓
[head] ←── 1 ←── 2 ←── 3 ←── 4
↑
head

• 使用迭代器封装底层节点指针
• 提供 operator*、operator++、operator!= 等基本操作
• 符合 STL 迭代器协议，便于与泛型算法（如 sort、find）配合使用

七、总结

本文系统梳理了 C++ STL list 容器的核心设计：

掌握这些原理，有助于深入理解 STL 设计思想，并为手写简易版容器打下坚实基础。

附录：参考资料

• 《C++ Primer》第 10 章：泛型算法与容器
• SGI STL 源码剖析
• cppreference.com：std::list

任何的批评和建议欢迎指出，我们共同进步！