当前位置：首页 > news >正文

C++ : list的模拟

news 2025/7/27 7:14:49

一、list的节点的构造

二、list的迭代器

三、list 的实现

一、list的节点的构造

/////////////////////          节点 _node                     ////////////////////////////
template <class T>
struct list_node//相当于class + public
{list_node<T>* _next;// char/int *_next//  初始化模版用T去初始化list_node<T>* _prev;T _val;list_node(const T& val = T()):_next(nullptr), _prev(nullptr), _val(val){}
};

list是由一个个节点链接而成并且每个节点要包含节点的前后两个指针和数据，所以这里我们将节点定义成一个strcut结构体，并且写出构造函数即可
最初的时候我们默认给节点的前后指针初始化为nullptr

二、list的迭代器

使用迭代器的目的就是模拟指针，在string和vector中，都可以通过++/--向后进行迭代找到下一个数据位置，而list却不可以，这其中的本质是list的结构不同造成的，list是由一个一个节点构成的，节点中存放着数据，我们使用指针指向节点，进行解引用拿到的是节点，而不是节点中的数据，并且由于节点的物理空间是不连续的，使用++无法进行迭代找到下一个位置的节点，而是访问到了一块未知的空间
所以我们可以考虑使用一个struct类封装一个节点的指针来作为iterator 模拟指针，并且由于这个节点的类型是不确定的所以这个struct类应该是 struct类的模板，通过运算符重载++/--，来达到我们的目的
模板类迭代器的类型为__list_iterator<T>,而不是__list_iterator

/////////////        迭代器   iterator                ///////////////////////////////////typedef _list_iterator<T, T&,T*> iterator;
//typedef _list_iterator<T,const T&,const T*> const_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_node<T> * _node; 这不就是节点的指针嘛_list_iterator(Node* node):_node(node){}Ref operator *(){return _node->_val;}Ptr operator->(){return &_node->_val;}self& operator++()//前置++ :  ++_node{_node = _node->_next;return *this;}self operator++(int)//后置++  :  _node++{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& it)const//传值返回，临时对象都有常型{return _node != it._node;}bool operator==(const self& it)const//传值返回，临时对象都有常型{return _node == it._node;}};

template <class T, class Ref, class Ptr> ——由于const对象要调用的const_iterator迭代器，而普通对象要调用iterator 迭代器 ,我们可以用模版template <class T, class Ref, class Ptr>,通过我们传参数如：_list_iterator<T, T&,T*> iterator ; _list_iterator<T,const T&,const T*> const_iterator; 来让编译器来帮我们写，如果不用模版，则我们要分开写iterator 和 const_iterator
```
struct _list_const_iterator{typedef list_node<T> Node;Node* _node;//list_node<T> * _node; 这不就是节点的指针嘛_list_const_iterator(Node* node):_node(node){}..............
```
typedef list_node<T> Node；——把list_node<T> 当作节点
class T, class Ref, class Ptr 分别对应着 T,const T&,const T* / T, T&,T* ——这里传引用因为我们不知道list中数据的类型是自定义类型还是内置类型，如果是自定义类型采用拷贝传参消耗大，所以我们统一使用引用传参
Node* _node;——实际上就是 list_node<T> * _node;
typedef _list_iterator<T, Ref, Ptr> self; ——由于在模板中要多次使用迭代器的类型，为了便于修改控制，这里我们就使用typedef将迭代器类型__list_iterator<T,Ref，Ptr>重命名为self

三、list 的实现

	///////////////////////       list       (双向链表)     /////////////       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;直接返回_head->_next;return iterator(_head->_next);//返回一个用_head->_next初始化的iterator}iterator end()//  _head的传值返回 具有常性{return _head;}const_iterator begin()const{//return _head->_next;直接返回_head->_next;return const_iterator(_head->_next);//返回一个用_head->_next初始化的iterator}const_iterator end()const//  _head的传值返回 具有常性{return _head;}void empty_init(){_head = new Node;_head->_prev = _head;_head->_next = _head;_size = 0;}list(){empty_init();}// lt2(lt1)list(const list<T>& lt)//list(const list& lt){empty_init();for (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)//list& operator=(list lt){swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}void push_back(const T& x){//Node* tail = _head->_prev;//Node* newnode = new Node(x);//tail->_next = newnode;////newnode->_prev = tail;//newnode->_next = _head;//_head->_prev = newnode;insert(end(), x);/** Node* newnode=new Node(x);* _head->_next=newnode;* newnode->prev=_head;* _head->_prev=newnode;*/}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* newnode = new Node(x);cur->_prev->_next = newnode;newnode->_prev = cur->_prev;newnode->_next = cur;cur->_prev = newnode;_size++;return newnode;}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 next;}size_t size(){return  _size;}private:Node* _head;size_t _size;};

typedef list_node<T> Node; typedef _list_iterator<T, T&, T*> iterator; typedef _list_iterator<T, const T&, const T*> const_iterator; —— 先将list_node<T>类，和_list_iterator<T,T&,T*> 类换成Node 和 iterator
iterator begin()———返回一个用_head->_next
iterator end()——返回head节点
void empty_init()——list的结构是一个带头双向循环链表，在没有数据的时候，仅仅剩下的这一个头节点仍然为带头双向循环，让头节点的的两个用于指向下一个节点指针和指向前一个节点的指针指向它自己
list()——构造函数需要使用没有数据的初始化
list(const list<T>& lt)——拷贝构造函数，不对拷贝对象进行修改，所以我们采用const修饰，同时拷贝构造必须是引用传参的形式，否则会造成无穷递归，拷贝出一个list对象，首先就应该确保这个对象有一个head节点，那么这时复用empty_init函数，再使用范围for去遍历被拷贝对象，依次将数据尾插到拷贝对象中即可，注意： 当我们使用范围for的时候针对这里变量e的初始化一定要采用引用，因为我们不确定对象中存储的类型是自定义类型还是内置类型，如果要是自定义类型进行拷贝给变量e的消耗大，所以这里采用引用
void swap(list<T>& lt)——交换俩个头节点指针和size数据
operator= ——接收list对象参数的时候采用值传参，即调用拷贝构造进行构造出目标对象,调用swap交换this指针指向的对象和lt对象，当operator=函数调用结束的时候，局部对象lt的生命周期结束那么lt对象自动调用析构函数去完成原this指针指向的对象的资源的清理工作
push_front(const T& x)、push_back(const T& x)——调用insert
注意： (使用引用传参，是为了避免这里的数据类型是自定义类型进行值传参(调用拷贝构造)的消耗大)
pop_back()、pop_front()——调用erase
insert——在pos迭代器位置前进行插入，找到pos前的节点位置，这里保存一下pos迭代器中的节点指针指向的前一个节点的指针_prev即可找到pos前的节点位置prev ，用new去申请一个值为val的节点作为要插入的新节点newnode，同时由于插入了一个节点，那么_size也应该对应加1
erase——初始状态无论有数据节点还是没有数据节点，这里的头节点都存在，不能被删除，所以应该使用asseert断言一下pos不等于头节点，删除一个节点之后list对象中的有效节点个数_size应该对应减一，使用delete释放pos迭代器对应的节点，防止内存泄露，函数返回原pos迭代器的节点的下一个节点的迭代器，便于对后续节点进行操作