C，list增删查改模拟成功前言一、list底层双链表验证、节点结构1.1list底层数据结构1.2节点结构二、迭代器封装成功，重点、难点，2.1前置说明2.2迭代器成功三、list成功3.1基本框架3.2迭代器和const迭代器3.2结构函数、析构函数、拷贝结构、赋值重载3.2.1结构函数3.2.2析构函数3.2.3拷贝结构3....。

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的成员函数和初始化吧。

1. 2 节点结构

//节点
templateclass T
struct List_nodeT _dataList_nodeT _prevList_nodeT _nextList_nodeconst T x  T_datax_prevnullptr_nextnullptr

小tips:

1. 咱们这里类名和库中一样(List_node)，后续在其余类中经常使用时在typedef。

2. 这里类名经常使用struct而不是class要素在于struct自动访问权限为私有，后续其余类只都须要少量经常使用。假设经常使用class须要经常使用少量友元类，过于繁琐。

   二、迭代器封装成功（重点、难点）

2.1 前置说明

1. 咱们知道迭代器的最大用途便是遍历数据。但何时停在，迭代器指向空间存储数据时是什么…造成咱们须要经常使用!=、++、*等操作。 但自定义类型是不可支持经常使用这些操作符的。为此给出的处置方法是： 封装加运算符重载 。
2. 迭代器经常使用上分为普通迭代器和const迭代器（还分为单向迭代器、双向迭代器和随机访问迭代器）。其中一种最繁难的成功形式就是成功两个类。但。。。 咱们知道两个迭代器的不同之处在于const迭代器不可修负数据，只是j关系借口（这里有*、->）不同而已便成功两个类难免过于“小题大做”。
   所以接上去咱们来看看库中是如何奇妙的处置这个疑问吧！

2.2 迭代器成功

前置说明中以及处置了如何成功一个类到达目的。接上去的成功过于繁难就不独自说明了。

//迭代器封装
templateclass T class Ref class Ptr
struct __list_iteratortypedef List_nodeT Node//节点类名重命名//因为迭代器成功中,如++、--等重载函数前往值类型为__list_iterator，名字过长,这里咱们重命名self象征自身typedef __list_iteratorTRef Ptr selfNode _node//成员变量__list_iteratorNode node//结构出一个节点_nodenode//前置++self operator_node  _node_nextreturn this//前置--self operator_node  _node_prevreturn this//后置++self operatorintself tmpthis_node  _node_nextreturn tmp//后置--self operatorintself tmpthis_node  _node_prevreturn tmp//解援用操作符重载Ref operatorreturn _node_data//用于访问迭代器指向对象中存储的是自定义类型Ptr operatorreturn _node_databool operatorconst self sreturn _node  s_nodebool operatorconst self sreturn _node  s_node

三、list成功

3.1 基本框架

list模拟中，咱们和库中一样，给出一个头节点_head、_size两个成员变量。同时咱们将节点、迭代器启动重命名。 迭代重视命名不是单纯图繁难，更关键的是提供一致接口(例如sting、vector、set等接口都一样)，屏蔽底层的变量和成员函数属性，成功环节和差异。

//list模拟成功
templateclass T
class Listtypedef List_nodeT Node
public//迭代重视命名，提供一致的接口，屏蔽底层成功细节和差异typedef __list_iteratorT T T iteratortypedef __list_iteratorT const T const T const_iterator
privateNode _head//头节点int _size

3.2 迭代器和const迭代器

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

成功：

const_iterator beginconst//return const_iterator(_head->_next);或return _head_next//单参数类型支持隐式类型转换const_iterator endconstreturn _headiterator beginreturn _head_nextiterator endreturn _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//无参结构
Listempty_Init

3.2.2 析构函数

析构函数咱们调用一个clear函数来将数据所有清空，在将_head变量监禁。

//析构函数
Listcleardelete _head_head  nullptrvoid cleariterator it  beginwhile it  endit  eraseit

3.2.3 拷贝结构

拷贝结构时首先要初始化出一个节点，而后将须要拷贝的数据依次尾插即可（尾插接口后续给出成功）

//拷贝结构
Listconst ListT Itempty_Initfor auto e  Itpush_back<img alt="list增删查改模拟成功" loading="lazy" src="https://www.jsdaima.com/kindeditor/attached/image/20180303/20180303172117_98444.jpg"></img>e

3.2.4 赋值重载

赋值重载有很多形式。比拟繁难的参数咱们间接传值，而后将待赋值的变量和传值传参省生成的暂时变量的数据启动替换即可。

void swapconst ListT Itstdswap_head It_head//赋值重载
ListT operatorconst ListT ItswapItreturn this

3.3 恣意位置拔出、恣意位置删除、尾插、尾删、头插、头删

3.3.1恣意位置拔出

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

iterator insertiterator pos const T xNode cur  pos_nodeNode prev  cur_prevNode newnode  new Nodexprev_next  newnodenewnode_prev  prevnewnode_next  curcur_prev  newnode_sizereturn newnode

3.3.2恣意位置拔出删除

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

iterator eraseiterator posNode cur  pos_nodeNode prev  cur_prevNode next  cur_nextdelete curprev_next  nextnext_prev  prev_sizereturn next

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

尾插、尾删、头插、头删都是复用恣意位置拔出、恣意位置删除接口。

void push_backconst T xinsertend xvoid push_frontconst T xinsertbegin xvoid pop_backeraseendvoid pop_fronterasebegin

四、list性能完善

4.1 迭代器operator->()

咱们先来看看上方这段代码对吗？

struct AAAAint a1  0 int a2  0_a1a1_a2a2int _a1int _a2void test_list3listAA ltltpush_backAA1 1ltpush_backAA2 2ltpush_backAA3 3listAAiterator it  ltbeginwhile it  ltendcoutititcout  endl

所以关于自定义类型咱们可以先解援用在去访问成员，也可以 在迭代器中重载operator->()函数。但须要留意的是编译器暗藏了一个->，详细原生行为如下：

struct AAAAint a1  0 int a2  0_a1a1_a2a2int _a1int _a2void test_list3listAA ltltpush_backAA1 1ltpush_backAA2 2ltpush_backAA3 3listAAiterator it  ltbeginwhile it  ltend//cout << (*it)._a1<<" "<<(*it)._a2 << endl;cout  it_a1    it_a2  endl//上方编译器访问成员变量的真正行为如下：//cout << it.operator->()->_a1 << " " << it.operator->()->_a1 << endl;itcout  endl

4.2 打印数据

//大少数状况模板是class还是typename是一样的，但当有未实例化模板时，必定经常使用typename
//template<typename T>
void print_listconst listT lt// list<T>未实例化的类模板，编译器不能去他外面去找// 编译器就不可list<T>::const_iterator是内嵌类型，还是静态成员变量// 前面加一个typename就是通知编译器，这里是一个类型，等list<T>实例化// 再去类外面去取typename listTconst_iterator it  ltbeginwhile it  ltendcout  it  itcout  endl  

优化：上方打印数据是针对list，上方是针对容器的。

// 模板(泛型编程)实质，原本应该由咱们干的活交给编译器
templatetypename Container
void print_containerconst Container contypename Containerconst_iterator it  conbeginwhile it  conendcout  it  itcout  endl

五·、一切代码以及测试用例

giteeC++:list增删查改模拟实现代码以及测试用例
介绍：giteeC++:list增删查改模拟实现代码（最终版本、觉得版本！！！）