【CPP】slt-list由认识到简化模拟实现深度理解~-阿里云开发者社区

关于我：

睡觉待开机：个人主页个人专栏: 《优选算法》《C语言》《CPP》生活的理想，就是为了理想的生活!作者留言

PDF版免费提供：倘若有需要，想拿我写的博客进行学习和交流，可以私信我将免费提供PDF版。

留下你的建议：倘若你发现本文中的内容和配图有任何错误或改进建议，请直接评论或者私信。

倡导提问与交流：关于本文任何不明之处，请及时评论和私信，看到即回复。

1.前言

今天简单分享一下STL中的一大容器——List

先介绍后模拟

在这里我会先以CPP文档为样去介绍其中比较重点的函数接口，之后我会简单的去模拟实现并详细介绍为什么去这样写，期间会配有一些图片和说文便于读者理解。

但请注意模拟实现的list是一个尽可能对STL源码进行精简的版本，可以说存在相当大的缺陷和漏洞，但我想对于了解list基本底层而言，这是足够的。

2.list简介

文档链接：LIST

std::list

template < class T, class Alloc = allocator > class list;

list是一个带头双向循环链表并且允许O(1)时间复杂度内插入或者删除一个结点。

我们该怎么理解带头双向循环链表呢？

带头：指的是带哨兵位结点的链表，这个哨兵位仅仅是用来方便对链表操作而额外申请的空间，并不表示有效数据。

双向：指的是链表的指向方向是双向的，也就是对于指向一个结点的指针，既可以向前走，找到他的前一个结点，也可以向后走，找到它的后一个结点。

循环：循环，就是链表可以抽象为一个环，即首尾相连，可以理解为哨兵位的前一个结点指向最后一个结点，最后一个结点的后一个结点是哨兵位。

链表：是一种数据结构，线性表的一种，是逻辑结构是线性但是物理逻辑不是线性的一种线性表。具体是怎么样的，我想可以参考后文中的链表抽象图。

好的，简单了解了带头双向链表的意思，我们简单介绍一下相关接口的使用。

3.list重点接口

重点函数，测试功能代码

在这一段落中，我并非将每个函数面面俱到去说的很详细，也不会很全面，我只提及我认为比较容易出错或者重要也或者说是常用的函数接口，同时给出测试代码来验证这个函数的相关功能。

3.1构造函数constructor

//无参构造
list<int> l1;
//n个val构造
list<int> l2(10, 1);
//迭代器构造
list<int> l3(l2.begin(), l2.end());
//拷贝构造
list<int> l4(l3);
for (auto& node : l1)
{
    cout << node << " ";
}
cout << endl;
for (auto& node : l2)
{
    cout << node << " ";
}
cout << endl;
for (auto& node : l3)
{
    cout << node << " ";
}
cout << endl;
for (auto& node : l4)
{
    cout << node << " ";
}
cout << endl;

3.2operator=

list<int> l1;
list<int> l2(10, 6);
l1 = l2;
for (auto& node : l1)
{
  cout << node << " ";
}
cout << endl;
for (auto& node : l2)
{
  cout << node << " ";
}

3.3max_size

list<int> l;
cout << l.max_size() << endl;
//结果：768614336404564650

3.4assigne重写

//assign
list<int> al(5, 6);
list<int> l(10, 1);
//支持迭代器重写
l.assign(al.begin(), al.end());
for (auto& node : l)
{
  cout << node << " ";
}
cout << endl;
//也支持n个val值重写
l.assign(12, 3);
for (auto& node : l)
{
  cout << node << " ";
}
cout << endl;

3.5insert

//insert
list<int> l(3, 3);
for (auto& node : l)
{
    cout << node << " ";
}//3 3 3
cout << endl;
//支持单个值插入
l.insert(l.begin(), 0);
for (auto& node : l)
{
    cout << node << " ";
}//0 3 3 3
cout << endl;
//支持插入n个val值插入
l.insert(l.end(), 4, 4);
for (auto& node : l)
{
    cout << node << " ";
}//0 3 3 3 4 4 4 4
cout << endl;
//支持迭代器插入一段区间
list<int> cl(6, 6);
l.insert(l.end(), cl.begin(), cl.end());
l.insert(l.end(), 4, 4);
for (auto& node : l)
{
    cout << node << " ";
}//0 3 3 3 4 4 4 4 6 6 6 6 6 6 4 4 4 4
cout << endl;

