跳到主要内容
STL list 容器模拟实现与核心原理 | 极客日志
C++ 算法
STL list 容器模拟实现与核心原理 综述由AI生成 详细解析了 C++ STL list 容器的底层实现原理。内容涵盖节点结构定义、带头双向循环链表的设计、迭代器的封装与运算符重载、以及常用成员函数的实现逻辑(如构造、插入、删除、赋值等)。文章提供了完整的 list.h 头文件和测试代码,帮助开发者深入理解 list 容器的内存管理与遍历机制。
指针猎手 发布于 2026/3/24 更新于 2026/5/3 7K 浏览一、STL 源码
定义节点
迭代器
list 定义
成员函数
初始化
从内存池中获取空间
创建节点
定位 new 初始化
销毁节点
二、模拟实现 list 容器
1. list 成员变量
template <class T >
struct list_node {
list_node<T>* _prev;
list_node<T>* _next;
T val;
list_node (const T& x = T ()) : _prev(nullptr ), _next(nullptr ), val (x) {}
};
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;
private :
Node* _head;
size_t _size;
};
2. 构造函数
void empty_init () {
_head = Node;
_head->_prev = _head;
_head->_next = _head;
_size = ;
}
() { (); }
new
0
list
empty_init
list 是一个带头的双向循环链表,因此,构造时创建一个带头的节点 。
3. insert void insert (const iterator& pos, const T& x) {
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node (x);
newnode->_prev = prev;
prev->_next = newnode;
newnode->_next = cur;
cur->_prev = newnode;
++_size;
}
list 容器 与数据结构中带头双向循环链表的原理是一样的,只不过进行了封装而已 。看不懂细节的,可以移步相关数据结构文章。list 容器,重点讲解迭代器部分 。
4. 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;
++_size;
}
其实,push_back就是尾插,可以复用 insert 函数。这样去实现。
void push_back (const T& x) {
insert (end (), x);
}
这样是不是简单多了,end返回的就是 list 容器中的末尾后的一个位置(即头结点),而插入节点是在该位置之前插入的。
5. 拷贝构造
list (list<T>& lt) {
empty_init ();
for (const auto & e : lt) {
push_back (e);
}
}
拷贝构造也需要先初始化 list 对象,在调用 push_back 逐个插入元素。
6. 初始化列表构造 list (initializer_list<T> lt) {
empty_init ();
for (const auto & e : lt) {
push_back (e);
}
}
7. operator= 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 ;
}
通过拷贝构造出一个局部对象,在进行资源的交换就完成赋值重载了。
8. erase iterator erase (iterator pos) {
assert (pos != end ());
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
--_size;
return iterator (next);
}
9. pop_back, push_front, pop_front void pop_back () {
erase (--end ());
}
void push_front (const T& x) {
insert (begin (), x);
}
void pop_front () {
erase (begin ());
}
10. clear void clear () {
iterator it = begin ();
while (it != end ()) {
it = erase (it);
}
}
清空 list 中的所有元素,从 list 中的 begin 位置的节点开始删除。
11. 析构函数 ~list () {
clear ();
delete _head;
_head = nullptr ;
_size = 0 ;
}
清空 list 容器中的所有节点,再删除头结点,更新_size。
12. size size_t size () const {
return _size;
}
13. 迭代器 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);
}
以前使用库里面的迭代器,都是直接获取迭代器,该迭代器指向某个元素的这块空间,通过解引用就可以访问到该元素 。那么,在 list 这里,可以直接用原生指针 Node*(list_node<T>*)作为迭代器吗?答案是不可以的 。
**因为如果用原生指针 Node*(内置类型) 作为迭代器,那么解引用能访问到元素,但是使用迭代器的方式就会与平时不一样,需要手动访问数据,而且原生指针是一个内置类型,要如何通过++操作访问下一个节点呢**?基于以上原因,因此,不能用原生指针作为迭代器。
我们可以对原生指针进行封装,使之成为一个自定义类型 ,这样不就可以通过解引用操作,调用运算符重载函数了,访问到数据了吗!其次,自定义类型在++操作的时候,也可以通过运算符重载指向下一个 Node 节点。
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) {}
Ref operator *() {
return _node->val;
}
Ptr operator ->() {
return &_node->val;
}
Self& operator ++() {
_node = _node->_next;
return *this ;
}
Self operator ++(int ) {
list_iterator<T> tmp (*this ) ;
_node = _node->_next;
return tmp;
}
Self& operator --() {
_node = _node->_prev;
return *this ;
}
Self operator --(int ) {
list_iterator<T> tmp (*this ) ;
_node = _node->_prev;
return tmp;
}
bool operator !=(const Self& it) {
return _node != it._node;
}
bool operator ==(const Self& it) {
return _node == it._node;
}
};
可以看到,这里不仅有模板参数 T,还多了两个模板参数 Ref 和 Ptr。实现迭代器的时候,不仅实现了普通迭代器,还实现了 const 版本的迭代器,如果不增加这两个模板参数,我们就还需要写一个类来封装 Node*指针 ,而且,这两个类的代码基本是一样的,在返回值,参数类型上会有所区别,代码会非常的冗余 。所以,添加两个模板参数就可以很好的解决这个问题了。
三、完整代码实现
list.h #pragma once
#include <iostream>
#include <assert.h>
using namespace std;
namespace LC {
template <class T >
struct list_node {
list_node<T>* _prev;
list_node<T>* _next;
T val;
list_node (const T& x = T ()) : _prev(nullptr ), _next(nullptr ), val (x) {}
};
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) {}
Ref operator *() { return _node->val; }
Ptr operator ->() { return &_node->val; }
Self& operator ++() { _node = _node->_next; return *this ; }
Self operator ++(int ) {
list_iterator<T> tmp (*this ) ;
_node = _node->_next;
return tmp;
}
Self& operator --() { _node = _node->_prev; return *this ; }
Self operator --(int ) {
list_iterator<T> tmp (*this ) ;
_node = _node->_prev;
return tmp;
}
bool operator !=(const Self& it) { return _node != it._node; }
bool operator ==(const Self& it) { return _node == it._node; }
};
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;
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);
}
void empty_init () {
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
_size = 0 ;
}
list () { empty_init (); }
list (list<T>& lt) {
empty_init ();
for (const auto & e : lt) {
push_back (e);
}
}
list (initializer_list<T> lt) {
empty_init ();
for (const auto & e : lt) {
push_back (e);
}
}
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 ;
}
size_t size () const { return _size; }
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;
++_size;
}
void insert (const iterator& pos, const T& x) {
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node (x);
newnode->_prev = prev;
prev->_next = newnode;
newnode->_next = cur;
cur->_prev = newnode;
++_size;
}
iterator erase (iterator pos) {
assert (pos != end ());
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
--_size;
return iterator (next);
}
void pop_back () {
erase (--end ());
}
void push_front (const T& x) {
insert (begin (), x);
}
void pop_front () {
erase (begin ());
}
void clear () {
iterator it = begin ();
while (it != end ()) {
it = erase (it);
}
}
~list () {
clear ();
delete _head;
_head = nullptr ;
_size = 0 ;
}
private :
Node* _head;
size_t _size;
};
}
test.cc #define _CRT_SECURE_NO_WARNINGS
#include "list.h"
struct A {
int _a1;
int _a2;
A (int a1 = 1 , int a2 = 2 ) : _a1(a1), _a2(a2) {}
};
void testlist1 () {
LC::list<int > l1;
l1. push_back (1 );
l1. push_back (2 );
l1. push_back (3 );
l1. push_back (4 );
LC::list<int >::iterator it = l1. begin ();
while (it != l1. end ()) {
cout << *it << " " ;
++it;
}
cout << endl;
l1. insert (l1. begin (), 5 );
l1. insert (l1. end (), 6 );
it = l1. begin ();
while (it != l1. end ()) {
cout << *it << " " ;
++it;
}
cout << endl;
l1. erase (l1. begin ());
it = l1. begin ();
while (it != l1. end ()) {
cout << *it << " " ;
++it;
}
cout << endl;
}
void testlist2 () {
LC::list<int > l1;
l1. push_back (1 );
l1. push_back (2 );
l1. push_back (3 );
l1. push_back (4 );
LC::list<int > l2 (l1) ;
LC::list<int >::iterator it = l2. begin ();
while (it != l2. end ()) {
cout << *it << " " ;
++it;
}
cout << endl;
cout << l2. size () << endl;
LC::list<int > l3;
l3. push_back (10 );
l3. push_back (20 );
l3. push_back (30 );
l3. push_back (40 );
l3. push_back (50 );
l2 = l3;
LC::list<int >::iterator it1 = l2. begin ();
while (it1 != l2. end ()) {
cout << *it1 << " " ;
++it1;
}
cout << endl;
cout << l2. size () << endl;
LC::list<double > l4 = { 1.1 , 2.2 , 3.3 , 4.4 };
LC::list<double >::iterator it2 = l4. begin ();
while (it2 != l4. end ()) {
cout << *it2 << " " ;
++it2;
}
cout << endl;
cout << l4. size () << endl;
LC::list<A> l5;
l5. push_back ({ 1 , 1 });
l5. push_back ({ 2 , 2 });
l5. push_back ({ 3 , 3 });
l5. push_back ({ 4 , 4 });
LC::list<A>::iterator it3 = l5. begin ();
while (it3 != l5. end ()) {
cout << it3->_a1 << " " << it3->_a2 << endl;
++it3;
}
cout << endl;
cout << l5. size () << endl;
}
int main () {
testlist2 ();
return 0 ;
}
相关免费在线工具 加密/解密文本 使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
Gemini 图片去水印 基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印,支持批量处理与下载。 在线工具,Gemini 图片去水印在线工具,online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
Markdown转HTML 将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online
HTML转Markdown 将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online