当前位置:首页 » 《关于电脑》 » 正文

C++:模拟实现list

8 人参与  2024年10月12日 14:41  分类 : 《关于电脑》  评论

点击全文阅读


节点

对于链表节点,我们需要一个数据、一个前驱指针、一个后继指针来维护,并且将其封装成一个类。

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

使用struct的原因是因为,struct默认的域作用限定符是public,方便后续使用,不用走友元的那一套。

迭代器

我们知道迭代器提供访问容器的方法,之前实现vector和string时,迭代器用的就是数据类型的指针,但是list不可以直接用。因为vector和string的数据在内存的存放都是连续的,如果想找下一个数据的指针(迭代器),直接(迭代器)指针++就可以了;但是list的数据存放在内存不是连续的,如果直接把指针当成迭代器,迭代器++是找不到下一个数据的迭代器

所以综上所述,我们应该用类对链表数据类型的指针封装成迭代器在类里重载操作符让其达到我们想要的效果。

当然,我们实现的迭代器应该有两个版本,普通版本和const版本。

//普通迭代器template<class T>struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T> Self;Node* _node;list_iterator(Node* node):_node(node){}T& operator*(){return _node->_data;}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--(){_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;}};
​//const迭代器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--(){_node = _node->_prev;return *this;}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>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& it) const{return _node != it._node;}bool operator==(const Self& it) const{return _node == it._node;}};

 增加Ref和Ptr模板参数,让T*和T&作为参数传入,这就可以解决将两份代码合二为一。

整体框架

​​template<class T>class list{typedef list_node<T> Node; public:/*typedef list_iterator<T> iterator;typedef list_const_iterator<T> const_iterator;*///将T&和T*作为参数传入    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 end()    {    //最后一个有效节点的下一位置,也就是哨兵节点    return _head;    }    const_iterator begin() const    {    return _head->_next;    }    const_iterator end() const    {    return _head;    }    //实现各种函数......private:Node* _head;size_t _size;};​​

构造函数

empty_init

多种构造函数的代码都有重合,所以把重合部分独立成一个函数。

​void empty_init(){//创造哨兵节点    _head = new Node();_head->_next = _head;_head->_prev = _head;_size = 0;}​

普通构造

普通构造就是创造哨兵节点,调用empty_init即可。

//普通构造list(){empty_init();}

列表构造

C++11的用法,用法例子如下:

list<int> lt1 = { 1,2,3,4,5,6 };

 先创造一个哨兵节点,然后将列表的元素尾插即可

//列表构造list(initializer_list<T> il){empty_init();for (auto& e : il){push_back(e);}}

关于列表initializer_list<T>的知识,可以看以下连接。

介绍列表

拷贝构造

创建哨兵节点,将链表元素尾插到待构造的链表就完成拷贝构造了。

//拷贝构造list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}

赋值重载

临时对象lt交换即可,跟string、vector的实现类似。

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

析构函数

clear

清理除了哨兵节点以外的所有节点。

void clear(){auto it = begin();while (it != end()){it = erase(it);}}

先将链表clear掉,然后清理哨兵节点。  

~list(){clear();delete _head;_head = nullptr;}

insert

在pos(迭代器)位置前插入元素x,插入后_size++,返回新插入元素的迭代器。

iterator insert(iterator pos, const T& x){Node* cur = pos._node; //pos是iterator类的对象,访问里面的成员变量用pos._node,不能用pos->_nodeNode* prev = cur->_prev;Node* newnode = new Node(x);newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;prev->_next = newnode;++_size;//隐式类型转换return newnode;}

erase

删除pos位置的元素,删除后_size--,返回删除元素的下一元素的迭代器。

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

push_back和push_front

利用insert函数就可以实现尾插和头插。

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);}void push_front(const T& x){insert(begin(), x);}

pop_back和push_front

利用erase函数实现尾删和头删。

void pop_back(){erase(--end());}void pop_front(){erase(begin());}

size

返回链表有效元素的个数.。

size_t size() const{return _size;}

empty

判断链表是否为空。

bool empty() const{return _size == 0;}

Print_Container

打印容器的函数。

template<class Container>void Print_Container(const Container& con){//const对象要用const迭代器,这里没实现的话会报错/*auto it = con.begin();while (it != con.end()){cout << *it << " ";++it;}*/for (auto e : con){cout << e << " ";}cout << endl;}

拜拜,下期再见?

摸鱼ing?✨?


点击全文阅读


本文链接:http://zhangshiyu.com/post/171045.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1