问题：我们vector中insert会引发迭代器失效问题，我们list中的insert会有迭代器失效问题吗？为什么？
答：不会。这是由底层结构决定的。

同理，erase也会引起vector失效，但是对于list就不会引起迭代器失效问题。

3.6splice转移

//splice 转移
//把一个链表转移到另一个链表
list<int> l;
list<int> l2(10, 6);
l.splice(l.begin(), l2);
cout << 'l' << ":" << endl;
for (auto& node : l)
{
    cout << node << " ";
}
cout << endl;
cout << "l2" << ":" << endl;
for (auto& node : l2)
{
    cout << node << " ";
}
cout << endl;

//把一个链表的一个元素转移给另一个链表
list<int> l;
list<int> l2(10, 6);
l.splice(l.begin(), l2, l2.begin());
cout << 'l' << ":" << endl;
for (auto& node : l)
{
  cout << node << " ";
}
cout << endl;
cout << "l2" << ":" << endl;
for (auto& node : l2)
{
  cout << node << " ";
}
cout << endl;

//把一个链表的一部分转移给另一个链表
list<int> l;
list<int> l2(10, 6);
l.splice(l.begin(), l2, ++l2.begin(),l2.end());
cout << 'l' << ":" << endl;
for (auto& node : l)
{
  cout << node << " ";
}
cout << endl;
cout << "l2" << ":" << endl;
for (auto& node : l2)
{
  cout << node << " ";
}
cout << endl;

3.7remove

list<int> l(10, 1);
l.remove(1);
for (auto& node : l)
{
  cout << node << " ";
}//输出为空
cout << endl;

3.8unique去重

//list未排序情况下使用去重unique
list<int> l;
l.push_back(1);
l.push_back(3);
l.push_back(3);
l.push_back(2);
l.push_back(3);
l.push_back(4);
l.unique();
for (auto& node : l)
{
  cout << node << " ";
}//1 3 2 3 4
cout << endl;

//list排序情况下使用去重unique
list<int> l;
l.push_back(1);
l.push_back(3);
l.push_back(3);
l.push_back(2);
l.push_back(3);
l.push_back(4);
l.sort();
l.unique();
for (auto& node : l)
{
  cout << node << " ";
}//1 2 3 4
cout << endl;

3.9merge合并

//未排序使用merge
list<int> l1;
l1.push_back(1);
l1.push_back(3);
l1.push_back(4);
l1.push_back(1);
list<int> l2;
l2.push_back(1);
l2.push_back(3);
l2.push_back(4);
l2.push_back(1);
l1.merge(l2);//assert断言错误
for (auto& node : l1)
{
  cout << node << " ";
}
cout << endl;
for (auto& node : l2)
{
  cout << node << " ";
}
cout << endl;

//未排序使用merge
list<int> l1;
l1.push_back(1);
l1.push_back(3);
l1.push_back(4);
l1.push_back(1);
l1.sort();
list<int> l2;
l2.push_back(1);
l2.push_back(3);
l2.push_back(4);
l2.push_back(1);
l2.sort();
l1.merge(l2);//assert断言错误
for (auto& node : l1)
{
  cout << node << " ";
}//1 1 1 1 3 3 4 4
cout << endl;
for (auto& node : l2)
{
  cout << node << " ";
}//空
cout << endl;

//未排序使用merge
list<int> l1;
l1.push_back(1);
l1.push_back(3);
l1.push_back(4);
l1.push_back(1);
l1.sort(greater<int>());
list<int> l2;
l2.push_back(1);
l2.push_back(3);
l2.push_back(4);
l2.push_back(1);
l2.sort(greater<int>());
l1.merge(l2, greater<int>());//com函数必须提供由sort的一致，不然断言错误
for (auto& node : l1)
{
  cout << node << " ";
}//4 4 3 3 1 1 1 1
cout << endl;
for (auto& node : l2)
{
  cout << node << " ";
}//空
cout << endl;

