【C++】list容器

server/2025/1/20 14:01:22/

学习途径

list的使用

list的一些构造

迭代器说明

接口使用

迭代器失效问题

list和vector对比

模拟实现list

迭代器的模拟（重点）

List.h文件

学习途径

在学习list之前，我们可以查询一些相关文档来学习！

文档详情：list文档学习

list的使用

list的一些构造

图：

构造使用示范：

迭代器说明

list中的迭代器和咋们印象中的迭代器一样：

begin指向第一个元素，end指向最后一个元素的后面一个位置！rbegin指向最后一个元素，rbegin指向第一个元素的前一个位置！

使用的时候要注意：

接口使用

常用接口

这里不做代码示范！比较简单！

迭代器失效问题

迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。

因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

list和vector对比

模拟实现list

迭代器的模拟（重点）

list的迭代器模拟和vector不一样！

因为list底层是带头的双向链表，而链表底层是节点连接而成的，不是连续的空间！

而vector底层是动态数组，是一块连续的空间！

所以我们如何将这一块一块的空间来遍历它！！！

我们可以用一个类包装它，这个类就叫迭代器，上图理解：

理解了这里，其他就水到渠成了！！！

List.h文件

#include<iostream>
#include<assert.h>
namespace ywc
{template<class T>struct list_node{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>struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T> Self;Node* _node;list_iterator(Node* node):_node(node){}bool operator!=(const Self& s){return _node != s._node;}const T& operator*(){return _node->_data;}Self& operator++(){_node = _node->_next;return *this;}};template<class T>class list{typedef list_node<T> Node;public:typedef list_iterator<T> iterator;iterator begin(){return _head->_next;}iterator end(){return _head;}list(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}size_t size(){return _size;}void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = pos._node->_prev;Node* newnode = new Node(x);//prev newnode curnewnode->_next = cur;cur->_prev = newnode;prev->_next = newnode;newnode->_prev = prev;++_size;}void 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;}void pop_back(){erase(_head->_prev);}void pop_front(){erase(begin());}bool empty(){return _size==0;}private:Node* _head;size_t _size;};
}

我们下期见！！！