stl中的list模拟实现

目录

一、list的简单介绍

首先我们要清楚list是一个带头双向循环的链表。

二、写出节点的代码

在下面代码中我们用到了模板，并且用的是struct没有用class，这是因为我们使用struct时相当于这一个类是公开的，当然我们也可以使用class但是得使用友元函数比较麻烦。

template<classT>//这里用到了模板structlistnode{
        T _data;
        listnode* _next;
        listnode* _prev;listnode(const T& x =T())//这里使用的是匿名函数，因为不确定x是什么类型，所以给了一个匿名函数的全缺省:_data(x),_next(nullptr),_prev(nullptr){}};

三、模拟实现迭代器（重点）

1、list中的迭代器是怎么实现的

我们可以查看stl的源码进行查看，如下：



我们可以看出list的迭代器就是由链表的一个节点指针来进行控制的，然后再进行对符号的重载。

2、编写iterator类的代码

根据上述可编写以下代码：

template<classT>structlist_iterator{typedef listnode<T> Node;typedef list_iterator<T> self;
        Node* _node;list_iterator(Node* node){
            _node = node;}
        self&operator++(){
            _node = _node->_next;return*this;}
        self&operator--(){
            _node = _node->_prev;return*this;}
        self operator++(int){
            self temp(*this);
            _node = _node->_next;return temp;}
        self operator--(int){
            self temp(*this);
            _node = _node->_prev;return temp;}
         T*operator->(){return&_node->_data;}
         T&operator*(){return _node->_data;}booloperator!=(const self& s){return s._node != _node;}booloperator==(const self& s){return s._node == _node;}

3、对const_iterator进行理解

首先我们要清楚是对谁加const,是对迭代器本身加const还是对迭代器指向的内容加const，我们平常使用const_iteratot时我们可以对迭代器进行++或–，但是不可以对迭代器指向的内容进行修改，由此可以看出我们的const_iterator和iterator是两个类，不可以直接对iterator加const。

4、编写const_iterator类的代码

template<classT>structlist_const_iterator{typedef listnode<T> Node;typedef list_const_iterator<T> self;
        Node* _node;list_iterator(Node* node){
            _node = node;}
        self&operator++(){
            _node = _node->_next;return*this;}
        self&operator--(){
            _node = _node->_prev;return*this;}
        self operator++(int){
            self temp(*this);
            _node = _node->_next;return temp;}
        self operator--(int){
            self temp(*this);
            _node = _node->_prev;return temp;}const T*operator->(){return&_node->_data;}const T&operator*(){return _node->_data;}booloperator!=(const self& s){return s._node != _node;}booloperator==(const self& s){return s._node == _node;}};

5、对iterator类和const_iterator类进行合并

在编写iterator类和const_iterator类我们发现除了下面的代码不一样其余的代码都是一样的。


但是这样写的话，代码就会冗余，所以这时我们用一个类模板，对代码进行修改，如下：

template<classT,classRef,classPtr>structlist_iterator{typedef listnode<T> Node;typedef list_iterator<T,Ref,Ptr> self;
        Node* _node;list_iterator(Node* node){
            _node = node;}
        self&operator++(){
            _node = _node->_next;return*this;}
        self&operator--(){
            _node = _node->_prev;return*this;}
        self operator++(int){
            self temp(*this);
            _node = _node->_next;return temp;}
        self operator--(int){
            self temp(*this);
            _node = _node->_prev;return temp;}
        Ptr operator->(){return&_node->_data;}
        Ref operator*(){return _node->_data;}booloperator!=(const self& s){return s._node != _node;}booloperator==(const self& s){return s._node == _node;}};

四、list类进行代码实现

这里主要是写构造函数、拷贝构造、赋值拷贝、析构函数、迭代器的begin()和end()的实现，以及其他功能的实现。
代码如下:

template<classT>classlist{typedef listnode<T> Node;public:typedef list_iterator<T,T&,T*> iterator;typedef list_iterator<T,const T&,const T*> const_iterator;voidempty_init(){
            _head =new Node;
            _head->_next = _head;
            _head->_prev = _head;
            _size =0;}
        const_iterator begin()const{return _head->_next;}
        const_iterator end()const{return _head;}
        iterator begin(){return _head->_next;}
        iterator end(){//返回的是最后一个节点的后一个，所以返回的是头节点return _head;}list(){empty_init();}list(list<T>& it){empty_init();for(auto e : it){push_back(e);}}voidswap(list<T>& It){
            std::swap(_head, It->_head);
            std::swap(_size, It->_size);}
        list<T>&operator=(list<T>& It){swap(It);return*this;}~list(){clear();delete(_head);
            _size =0;}voidpush_back(const T& x){insert(end(), x);}voidpush_front(const T& x){insert(begin(), x);}voidpop_front(){erase(begin());}voidpop_back(){erase(--end());}voidclear(){while(!empty()){pop_back();}}boolempty(){return _size ==0;}
        size_t size(){return _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;returniterator(next);}
        iterator insert(iterator pos, T x){
            Node* cur = pos._node;
            Node* newNode =newNode(x);
            Node* prev = cur->_prev;
            prev->_next = newNode;
            newNode->_prev = prev;
            newNode->_next = cur;
            cur->_prev = newNode;++_size;returniterator(newNode);}private:
        Node* _head;
        size_t _size;};