3.10sort排序

排序效率一般：这里需要重点强调一下list中的sort排序和vector中的sort排序效率差距还是挺大的，建议数据量比较大的话有条件就用vector进行排序，即使是从list把数据拷贝到vector再拷贝回list

list提供了自己的sort排序接口：

//sort
list<int> l;
l.push_back(1);
l.push_back(3);
l.push_back(2);
l.push_back(5);
l.push_back(4);
l.sort();
for (auto& node : l)
{
  cout << node << " ";
}//1 2 3 4 5
cout << endl;

void test_op1()
{
  srand(time(0));
  const int N = 1000000;//一百万数据
  //两个链表
  list<int> lt1;
  list<int> lt2;
  //一个顺序表
  vector<int> v;
  //生成随机数据，尾插到链表1和顺序表v中去
  for (int i = 0; i < N; ++i)
  {
    auto e = rand() + i;//加上这个i主要是为了减少重复数字概率
    lt1.push_back(e);
    v.push_back(e);
  }
  //vector排序
  int begin1 = clock();
  sort(v.begin(), v.end());
  int end1 = clock();
  //list排序
  int begin2 = clock();
  lt1.sort();
  int end2 = clock();
  //打印比较两者用时
  printf("vector sort:%d\n", end1 - begin1);
  printf("list sort:%d\n", end2 - begin2);
  //vector sort : 253
  //list sort : 411
}

void test_op2()
{
  srand(time(0));//种子
  const int count = 1000000;
  
  //两个链表
  list<int> l1;
  list<int> l2;
  //制造数据并加入到l1和l2中
  for (int i = 0; i < count; i++)
  {
    int n = rand();
    l1.push_back(n);
    l2.push_back(n);
  }
  //l1自己排序
  size_t begin1 = clock();
  l1.sort();
  size_t end1 = clock();
  //让l2先把数据拷贝到v中，再在v中进行排序，之后拷贝回l2中
  size_t begin2 = clock();
  vector<int> v(l2.begin(), l2.end());
  sort(v.begin(), v.end());
  l1.insert(l1.begin(), v.begin(), v.end());
  size_t end2 = clock();
  
  cout << end1 - begin1 << endl;//755
  cout << end2 - begin2 << endl;//520
}

结论：数据量比较大的时候尽量少用list进行排序。

4.快速模拟最基本的list

我们去模拟一个东西，应该先去搞出这个东西的大致框架，然后再去逐渐完善，在这里我就很简单的写一个list模拟实现。

请注意，这里仅供参考，list都有不同的实现方式，且本模拟实现仅是个框架。

我们知道写代码的过程往往十分复杂，即使是一个几百行的简单项目，用图文的形式呈现出来更是需要大量的篇幅。基于此，我将不再叙说我写的时候走过的弯路，直接是用一气呵成的顺序，按照逻辑一步一步呈现相关内容。

4.1自定义命名空间域和list成员变量

我们知道，模拟写链表类最好先写一个自定义命名空间域，这样不容易与其他写的代码相冲突。

同时，我们想链表中最重要的肯定就是相关的成员变量，那链表中需要用到的只有一个，即头节点指针。

namespace szg
{
template<class T>
class list
{
private:
    node* _head;
}
}

但是这个头节点指针是CPP本身就有的吗？显然不是，所以我们要去写一个node的自定义类型：

4.2node的自定义

template<class T>
struct ListNode
{
  T _val;
  struct ListNode* _prev;
  struct ListNode* _next;
  //ListNode的构造函数
  ListNode(const T& x = T())
    :_next(nullptr)
    , _prev(nullptr)
    , _val(x)
  {}
};

在上面struct ListNode的类，就是我写的关于node的自定义类型及其相关构造函数，这里请思考一下：

ListNode的成员变量为什么是prev和next两个指针呢？ 因为我们要写的是双向链表，对于每个结点而言都需要去存储前一个结点的地址和后一个结点的地址，结点本身还要存储上自己的数据val这样才可以。

