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

list 的实现

news 2024/10/26 18:37:57

在这里插入图片描述
上图的下述代码实现：

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;
}

顺序表可以用原生指针代替迭代器的指针，但链表不可以，链表的指针++并不能够保证找到下一个节点的位置。因此需要把当前节点封装起来作为迭代器，在迭代器类中重载++函数，使其++也可以找到下一个结点的位置。

下述代码为list的迭代器代码，对于拷贝构造使用浅拷贝就可以，因为只需要让另一个指针指向当前节点的资源，而链表不可以浅拷贝。对于析构函数，迭代器不能去析构资源。因为资源是在链表中的，迭代器只是访问。

对于迭代器而言，需要完成 *it，重载 ++ 和 – 函数，还有迭代器的比较节点是否相等函数。
在这里插入图片描述

const迭代器为什么是const_iterator而不是const iterator？
const迭代器是迭代器指向的内容不能修改而不是迭代器本身不能修改，而const iterator是iterator不能修改，因此不满足需求。
const迭代器相当于要模拟的不是 T* const 而是 const T*
在list中写了一个模板类，编译器底层生成了两个类。
在这里插入图片描述

const类型的迭代器只有operator*和operator->的返回值和普通迭代器的返回值不同，返回值不同就可以用模板。
对于下述代码自定义类型A而言，如果想用迭代器->读取A的内容，就需要在迭代器中重载->，也就是定义的模板 Ptr 函数。

template <class T , class Ref, class Ptr>
struct ListIterator
{typedef ListNode<T> Node; typedef ListIterator<T, Ref, Ptr> Self;Node* _node; //内置类型浅拷贝就可以了ListIterator(Node* node):_node(node){}//*it 可读可写，得引用返回。//T& operator*()Ref operator*(){return _node->_data;}// it->//T* operator->()Ptr operator->(){//node里的data进行取地址，返回一个T类型的指针指向data的地址，//如果存放的是A类型数据，data就是一个A类型指针就可以访问a1和a2return &_node->_data; }Self& operator++() //前置++ 返回++以后的值{_node = _node->_next;return *this;}Self operator++(int){//让tmp指针指向NOde*的资源就行了 浅拷贝够用。Self tmp(*this); _node = _node->_next;return tmp;}Self& operator--() //前置-- 返回--以后的值{_node = _node->_prev;return *this;}Self operator--(int){//让tmp指针指向NOde*的资源就行了 浅拷贝够用。Self 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;}
};

只有list才知道链表的开始和结束，因此得用list把封装的iterator连接起来。
完整的list代码：

namespace ggg
{// 节点类型定义template<class T>struct ListNode //节点的数据需要公开 用struct{ListNode<T>* _next;ListNode<T>* _prev;T _data;ListNode(const T& x = T()):_next(nullptr), _prev(nullptr), _data(x){}};// 封装节点迭代器完成的工作 普通迭代器和const迭代器使用模板复用template <class T , class Ref, class Ptr>struct ListIterator{typedef ListNode<T> Node; typedef ListIterator<T, Ref, Ptr> Self;Node* _node; //内置类型浅拷贝就可以了ListIterator(Node* node):_node(node){}//*it 可读可写，得引用返回。//T& operator*()Ref operator*(){return _node->_data;}// it->//T* operator->()Ptr operator->(){//node里的data进行取地址，返回一个T类型的指针指向data的地址，//如果存放的是A类型数据，data就是一个A类型指针就可以访问a1和a2return &_node->_data; }Self& operator++() //前置++ 返回++以后的值{_node = _node->_next;return *this;}Self operator++(int){//让tmp指针指向NOde*的资源就行了 浅拷贝够用。Self tmp(*this); _node = _node->_next;return tmp;}Self& operator--() //前置-- 返回--以后的值{_node = _node->_prev;return *this;}Self operator--(int){//让tmp指针指向NOde*的资源就行了 浅拷贝够用。Self 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 ListNode<T> Node;public://typedef ListIterator<T> iterator;//typedef ListConstIterator<T> const_iterator;typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;iterator begin(){//return iterator(_head->_next); 匿名对象iterator it(_head->_next);return it;}//链表的结尾是最后一个节点的下一个位置，也就是哨兵位iterator end() {return iterator(_head);}//类比：相当于要模拟的不是 T* const 而是 const T*const_iterator begin() const{const_iterator it(_head->_next);return it;}const_iterator end() const{return const_iterator(_head);}///void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}void clear(){iterator it = begin();while (it != end()) // !=end() 就不会清除掉head节点{it = erase(it);}}list() //构造{empty_init();}//lt1(lt)list(const list<T>& lt) //拷贝构造{empty_init();for (auto& e : lt){push_back(e);}}list<T>& operator=(list<T> lt) //赋值{std::swap(_head, lt._head);std::swap(_size, lt._size);return *this;}~list() //析构{clear();delete _head;_head = nullptr;}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;insert(end(), x); //在end前面插入就是尾插}void push_front(const T& x){insert(begin(), x);}//尾删，删掉end()（哨兵位head）的下一个，也就是最后一个有数据的位置，--就是求上一个位置prevvoid pop_back() {erase(--end());}void pop_front() //头删，begin()就是头{erase(begin());}void insert(iterator pos, const T& val){Node* cur = pos._node;Node* newnode = new Node(val);Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;_size++;}iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;_size--;return iterator(next);}size_t size() const{return _size;}bool empty(){return _size == 0;}private:Node* _head;size_t _size;};/struct A{int _a1;int _a2;A(int a1 = 0, int a2 = 0):_a1(a1),_a2(a2){}};}