C++ STL list 容器详解：使用与模拟实现

文章目录

• C++ STL list 容器详解：使用与模拟实现
  • 1. list 的介绍及使用
    • 1.1 list 的介绍
    • 1.2 list 的使用
      • 1.2.1 list 的构造
      • 1.2.2 list 迭代器的使用
      • 1.2.3 list capacity
      • 1.2.4 list element access
      • 1.2.5 list modifiers
      • 1.2.6 list 的迭代器失效
  • 2. list 的模拟实现
    • 2.1 基本结构
      • 2.1.1 节点类 (list_node)
      • 2.1.2 迭代器类 (list_iterator)
    • 2.2 list 容器类
      • 2.2.1 类型定义和迭代器
      • 2.2.2 构造函数和初始化
      • 2.2.3 插入操作
      • 2.2.4 删除操作
      • 2.2.5 容量操作
      • 2.2.6 赋值操作
    • 2.3 迭代器模板技巧
    • 2.4 测试示例
      • 源代码
    • 2.5 设计要点总结
  • 3. list 与 vector 的对比

C++ STL list 容器详解：使用与模拟实现

1. list 的介绍及使用

1.1 list 的介绍

list 是 C++ STL 中的一个重要容器，它是一个带头结点的双向循环链表。与 vector 不同，list 在任意位置插入和删除元素的时间复杂度都是 O(1)，但不支持随机访问（即不能通过下标直接访问元素）。

1.2 list 的使用

list 提供了丰富的接口，下面我们介绍其中一些常见且重要的接口。

1.2.1 list 的构造

1.2.2 list 迭代器的使用

迭代器可以暂时理解为指向 list 中某个节点的指针。

• begin()：返回指向第一个元素的迭代器
• end()：返回指向最后一个元素下一个位置的迭代器
• rbegin()：返回指向最后一个元素的反向迭代器（即 end() 位置）
• rend()：返回指向第一个元素前一个位置的反向迭代器（即 begin() 位置）

注意：

1. begin 和 end 是正向迭代器，++ 向后移动。

rbegin 和 rend 是反向迭代器，++ 向前移动。迭代器分类

1.2.3 list capacity

1.2.4 list element access

1.2.5 list modifiers

1.2.6 list 的迭代器失效

由于 list 的底层是双向循环链表，插入操作不会导致迭代器失效。只有在删除元素时，指向被删除节点的迭代器才会失效，其他迭代器不受影响。

错误的删除写法：

while (it != l.end()) { l.erase(it); // it 失效 ++it; // 错误，it 已无效 } 

2. list 的模拟实现

2.1 基本结构

2.1.1 节点类 (list_node)

template<class T> class list_node { public: T _data; list_node<T>* _next; list_node<T>* _prev; list_node(const T& data = T()) :_data(data) ,_next(nullptr) ,_prev(nullptr) { } }; 

这是 list 的基础节点结构，采用双向链表设计，每个节点包含：

• _data: 存储实际数据
• _next: 指向下一个节点
• _prev: 指向上一个节点

2.1.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) { } // 解引用操作符 Ref operator*() { return _node->_data; } // 箭头操作符 Ptr operator->() { return &_node->_data; } // 前置++ Self& operator++() { _node = _node->_next; return *this; } // 后置++ Self operator++(int) { Self tmp(*this); _node = _node->_next; return tmp; } // 前置-- Self& operator--() { _node = _node->_prev; return *this; } // 后置-- Self operator--(int) { Self tmp(*this); _node = _node->_prev; return tmp; } // 不等于操作符 bool operator!=(const Self& s) { return _node != s._node; } }; 

关键特性：

• 通过模板参数 Ref 和 Ptr 实现 const 和非 const 迭代器的统一
• 支持前后遍历操作
• 支持箭头操作符访问成员

2.2 list 容器类

2.2.1 类型定义和迭代器

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 _head->_next; // 隐式类型转换 } iterator end() { return _head; } const_iterator begin() const { return _head->_next; } const_iterator end() const { return _head; } 

迭代器转换机制：

• Node* 可以隐式转换为 iterator，因为 list_iterator 有单参数构造函数
• begin() 返回第一个有效元素位置
• end() 返回头节点位置，符合 STL 左闭右开原则

2.2.2 构造函数和初始化

