C++:list增删查改模拟实现

C++:list增删查改模拟实现

• 前言
• 一、list底层双链表验证、节点构造
• • 1.1 list底层数据结构
  • 1. 2 节点构造
  • 二、迭代器封装实现（重点、难点）
  • • 2.1 前置说明
    • 2.2 迭代器实现
    • 三、list实现
    • • 3.1 基本框架
      • 3.2 迭代器和const迭代器
      • 3.2 构造函数、析构函数、拷贝构造、赋值重载
      • • 3.2.1 构造函数
        • 3.2.2 析构函数
        • 3.2.3 拷贝构造
        • 3.2.4 赋值重载
        • 3.3 任意位置插入、任意位置删除、尾插、尾删、头插、头删
        • 3.3.1任意位置插入
        • 3.3.2任意位置插入删除
        • 3.3.3 尾插、尾删、头插、头删
        • 四、list功能完善
        • • 4.1 迭代器operator->()
          • 4.2 打印数据
          • 五·、���有代码以及测试用例

            前言

            本篇博客采用SGI版本，同时考虑到看到此篇博客大部分为初学者，为此博主仅仅给出有用片段。C++:list增删查改模拟实现就是用C++复写双链表，非常简单。难点主要在迭代器实现

            一、list底层双链表验证、节点构造

            1.1 list底层数据结构

            list底层使用什么数据结构来实现的呢？我们先来看看SGI库中list的成员函数和初始化吧。

            我们发现list实现中，只有node一个成员变量。构造函数构造出一个头尾相连的哨兵位。同时验证了list底层是一个带哨兵位的双链表。

            1. 2 节点构造

            节点和双链表一样有三个成员：节点数据、指向前一个节点(prev)、指向后一个节点(next)。

            //节点templatestruct List_node{T _data;List_node* _prev;List_node* _next;List_node(const T& x = T()):_data(x),_prev(nullptr),_next(nullptr){}};

            小tips:

            1. 我们这里类名和库中一样(List_node)，后续在其他类中使用时在typedef。
            2. 这里类名使用struct而不是class原因在于struct默认访问权限为公有，后续其他类只都需要大量使用。如果使用class需要使用大量友元类，过于繁琐。

            二、迭代器封装实现（重点、难点）

            2.1 前置说明

            1. 我们知道迭代器的最大用途便是遍历数据。但何时停在，迭代器指向空间存储数据时是什么…导致我们需要使用!=、++、*等操作。但自定义类型是无法支持使用这些操作符的。为此给出的解决办法是：封装加运算符重载。
            2. 迭代器使用上分为普通迭代器和const迭代器（还分为单向迭代器、双向迭代器和随机访问迭代器）。其中一种最简单的实现方式就是实现两个类。但。。。我们知道两个迭代器的不同之处在于const迭代器无法修改数据，只是j相关借口（这里有*、->）不同而已便实现两个类未免过于“小题大做”。

               所以接下来我们来看看库中是如何巧妙的解决这个问题吧！

            2.2 迭代器实现

            前置说明中以及解决了如何实现一个类达到目的。接下来的实现过于简单就不单独说明了。

            //迭代器封装templatestruct __list_iterator{typedef List_node Node;//节点类名重命名//由于迭代器实现中,如++、--等重载函数返回值类型为__list_iterator，名字过长,这里我们重命名self意味自身typedef __list_iterator 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 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;}};

            三、list实现

            3.1 基本框架

            list模拟中，我们和库中一样，给出一个头节点_head、_size两个成员变量。同时我们将节点、迭代器进行重命名。迭代器重命名不是单纯图方便，更重要的是提供统一接口(例如sting、vector、set等接口都一样)，屏蔽底层的变量和成员函数属性，实现过程和差异。

            //list模拟实现templateclass List{typedef List_node Node;public://迭代器重命名，提供统一的接口，屏蔽底层实现细节和差异typedef __list_iterator iterator;typedef __list_iterator const_iterator;private:Node* _head;//头节点int _size;};

            3.2 迭代器和const迭代器

            下面是begin()、end()指向一个有效双线表的位置。

            实现：

            const_iterator begin()const{//return const_iterator(_head->_next);或return _head->_next;//单参数类型支持隐式类型转换}const_iterator end()const{return _head;}iterator begin(){return _head->_next;}iterator end(){return _head;}

            3.2 构造函数、析构函数、拷贝构造、赋值重载

            3.2.1 构造函数

            构造函数的实现和开头中看到的一样：构造函数中调用一个函数（empty_Init）来是实现。empty_Init()用来完成初始化。（empty_Init()函数后续其他接口也要调用）

            //初始化void empty_Init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}//无参构造List(){empty_Init();}

            3.2.2 析构函数

            析构函数我们调用一个clear函数来将数据全部清空，在将_head变量释放。

            //析构函数~List(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}

            3.2.3 拷贝构造

            拷贝构造时首先要初始化出一个节点，然后将需要拷贝的数据依次尾插即可（尾插接口后续给出实现）

            //拷贝构造List(const List& It){empty_Init();for (auto e : It){push_back(e);}}

            3.2.4 赋值重载

            赋值重载有很多方式。比较简单的参数我们直接传值，然后将待赋值的变量和传值传参省生成的临时变量的数据进行交换即可。

            void swap(const List& It){std::swap(_head, It._head);}//赋值重载List& operator=(const List It){swap(It);return *this;}

            3.3 任意位置插入、任意位置删除、尾插、尾删、头插、头删

            3.3.1任意位置插入

            首先new出待插入节点newnode，然后将pos前一个节点prev、newnode、pos相连。最后++_size即可。

            iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;_size++;return newnode;}

            3.3.2任意位置插入删除

            将待删除数据的前后节点先保存起来，然后将删除pos处节点，再将前后节点连接起来。最后–_size即可。

            iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;delete cur;prev->_next = next;next->_prev = prev;_size--;return next;}

            3.3.3 尾插、尾删、头插、头删

            尾插、尾删、头插、头删都是复用任意位置插入、任意位置删除接口。

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

            四、list功能完善

            4.1 迭代器operator->()

            我们先来看看下面这段代码对吗？

            struct AA{AA(int a1 = 0, int a2 = 0):_a1(a1),_a2(a2){}int _a1;int _a2;};void test_list3(){list lt;lt.push_back(AA(1, 1));lt.push_back(AA(2, 2));lt.push_back(AA(3, 3));list::iterator it = lt.begin();while (it != lt.end()){coutAA(int a1 = 0, int a2 = 0):_a1(a1),_a2(a2){}int _a1;int _a2;};void test_list3(){list//cout // listcout typename Container::const_iterator it = con.begin();while (it != con.end()){cout