ListNode的构造函数为什么这样写？ 因为函数头参数给缺省值是更加方便构建结点，同时对于一个新节点来说，前后指针都应指向空，方便后续操作，而val则应该放上对应的数值。

好，处理完node结点问题，然后我们继续来写我们的链表。

写好了ListNode类，我们得把他用起来啊，但是我们的list类中写的是node!=ListNode，这里只需要typedef一下就行了：

namespace szg
{
template<class T>
class list
{
private:
  typedef ListNode<T> node;
  node* _head;
}
}

在这个地方，我想补充一个知识点：

CPP中类中内嵌类型。 什么是类中内嵌类型呢？就是在一个类的内部可以直接调用的类型，特指自定义类型，比如我们上面说的ListNode类就是list的一个内嵌类型。

一般而言，定义类中内嵌类型的方法有两个，一个是在类外定义的自定义类，在要使用的类中typedef一下就行，还有一种方法就是直接定义内部类的方法。

习惯上，我们CPP更加习惯于前者，后者是JAVA常用的手段。

写好了上面代码，我们继续来写list的无参构造函数。

4.3list::list()无参构造

我是这样写的：

在list中：

//无参构造函数
list()
{
  empty_initialization();
}
void empty_initialization()
{
  _head = new node;
  _head->_next = _head;
  _head->_prev = _head;
}

这里调用了一次空初始化函数哈，因为STL库中直接嵌套了四五层，这里就是模拟一下样子就好。

empty_initialization()中，我们肯定是得先new一个node空间，因为无参构造出的链表只有一个哨兵结点，所以让哨兵位的next指向他自己，哨兵位的prev也指向他自己就好了。

4.4list::push_back()

我们得实现一个插入结点的接口才行，所以这里我们实现最简单的尾插接口：

代码如下：

//push_back
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++;
}

我们想要新插入一个结点，

函数参数：因为我不知道你要插入结点的val值是多少，所以你得给到我，设计上参数const T& x用来接收val数据
函数体：逻辑肯定是先开空间，再把这个结点融合到链表中。

new一个空间，取名为newnode
再把newnode融合到链表中，

让原先链表的最后一个结点的后继指针指向newnode
再让newnode的前驱指针指向原先链表的最后一个结点
newnode的后继指针指向哨兵位
哨兵位的前驱指针指向newnode

好的，这样整体上就完成了push_back()的逻辑。

然后我们稍微测试一下我们写的是否正确，当然需要打印出来，因此需要写一个迭代器去访问测试一下。

4.5list::迭代器的设计

但是这里有个问题：迭代器怎么写？？？用原生指针typedef一下吗？

当然不行。

在vector中，用原生指针充当迭代器是完全可以的，但是对于list，原生指针++或者–操作之后，会指向内存的下一块区域，问题就是list在内存中实际的存储是不确定的。

重要的原因在于，这个原生指针++、–操作之后的行为不是我们想要的，如果我们可以修改他的++、–行为岂不是很好吗？
于是，我们将原生指针封装为一个类，重载他的运算符，就解决了这个问题。本质上，封装原生指针就是为了扩大我们对指针的控制权限。

思考之后，我写出了下面的代码：

template<class T>
struct ListIterator
{
public:
  typedef ListNode<T> node;
  node* _iterator;
}

好，我们开始重载他的运算符。

不过在这之前，我们得先把这个迭代器的构造函数写一下。

//itrator构造
ListIterator(node* node)
  :_iterator(node)
{}

之后我们重载他的相关运算符：包括解引用、加加、减减、等于和不等于。

public:
  node* GetIterator()
  {
    return _iterator;
  }
  node* GetIterator() const
  {
    return _iterator;
  }
