C++ list模拟实现

C++ list的模拟实现

• 一.前置说明
• • 1.前言
  • 2.list是如何封装的?
  • • 1.STL库中的实现
    • • 1.成员变量
      • 2.构造函数
      • 3.迭代器
      • 2.节点类
      • 3.迭代器类
      • 4.list类
      • 3.const迭代器的说明
      • 4.最终的大致框架:
      • 5.初步版本(不包含const迭代器的版本)
      • 二.迭代器类的实现
      • • 1.iterator的成员变量和构造函数
        • 2.前置后置++ --
        • 3.解引用* ->
        • 4.== !=
        • 三.list类的实现
        • • 1.构造函数
          • 2.begin end
          • 3.insert
          • 4.erase
          • 5.头插头删,尾插尾删的复用
          • 6.clear和析构函数
          • • 1.clear
            • 2.析构函数
            • 7.swap和其他小函数
            • • 1.swap
              • 2.empty
              • 3.size
              • 8.拷贝构造函数
              • 9.赋值运算符重载
              • 四.const迭代器加入后的改动
              • • 1.原版
                • 2.精简版
                • 五.完整代码
                • 六.补充
                • • 1.一个"奇怪"的现象
                  • 2.小小优化一下

                    一.前置说明

                    对于list而言,���难的点是它如何进行设计与封装的

                    尤其是list的迭代器

                    而不是链表的基础操作

                    只要实现好迭代器之后,list就非常好实现了

                    1.前言

                    首先我们要说明的是:

                    1.list就是数据结构当中的带头双向循环链表

                    2.list的迭代器不是简简单单的原生指针,而是在原生指针的基础上进行了一层封装

                    3.关于链表的操作我们就不再赘述了,因为带头双向循环链表的知识并不难,而且大家应该都是掌握了的

                    2.list是如何封装的?

                    1.STL库中的实现

                    下面我们依次看一下成员变量,构造函数和迭代器

                    1.成员变量

                    2.构造函数

                    3.迭代器

                    因此我们要实现的这三个类的介绍如下:

                    2.节点类

                    templatestruct list_node{T _data;list_node* _next;list_node* _prev;list_node(const T& x = T()):_data(x), _next(nullptr), _prev(nullptr){}};

                    3.迭代器类

                    templatestruct __list_iterator{typedef __listIterator Self;typedef __listIterator iterator;typedef ListNode Node;Node* _node;__listIterator(Node* node):_node(node){}__listIterator(const iterator& it):_node(it._node){}self& operator++();self& operator--();self operator++(int);Ref operator*();Ptr operator->();//注意:一定是判断节点指针是否相等,不是迭代器是否相等!!!!bool operator!=(const self& s);bool operator==(const self& s);};

                    这里把节点类和迭代器类都用struct来定义

                    是因为这两个类我们一般都是开放使用的

                    而struct的默认访问限定符是public 外部可以访问

                    4.list类

                    templateclass list{typedef list_node Node;public:typedef __list_iterator iterator;typedef __list_iterator const_iterator;iterator begin();iterator end();const_iterator begin() const;const_iterator end() const;list(){empty_init();}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}//其他一堆成员函数private:Node* _head;size_t _size;//记录数据个数};

                    3.const迭代器的说明

                    我们先基于非const迭代器实现完整个list之后

                    最后在加上const迭代器的版本形成最终的大致框架

                    4.最终的大致框架:

                    namespace wzs{templatestruct list_node{T _data;list_node* _next;list_node* _prev;list_node(const T& x = T());};templatestruct __list_iterator{typedef __listIterator Self;typedef __listIterator iterator;typedef ListNode Node;Node* _node;__listIterator(Node* node):_node(node){}__listIterator(const iterator& it):_node(it._node){}self& operator++();self& operator--();self operator++(int);self operator--(int);Ref operator*();Ptr operator->();//注意:一定是判断节点指针是否相等,不是迭代器是否相等!!!!bool operator!=(const self& s);bool operator==(const self& s);};templateclass list{typedef list_node Node;public:typedef __list_iterator iterator;typedef __list_iterator const_iterator;iterator begin();iterator end();const_iterator begin() const;const_iterator end() const;void empty_init();list();list(const list& lt);void swap(list& lt);//现代写法list& operator=(list lt);~list();//复用erasevoid clear();//复用insertvoid push_back(const T& x);void push_front(const T& x);void pop_front();void pop_back();//list的insert没有迭代器失效的问题iterator insert(iterator pos, const T& x);//list的erase有迭代器失效的问题iterator erase(iterator pos);size_t size() const;bool empty() const;private:Node* _head;size_t _size;};}

                    5.初步版本(不包含const迭代器的版本)

                    namespace wzs{templatestruct list_node{T _data;list_node* _next;list_node* _prev;list_node(const T& x = T());};templatestruct __list_iterator{typedef list_node Node;typedef __list_iterator self;Node* _node;__list_iterator(Node* node);self& operator++();self& operator--();self operator++(int);self operator--(int);Ref operator*();Ptr operator->();//注意:一定是判断节点指针是否相等,不是迭代器是否相等!!!!bool operator!=(const self& s);bool operator==(const self& s);};templateclass list{typedef list_node Node;public:typedef __list_iterator iterator;iterator begin();iterator end();void empty_init();list();list(list& lt);void swap(list& lt);//现代写法list& operator=(list lt);~list();//复用erasevoid clear();//复用insertvoid push_back(const T& x);void push_front(const T& x);void pop_front();void pop_back();//list的insert没有迭代器失效的问题iterator insert(iterator pos, const T& x);//list的erase有迭代器失效的问题iterator erase(iterator pos);size_t size() const;bool empty() const;private:Node* _head;size_t _size;};}

                    二.迭代器类的实现

                    1.iterator的成员变量和构造函数

                    typedef list_node Node;typedef __list_iterator self;Node* _node;__list_iterator(Node* node):_node(node){}

                    注意这两个typedef

                    一个是把list_node给命名为Node

                    一个是把迭代器自身__list_iterator命名为self

                    增强代码的可读性

                    这里的构造函数的作用就是能够通过节点指针直接转换为迭代器

                    2.前置后置++ –

                    迭代器++就是指向下一个元素

                    迭代器–就是指向前一个元素

                    在链表这里

                    假设有这么一个节点:Node* cur

                    指向下一个元素就是

                    cur=cur->_next

                    指向前一个元素就是

                    cur=cur->_prev

                    因此我们可以写出这样的代码

                    self就是这个迭代器本身的类型

                    //前置++self& operator++(){_node = _node->_next;return *this;}//前置--self& operator--(){_node = _node->_prev;return *this;}//后置++self operator++(int){//拷贝构造一个tmpself tmp(*this);_node = _node->_next;return tmp;}//后置--self operator--(int){//拷贝构造一个tmpself tmp(*this);_node = _node->_prev;return tmp;}

                    3.解引用* ->

                    迭代器解引用就是取出迭代器指向的数据

                    因此对于链表而言

                    假设有这么一个节点:Node* cur

                    *就是 cur->data,类型为T&

                    ->就是&cur->data,类型为T*

                    因此我们写出这样的代码

                    T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}

                    4.== !=

                    注意:我们一定是判断节点指针是否相等,而不是判断迭代器是否相等!

                    bool operator!=(const self& s){return _node != s._node;}bool operator==(const self& s){return _node == s._node;}

                    list的iterator体现了一个非常重要面向对象的设计思想:

                    封装:屏蔽了底层差异和实现细节,提供了统一的访问修改遍历方式

                    也正是因为这层封装,list的迭代器在使用的时候才能够让我们无需关心底层的具体实现细节而能够快速上手和使用

                    list的非const迭代器就是这些内容

                    三.list类的实现

                    1.构造函数

                    typedef list_node Node;void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}

                    头节点一开始就是要存在的

                    头节点的前驱是自己,后继也是自己

                    2.begin end

                    begin是指向第一个有效数据的迭代器

                    end是指向最后一个有效数据的下一个位置的迭代器

                    又因为list是带头双向循环链表,头节点_head是不存储有效数据的

                    因此第一个有效数据的节点是_head->_next

                    最后一个有效数据的节点是_head->_prev

                    最后一个有效数据的下一个节点就是_head

                    typedef __list_iterator iterator;iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}

                    list类中把__list_iteratortypedef成了iterator

                    这里调用了iterator这个类的构造函数

                    3.insert

                    list的insert没有迭代器失效的问题

                    因为list没有扩容这一概念,节点都是一个一个按需申请的

                    //在pos位置前面插入xiterator insert(iterator pos, const T& x){//new一个新节点Node* newnode = new Node(x);//利用迭代器取出其中的节点Node* cur = pos._node;//记录当前节点的前驱Node* prev = cur->_prev;//插入新节点newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;prev->_next = newnode;//有效数据个数+1++_size;//返回新节点的迭代器return iterator(newnode);}

                    到此我们就可以插入数据并且遍历访问修改数据了

                    4.erase

                    //list的erase有迭代器失效的问题//因此要返回被删除位置的下一个位置的迭代器iterator erase(iterator pos){//利用迭代器取出当前节点Node* cur = pos._node;//找到当前节点的前驱和后继Node* prev = cur->_prev;Node* next = cur->_next;//在链表中删除当前节点prev->_next = next;next->_prev = prev;//释放当前节点delete cur;cur = nullptr;//有效数据个数-1--_size;//返回被删除位置的下一个位置的迭代器//也就是后继指针的迭代器return iterator(next);}

                    5.头插头删,尾插尾删的复用

                    void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}

                    6.clear和析构函数

                    1.clear

                    clear:清空所有有效数据,恢复到原始状态(无参构造后的状态)

                    超级传统的版本

                    void clear(){if (!empty()){//释放所有有效数据的节点Node* cur = _head->_next;while (cur != _head){Node* next = cur->_next;delete cur;cur = next;}//恢复成原始状态_head->_next = _head;_head->_prev = _head;_size = 0;}}

                    复用erase的版本

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

                    2.析构函数

                    有了clear之后,析构函数就能复用clear了

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

                    注意:我们new节点的时候是直接new的

                    不是这样new []的

                    因此delete的时候要直接delete

                    而不要这样delete[]

                    否则会出现错误的,而且不容易看出来

                    7.swap和其他小函数

                    1.swap

                    因为list的成员变量只有Node*和size,而且他们都是内置类型(指针类型和int类型)

                    因此交换这两个成员变量即可

                    void swap(list& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}

                    2.empty

                    bool empty() const{return _head->_next == _head;}

                    只有头节点自己的时候就是空链表

                    3.size

                    记录链表当中有效数据的个数

                    size_t size() const{return _size;}

                    8.拷贝构造函数

                    对于拷贝构造函数

                    参数类型应该是const list& lt的

                    但是因为我们还没有实现const迭代器,所以这里先用一下非const的引用作为参数

                    list(list& lt){//先初始化listempty_init();//然后逐个取出lt中的数据尾插到list当中即可typename list::iterator it = lt.begin();while (it != lt.end()){push_back(*it);++it;}}

                    9.赋值运算符重载

                    这里我们直接写现代写法了

                    list& operator=(list lt){swap(lt);return *this;}

                    四.const迭代器加入后的改动

                    想要加入const迭代器

                    首先想到的就是再写一个const_iterator类

                    首先我们要明白:const迭代器中const修饰的是迭代器指向的内容不能被修改

                    而通过迭代器修改数据的方式就是解引用

                    因此只需要修改一下解引用的地方即可

                    对于非const迭代器来说

                    *返回的是T&

                    ->返回的是T*

                    因此对于const迭代器来说

                    *返回的是const T&

                    ->返回的是const T*

                    同时不要忘了改一下名字

                    把iterator改为const_iterator

                    并且在list类当中实现const修饰后的begin和end

                    1.原版

                    其他的地方都跟非const迭代器一样

                    templatestruct __list_const_iterator{typedef list_node Node;typedef __list_const_iterator self;Node* _node;__list_const_iterator(Node* node):_node(node){}//T& 改为了 const T&const T& operator*(){return _node->_data;}//修改的地方://T* 改为了 const T*const T* operator->(){return &_node->_data;}};

                    templateclass list{typedef list_node Node;public:typedef __list_iterator iterator;//加上const_iteratortypedef __list_const_iterator const_iterator;iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}//实现const修饰后的begin和endconst_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}其他的成员函数,成员变量等等都不用修改....

                    不过这样的话代码就有些冗余了

                    有没有更好的方法呢?

                    设计STL的大佬就出了这么一个主意

                    2.精简版

                    既然你const迭代器和非const迭代器只有两个地方不同

                    那么我就直接把那两个地方也放到类模板当中

                    这样不就能把你们两个合并成一个类了吗?

                    Ref:reference:引用的英文Ptr:pointer:指针的英文templatestruct __list_iterator{typedef list_node Node;typedef __list_iterator self;typedef __listIterator iterator;Node* _node;__list_iterator(Node* node):_node(node){}//const_iterator和iterator的转化//支持用iterator构造const_iterator__listIterator(const iterator& it):_node(it._node){}//这里修改成了RefRef operator*(){return _node->_data;}//这里修改成了PtrPtr operator->(){return &_node->_data;}};

                    对于list类的修改

                    templateclass list{typedef list_node Node;public://把实例化的操作放在list类当中完成typedef __list_iterator iterator;typedef __list_iterator const_iterator;iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}其他的成员函数,成员变量等等都不用修改....};

                    此时const迭代器实现完毕了

                    拷贝构造就可以改回来了

                    list(const list& lt){empty_init();list::const_iterator it = lt.begin();while (it != lt.end()){push_back(*it);++it;}}

                    五.完整代码

                    #pragma once#include using namespace std;#include #include namespace wzs{templatestruct list_node{T _data;list_node* _next;list_node* _prev;list_node(const T& x = T()):_data(x), _next(nullptr), _prev(nullptr){}};templatestruct __list_iterator{typedef list_node Node;typedef __list_iterator self;typedef __listIterator iterator;Node* _node;__list_iterator(Node* node):_node(node){}//const_iterator和iterator的转化//支持用iterator构造const_iterator__listIterator(const iterator& it):_node(it._node){}self& operator++(){_node = _node->_next;return *this;}self& operator--(){_node = _node->_prev;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}//注意:一定是判断节点指针是否相等,不是迭代器是否相等!!!!bool operator!=(const self& s){return _node != s._node;}bool operator==(const self& s){return _node == s._node;}};templateclass list{typedef list_node Node;public:typedef __list_iterator iterator;typedef __list_iterator const_iterator;iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}//const迭代器搞完之后:修改为//list(const list& lt);list(const list& lt){empty_init();list::const_iterator it = lt.begin();while (it != lt.end()){push_back(*it);++it;}}void swap(list& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}//现代写法list& operator=(list lt){swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;}//超级传统版本//void clear()//{//if (!empty())//{////释放所有有效数据的节点//Node* cur = _head->_next;//while (cur != _head)//{//Node* next = cur->_next;//delete cur;//cur = next;//}////恢复成原始状态//_head->_next = _head;//_head->_prev = _head;//_size = 0;//}//}//复用erasevoid clear(){iterator it = begin();while (it != end()){it = erase(it);}}//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++;//}//复用insertvoid push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}//list的insert没有迭代器失效的问题iterator insert(iterator pos, const T& x){Node* newnode = new Node(x);Node* cur = pos._node;Node* prev = cur->_prev;newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;prev->_next = newnode;++_size;//调用iterator的构造函数构造一个新的迭代器并返回return iterator(newnode);}//list的erase有迭代器失效的问题iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;cur = nullptr;//调用iterator的构造函数构造一个新的迭代器并返回--_size;return iterator(next);}size_t size() const{return _size;}bool empty() const{return _head->_next == _head;}private:Node* _head;size_t _size;};}

                    六.补充

                    1.一个"奇怪"的现象

                    templatevoid print_list(const list& lt){list::const_iterator it = lt.begin();while (it != lt.end()){cout typename Container::const_iterator it = con.begin();while (it != con.end()){cout