void empty_init() { _head = new Node; _head->_next = _head; _head->_prev = _head; _size = 0; } list() { empty_init(); } // 拷贝构造 list(list<T>& lt) { empty_init(); for (auto& e : lt) { push_back(e); } } // 初始化列表构造 list(initializer_list<int> il) { empty_init(); for (auto& e : il) { push_back(e); } } 

2.2.3 插入操作

iterator insert(iterator pos, const T& x) { Node* cur = pos._node; Node* prev = cur->_prev; Node* newnode = new Node(x); prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; ++_size; return newnode; // 返回新插入节点的迭代器 } void push_back(const T& x) { insert(end(), x); // 复用 insert } void push_front(const T& x) { insert(begin(), x); // 复用 insert } 

2.2.4 删除操作

iterator erase(iterator pos) { assert(pos != end()); // 不能删除头节点 Node* prev = pos._node->_prev; Node* next = pos._node->_next; prev->_next = next; next->_prev = prev; delete pos._node; --_size; return next; // 返回下一个有效位置的迭代器 } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } 

迭代器失效处理：

• erase 返回下一个有效位置的迭代器
• 正确处理删除操作后的迭代器续接

2.2.5 容量操作

size_t size() const { return _size; } bool empty() const { return _size == 0; } void clear() { auto it = begin(); while (it != end()) { it = erase(it); // erase 返回下一个地址 } } 

2.2.6 赋值操作

list<T>& operator=(list<T> lt) { swap(lt); return *this; } void swap(list<T>& lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); } 

2.3 迭代器模板技巧

// 使用模板参数实现 const 和非 const 迭代器的统一 typedef list_iterator<T, T&, T*> iterator; typedef list_iterator<T, const T&, const T*> const_iterator; 

这种设计避免了重复代码，只需要一个模板类就能同时支持普通迭代器和 const 迭代器。

2.4 测试示例

// 测试基本功能 void test_list01() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); // 遍历输出 list<int>::iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; ++it; } cout << endl; } // 测试迭代器失效 void test_list02() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); // insert 不会导致迭代器失效 list<int>::iterator it = lt.begin(); lt.insert(it, 10); *it += 100; // 仍有效 // erase 会导致当前迭代器失效 it = lt.begin(); while (it != lt.end()) { if (*it % 2 == 0) { it = lt.erase(it); // 必须接收返回值 } else { ++it; } } } 

源代码

#pragma once #include<assert.h> namespace bit { template<class T> class list_node { public: T _data; list_node<T>* _next; list_node<T>* _prev; list_node(const T& data = T()) :_data(data) ,_next(nullptr) ,_prev(nullptr) { } }; 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->_data; } Ptr operator->() { return &_node->_data; } Self& operator++() { _node = _node->_next; return *this; } Self operator++(int) { Self tmp(*this); _node = _node->_next; return tmp; } Self operator--(int) { Self tmp(*this); _node = _node->_prev; return tmp; } Self& operator--() { _node = _node->_prev; return *this; } bool operator!=(const Self& s) { return _node != s._node; } }; /*template<class T> struct list_const_iterator { typedef list_node<T> Node; typedef list_const_iterator<T> Self; Node* _node; list_const_iterator(Node* node) :_node(node) { } const T& operator*() { return _node->_data; } const T* operator->() { return &_node->_data; } Self& operator++() { _node = _node->_next; return *this; } Self operator++(int) { Self tmp(*this); _node = _node->_next; return tmp; } Self operator--(int) { Self tmp(*this); _node = _node->_prev; return tmp; } Self& operator--() { _node = _node->_prev; return *this; } bool operator!=(const Self& s) { return _node != s._node; } };*/ template<class T> class list { typedef list_node<T> Node; public: /*typedef list_iterator<T> iterator; typedef list_const_iterator<T> const_iterator;*/ typedef list_iterator<T,T&,T*> iterator; typedef list_iterator<T,const T&,const T*> const_iterator; iterator begin() { /*iterator it(_head->_next); return it;*/ //return iterator(_head->_next); return _head->_next;//节点的指针可以隐式类型转换成iterator的 //单参数构造函数可以隐式类型转换 } iterator end() { return _head; } const_iterator begin() const { /*iterator it(_head->_next); return it;*/ //return iterator(_head->_next); return _head->_next;//节点的指针可以隐式类型转换成iterator的 //单参数构造函数可以隐式类型转换 } const_iterator end() const { return _head; } void empty_init() { _head = new Node; _head->_next = _head; _head->_prev = _head; _size = 0; } list() { empty_init(); } ~list() { clear(); delete _head; _head = nullptr; } void clear() { auto it = begin(); while (it != end()) { it = erase(it);//erase返回下一个地址 } } list<T>& operator=(list<T> lt) { swap(lt); return *this; } void swap(list<T>& lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); } //lt2(lt1) 拷贝构造 list(list<T>& lt) { empty_init(); for (auto& e : lt) { push_back(e); } } list(initializer_list<int> il) { empty_init(); for (auto& e : il) { push_back(e); } } 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;*/ insert(end(), x); } iterator insert(iterator pos,const T& x)//c++中插入默认在之前插 { Node* cur = pos._node; Node* prev = cur->_prev; Node* newnode = new Node(x); prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; ++_size; return newnode; } void push_front(const T& x) { insert(begin(), x); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } iterator erase(iterator pos) { assert(pos != end()); Node* prev = pos._node->_prev; Node* next = pos._node->_next; prev->_next = next; next->_prev = prev; delete pos._node; return next;//走隐式类型转换 编译器发现next是Node*类型的，就会走构造函数iteratpor(Node* node) } size_t size() const { return _size; } bool empty() const { return _size == 0; } private: Node* _head; size_t _size; }; struct AA { int _a1; int _a2; }; template<class Container> void print_container(const Container& con) { //const iterator 迭代器本身不能修改 //const_iterator 指向内容不能修改 迭代器要修改(比如++) //list<int>::const_iterator it = con.begin(); //typename Container::const_iterator it = con.begin(); auto it = con.begin(); while (it != con.end()) { cout << *it << " "; ++it; } cout << endl; /* for (auto e : con) { cout << e << " "; } cout << endl;*/ } void test_list01() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); list<int>::iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; ++it; } cout << endl; list<AA> lta; lta.push_back(AA()); lta.push_back(AA()); lta.push_back(AA()); lta.push_back(AA()); list<AA>::iterator ita = lta.begin(); while (ita != lta.end()) { //cout<< (*ita)._a1 << " "<<(*ita)._a2<<endl; //特殊处理 本来应该两个->才合理，为了可读性，省略一个 cout << ita->_a1 << ":" << ita->_a2 << endl; //cout << ita.operator->()->_a1 << ":" << ita->_a2 << endl; ++ita; } cout << endl; print_container(lt); } void test_list02() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); list<int>::iterator it = lt.begin(); lt.insert(it, 10); *it += 100; print_container(lt); //insert以后迭代器不失效 //删除偶数 it = lt.begin(); while (it != lt.end()) { if (*it % 2 == 0) { it=lt.erase(it);//erase以后 迭代器失效 } else { ++it; } } print_container(lt); } void test_list03() { list<int> lt1; lt1.push_back(1); lt1.push_back(2); lt1.push_back(3); lt1.push_back(4); list<int> lt2(lt1); print_container(lt1); print_container(lt2); list<int> lt3; lt3.push_back(10); lt3.push_back(20); lt3.push_back(30); lt3.push_back(40); lt1 = lt3; print_container(lt1); print_container(lt3); } void func(const list<int>& lt) { print_container(lt); } void test_list04() { //直接构造 list<int> lt0 ( { 1,3,5 }); //隐式类型转换 list<int> lt1= {1, 2, 3, 4, 5}; print_container(lt1); auto il = { 1,2,3,4 }; cout << typeid(il).name() << endl; func(lt1); func({ 1,3,6,7 });//隐式类型转换 } }; 

2.5 设计要点总结

1. 双向循环链表：头节点连接首尾，简化边界处理
2. 迭代器封装：隐藏底层指针，提供统一接口
3. 模板复用：通过模板参数减少代码重复
4. 异常安全：正确管理资源，避免内存泄漏
5. STL 兼容：遵循 STL 接口规范

这个实现展示了 list 容器的核心机制，包括节点管理、迭代器设计、插入删除操作等关键技术点。

3. list 与 vector 的对比