//解引用重载
T& operator* ()
{
  return _iterator->_val;
}
//前置++重载
ListIterator<T>& operator++()
{
  _iterator = _iterator->_next;
  return *this;
}
//后置++重载
ListIterator<T> operator++(int)
{
  ListIterator<T> temp(*this); // 构建一个临时对象
  _iterator = _iterator->_next; // 让当前this指向下一个结点
  return temp; // 但是返回临时变量
}
//!=重载
bool operator!=(const ListIterator<T>& l)
{
  return this->_iterator != l.GetIterator();
}
//==重载
bool operator==(const ListIterator<T>& l)
{
  return this->_iterator == l.GetIterator();
}

为了便于大家理解，我在这里提出下面几个问题帮助大家进一步理解上面代码：

为什么list的迭代器需要对原生指针进行封装？答：为了重载他的操作符
迭代器需要写构造函数和拷贝构造函数吗？为什么？构造函数需要写，拷贝构造不用谢，因为编译器自动浅拷贝。
迭代器需要写析构函数吗？不用，因为迭代器不用考虑结点的释放，释放结点属于list的工作
迭代器什么操作符需要进行重载？根据需要和实际意义，比如在当前场景下迭代器重载大于和小于就没有什么实际意义，可以选择不重载。
上面我们写的iterator类准确来说是类型还是迭代器？是迭代器类型，迭代器是在list中实现的。

好的，相必大家已经了解了上面所说的要点，那我们回到list并为list写上一个简单的迭代器。

template<class T>
class list
{
private:
  typedef ListNode<T> node;
  typedef ListIterator<T> iterator;
  node* _head;
public:
  //无参构造函数
  void empty_initialization()
  {
    _head = new node;
    _head->_next = _head;
    _head->_prev = _head;
  }
  list()
  {
    empty_initialization();
  }
  //基本迭代器
  iterator begin()//迭代器怎么不返回引用呢？begin()默认指向第一个有效节点
  {
    return iterator(_head->_next);//返回匿名对象
  }
  iterator end()
  {
    return iterator(_head);//返回匿名对象
  }
  //push_back
  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++;
  }
};

上面代码中的begin和end函数才是我们说的迭代器。

请思考一下为什么这个begin和end的返回类型是iterator，而不能是iterator&，为什么是迭代器值返回，而不是引用返回呢，毕竟引用返回效率更高啊？

因为迭代器如果返回引用，就会造成很大的问题，毕竟外界可以修改begin和end，这也就会造成begin/end的指向错误。

我用下面例子来进行说明：

至此，我们写出了下面代码：

4.6小总结

#include<iostream>
namespace szg
{
  template<class T>
  struct ListNode
  {
    T _val;
    struct ListNode* _prev;
    struct ListNode* _next;
    //ListNode的构造函数
    ListNode(const T& x = T())
      :_next(nullptr)
      , _prev(nullptr)
      , _val(x)
    {}
  };
  template<class T>
  struct ListIterator
  {
  public:
    typedef ListNode<T> node;
    node* _iterator;
  public:
    //itrator构造
    ListIterator(node* node)
      :_iterator(node)
    {}
    //解引用重载
    T& operator* ()
    {
      return _iterator->_val;
    }
    //前置++重载
    ListIterator<T>& operator++()
    {
      _iterator = _iterator->_next;
      return *this;
    }
    //后置++重载
    ListIterator<T> operator++(int)
    {
      ListIterator<T> temp(*this); // 构建一个临时对象
      _iterator = _iterator->_next; // 让当前this指向下一个结点
      return temp; // 但是返回临时变量
    }
    //!=重载
    bool operator!=(const ListIterator<T>& l)
    {
      return this->_iterator != l._iterator;
    }
    //==重载
    bool operator==(const ListIterator<T>& l)
    {
      return this->_iterator == l._iterator;
    }
  };
  template<class T>
  class list
  {
  private:
    typedef ListNode<T> node;
    typedef ListIterator<T> iterator;
    node* _head;
    size_t _size;
  public:
    //无参构造函数
    void empty_initialization()
    {
      _head = new node;
      _head->_next = _head;
      _head->_prev = _head;
      _size = 0;
    }
    list()
    {
      empty_initialization();
    }
    //基本迭代器
    iterator begin()//迭代器怎么不返回引用呢？begin()默认指向第一个有效节点
    {
      return iterator(_head->_next);//返回匿名对象
    }
    iterator end()
    {
      return iterator(_head);//返回匿名对象
    }
    //push_back
    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++;
    }
  };
}

我们不妨来测试一下是否能够正常运行>>

//test.cpp
#include"List.h"
int main()
{
  szg::list<int> l;
  l.push_back(1);
  l.push_back(2);
  l.push_back(3);
  l.push_back(4);
  //访问
  szg::ListIterator<int> it = l.begin();
  while (it != l.end())
  {
    std::cout << *it << " ";
    it++;
  }
  std::cout << std::endl;
  return 0;
}

输出结果：

5.进一步完善list

这一部分内容很简单，没有什么难理解的地方，无非就是大量复用已经实现的接口。在这里我就不再依次进行详述。

5.1list的insert函数接口实现

我们结合CPP文档中insert的功能，我们需要先传入一个迭代器指定位置，之后传入要插入的x数值。

经过思考，我们可以这样实现代码：

//inser
void insert(iterator pos, const T& x)
{
  // 开空间
  node* newnode = new node(x);
  // 记录一下位置
  node* prev = pos._iterator->_prev;
  node* pcur = pos._iterator;
  // 组织逻辑
  newnode->_next = pcur;
  pcur->_prev = newnode;
  newnode->_prev = prev;
  prev->_next = newnode;
}

思考：这个地方为啥是node* prev;node* pcur???不能用iterator类型吗？

答：也可以写成iterator，只不过写成node*后面组织逻辑得时候更加方便而已。

5.2list::size()

这个函数的功能主要是返回当前list中所剩结点的个数，不包含哨兵结点。

这里有两种方案，一是list成员变量中新加入_size，但是请注意每次插入新节点时候要_size++

//size()
size_t size()//返回当前的结点数量
{
  return _size;
}

第二种方案就是遍历链表进行计数即可，这里不再多说。

5.3list::erase()

要实现erase功能，我们可以这样实现代码：

//erase()
iterator erase(iterator pos)
{
  node* cur = pos._iterator;
  node* prev = cur->_prev;
  node* next = cur->_next;
  prev->_next = next;
  next->_prev = prev;
  delete cur;
  _size--;//记得要更新_size的数值
  return iterator(next);
}

5.4pop_back,pop_front,push_back,push_front

pop_back,pop_front,push_back,push_front这些函数都可以复用insert或者erase，这里我们进行复用一下：

//push_back
//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++;
//}
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());
}

这里之前写的push_back()注释一下，我们一致复用insert就行了。

6.完善迭代器

实际上，我们之前写的迭代器只是个半成品，比如const迭代器不支持。还比如不够灵活，operator->就没有支持。

下面重点详细介绍，这才是本节博客的精华所在，请诸君静听。

6.1operator->的理解

对于自定义类型

struct A
{
  int _a;
  int _b;
  //构造函数
  A(const int& a = 0, const int& b = 0)
  {
    _a = a;
    _b = b;
  }
};

我想弄个list<A>请问此时应该怎么进行数据遍历呢？

可能你会写出下面的代码：

szg::list<A> la;
A a(1, 1);
la.push_back(a); // 有名对象尾插
la.push_back(A(2,2)); // 匿名对象尾插
la.push_back({3,3}); // CPP11新语法，多参数隐式类型转换
//访问
szg::ListIterator<A> itA = la.begin();
while (itA != la.end())
{
  std::cout << (*itA)._a << " ";
  std::cout << (*itA)._b << " ";
  itA++;
}
std::cout << std::endl;

总感觉很奇怪，但是这是正确的。

倘若这不是struct A，而是class A呢？？？有人可能会说提供Get_A和Get_B函数，一般CPP中不习惯写Get函数，这种JAVA是常用这样的方法的。

CPP会重载一个operator->去解决这个问题。

在ListIterator类中，我们可以写下下面代码：

T* operator->()//返回对应val值的地址
{
  return &_iterator->_val;
}

之后，我们可以这样写Test：

struct A
{
  int _a;
  int _b;
  //构造函数
  A(const int a = 0, const int b = 0)
  {
    _a = a;
    _b = b;
  }
};

szg::list<A> la;
A a(1, 1);
la.push_back(a); // 有名对象尾插
la.push_back(A(2,2)); // 匿名对象尾插
la.push_back({3,3}); // CPP11新语法，多参数隐式类型转换
//访问
szg::list<A>::iterator it = la.begin();
while (it != la.end())
{
  /*std::cout << (*itA)._a << " ";
  std::cout << (*itA)._b << " ";*/
  //std::cout << (*it)._a << " ";
  std::cout << it->_a << " ";
  std::cout << it->_b << " ";
    it++;
}
std::cout << std::endl;

这里需要注意的是，在我们调用operator的时候，编译器对其做了优化，按照逻辑我们需要写为it.operator->()->_a，这里我们可以少写一个->，更加符合我们的使用习惯。

6.2const迭代器

不知道大家发现了没有，一直以来都没用过const迭代器去遍历，实际上，在上面所写的代码中就完全没有const的影子，如果用const迭代器就会报语法错误，因为压根没有实现。

倘若你认为这样写：

那我可以告诉你这样的const迭代器跟非const是一样的行为，一样可以修改迭代器指向的内容。

辨析：

const迭代器和非const迭代器的区别？？？
const迭代器不可修改迭代器指向的内容，非const迭代器可以修改迭代器指向元素的内容。

倘若你灵机一动，说改成这样：

那么你这样就是让迭代器本身不可更改，而不是迭代器指向的内容不可更改。

实际上，想要正确写出const迭代器有两种方法：一是再写一个const_iterator迭代器类，再一个就是把const作为一个参数传入ListIterator中，让其根据模板自动生成一份const迭代器类。

下面来依次介绍两种方法：

对于两种方法，都是重新写一个类而已，只不过前者是自己写，后置式让编译器根据模板进行推导罢了。

template<class T>
struct ConstListIterator
{
  typedef ListNode<T> node;
  const node* _iterator;
  //itrator构造
  ConstListIterator(const node* node)
    :_iterator(node)
  {}
  //解引用重载
  const T& operator* ()const
  {
    return _iterator->_val;
  }
  const T* operator-> ()const//返回对应val值的地址
  {
    return &_iterator->_val;
  }
  //前置++重载
  ConstListIterator<T>& operator++()
  {
    _iterator = _iterator->_next;
    return *this;
  }
  //后置++重载
  //ConstListIterator<T> operator++(int)
  //{
  //  ListIterator<T> temp(*this); // 构建一个临时对象
  //  _iterator = _iterator->_next; // 让当前this指向下一个结点
  //  return temp; // 但是返回临时变量
  //} //error：temp类型错误。
  ConstListIterator<T> operator++(int)
  {
    ConstListIterator<T> tmp(*this);
    _iterator = _iterator->_next;
    return tmp;
  }
  //!=重载
  bool operator!=(const ConstListIterator<T>& l)
  {
    //return this->_iterator != l._iterator;
    return _iterator != l._iterator;
  }
  //==重载
  bool operator==(const ListIterator<T>& l)
  {
    return this->_iterator == l._iterator;
  }
};

上面就是一个写好的const迭代器类，请注意：在list中使用的时候也要用typedef更改一下名字，这样struct ConstListIterator就成为了List类中的内部类，自由使用了。

简单测试：

//test
szg::list<int> li;
li.push_back(1);
li.push_back(2);
li.push_back(3);
li.push_back(4);
li.push_back(5);
const szg::list<int> li2 = li;
szg::list<int>::const_iterator it = li2.begin();
while (it != li2.end())
{
  std::cout << *it << " ";
  it++;
}
std::cout << std::endl;

当然，我们也可以用第二种方式让编译器为我们写const迭代器：

template<class T, class Ref, class Pon>
struct ListIterator
{
public:
  typedef ListNode<T> node;
  node* _iterator;
public:
  //itrator构造
  ListIterator(node* node)
    :_iterator(node)
  {}
  //解引用重载
  Ref operator* ()
  {
    return _iterator->_val;
  }
  Pon operator-> ()//返回对应val值的地址
  {
    return &_iterator->_val;
  }
  //前置++重载
  ListIterator<T, Ref, Pon>& operator++()
  {
    _iterator = _iterator->_next;
    return *this;
  }
  //后置++重载
  ListIterator<T, Ref, Pon> operator++(int)
  {
    ListIterator<T, Ref, Pon> temp(*this); // 构建一个临时对象
    _iterator = _iterator->_next; // 让当前this指向下一个结点
    return temp; // 但是返回临时变量
  }
  //!=重载
  bool operator!=(const ListIterator<T, Ref, Pon>& l)
  {
    return this->_iterator != l._iterator;
  }
  //==重载
  bool operator==(const ListIterator<T, Ref, Pon>& l)
  {
    return this->_iterator == l._iterator;
  }
};

7.析构、拷贝构造、赋值运算符重载

7.1析构函数

~list()
{
  clear();//释放链表内容
  delete _head;//释放哨兵结点
  _head = nullptr;//置空
  _size = 0;//归零
}
void clear()
{
  iterator it = begin();
  while (it != end())
  {
    it = erase(it);
  }
}

7.2拷贝构造

注意，这个需要深拷贝，不然析构时候会析构两次出现问题。

list(const list<T>& l)
{
  empty_initialization();//申请一个哨兵位
  for (auto& node : l)//然后一直尾插数据
  {
    push_back(node);
  }
}

7.3赋值运算符重载

//赋值运算符重载
list<T>& operator=(const list<T>& l)
{
  clear();//清空内容，此时还有头节点
  const_iterator it = l.begin();//依次尾插
  while (it != l.end())
  {
    push_back(*it);
    it++;
  }
  return *this;
}

当然，也可以这样写去复用拷贝构造也行。

void swap(list<T>& l)
{
  std::swap(_head, l._head);
  std::swap(_size, l._size);
}
//赋值运算符重载
list<T>& operator=(list<T> l)
{
  swap(l);
  return *this;
}

好的，到这里我们基本就把list简化模拟实现完成了。我感觉总体来说还是稍微有点麻烦的，毕竟自己写的时候老是写着写着进到坑里去了…

好的，如果本篇文章对你有帮助，不妨点个赞~谢谢。

EOF

【CPP】slt-list由认识到简化模拟实现深度理解~

1.前言

2.list简介

3.list重点接口

3.1构造函数constructor

3.2operator=

3.3max_size

3.4assigne重写

3.5insert

3.6splice转移

3.7remove

3.8unique去重

3.9merge合并

3.10sort排序

4.快速模拟最基本的list

4.1自定义命名空间域和list成员变量

4.2node的自定义

4.3list::list()无参构造

4.4list::push_back()

4.5list::迭代器的设计

4.6小总结

5.进一步完善list

5.1list的insert函数接口实现

5.2list::size()

5.3list::erase()

5.4pop_back,pop_front,push_back,push_front

6.完善迭代器

6.1operator->的理解

6.2const迭代器

7.析构、拷贝构造、赋值运算符重载

7.1析构函数

7.2拷贝构造

7.3赋值运算符重载

热门文章

最新文章

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【CPP】slt-list由认识到简化模拟实现深度理解~

1.前言

2.list简介

3.list重点接口

3.1构造函数constructor

3.2operator=

3.3max_size

3.4assigne重写

3.5insert

3.6splice转移

3.7remove

3.8unique去重

3.9merge合并

3.10sort排序

4.快速模拟最基本的list

4.1自定义命名空间域和list成员变量

4.2node的自定义

4.3list::list()无参构造

4.4list::push_back()

4.5list::迭代器的设计

4.6小总结

5.进一步完善list

5.1list的insert函数接口实现

5.2list::size()

5.3list::erase()

5.4pop_back,pop_front,push_back,push_front

6.完善迭代器

6.1operator->的理解

6.2const迭代器

7.析构、拷贝构造、赋值运算符重载

7.1析构函数

7.2拷贝构造

7.3赋值运算符重载

热门文章

最新文章

相关电子书

相关实验场景