C++入门第八篇---STL模板---list的模拟实现

前言：

有了前面的string和vector两个模板的基础，我们接下来就来模拟实现一下list链表模板，我还是要强调的一点是，我们模拟实现模板的目的是熟练的去使用以及去学习一些对于我们本身学习C++有用的知识和用法，而不是单纯的去模拟实现。希望大家在学习之前先搞清楚目的再去行动，切忌盲目努力。

list的大致介绍：

在STL模板中，list模板实现的是一个双向带头循环的链表。

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

所以在这里我想说一下，对于想要频繁支持任意位置增删的数据来说，使用list更为划算，但list遍历却很麻烦，但vector对于增删很麻烦，需要全部串动一遍数据，不过对于任意位置的访问却很简单，这就是两者在不同情况下的使用特点，我们应该按照不同的场景去灵活使用。

可以用下面的这张图来理解：

有了前面的双向带头循环链表模拟实现的基础，现在让我们正式开始模拟实现吧。

模拟实现list:

1.节点 链表 ：

节点：

首先，对于链表来说，每一个节点都应该是一个独立的结构体，我在这里将其设为结构体，其目的就是让其数据都是开放的，在C++中默认struct类型是public权限的，然后就是常规的节点结构体的书写方法如下：

template<class T>
struct list_node
{
  T _data;
  list_node<T>* _next;
  list_node<T>* _prev;
  list_node(const T& x=T())//注意这里不要给赋值，C++STL模板也是支持对内置类型进行拷贝构造的，而这里的数据不一定是内置类型，一旦是自定义类型就得调用拷贝构造了，所以我们这里使用匿名构造
    :_data(x),
    ,_next(nullptr)
    ,_prev(nullptr)
  {}
};

处于为了让我们的每一个节点可存储的数据是任意类型的，我们使用模板来定义类，同时我们写出来我们这个节点类的构造函数，其原理很简单，但是我们要注意我们的缺省参数的给法，在模板使用之后，我们的内置类型也开始能支持构造函数的，同时我们的节点的数据也有可能是自定义类型，所以我们在这里给缺省值直接给其匿名构造的缺省值，这样同时满足了内置类型和自定义类型双重数据类型可以通过拷贝构造，这个很关键，我在vector那里讲过，在这里我再提及一次。，然后就是很常规的把指针先指向空和我们的数据给过去即可。

链表：

首先由于我们要实现的是一个双向带头循环的链表，那么自然我们只需要记录我们的头节点即可，通过头节点我们可以去访问任意的数据，通过指针的迭代即可。所以，我们的链表类的成员只要包含一个头节点的指针以及一个记录数据个数的size即可，如下：

private:
  Node* _head;//类的成员只有一个哨兵位节点作为头节点
  size_t _size;//利用这个变量实时统计，就省去了从头遍历一遍链表的时间

我们同样需要对头节点进行初始化，我在这里这样实现：

void empty_init()//空初始化,创建一个哨兵节点出来
{
  _head = new Node;
  _head->_next = _head;
  _head->_prev = _head;
}
list()//构造函数
{
  empty_init();
  _size = 0;
}

有了对头节点的初始化，我们同时直接把链表类的构造函数写出来，即初始化头节点的同时再初始化size即可。

有了这两步，我们的链表的大体模型就出来了，创造节点类和链表类链接。

2.迭代器：

首先让我们考虑一下迭代器的本质，我们都知道迭代器的本质是对指针进行操控，解引用，迭代加加，判断是否到结尾。通过封装一个指针，我们是可以做到这些的，例如string和vector，因为首先他们都是以数组为基本的容器去处理的，并且他们很多都是单一的数据类型，直接解引用就能得到，但是节点不同，首先节点内部就存在多个成员变量，也就是说，对于自定义类型的解引用是没有默认的，我们必须要自己去写运算符重载才可以。再说加加和减减的问题。我们为什么可以对vector和string加加和减减呢？这是因为它们的底层都是数组，其空间地址是连续的，指针可以通过加加连续的迭代，但是对于链表来说，每一个节点都是一个独立的个体，他们的空间位置是不连续的，你指针的加加和减减毫无意义，包括判断结尾也是，你没有默认的判断方式，你可以用下面这张图理解我的意思：

那怎样解决这个问题呢？由此，我们就封装一个类来模拟迭代器，通过运算符重载去解决问题，这个便是我们list库的最关键最核心的部分，即在处理我们没法直接利用指针去封装的自定义类型的迭代器时，通过使用类去构建一个迭代器模拟指针来实现。

template<class T,class Ref,class Ptr>
struct __list_iterator
{
  typedef list_node<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++(int)//后置++
  {
    self tmp(*this);
    _node = _node->_next;
    return tmp;
  }
  self& operator--()//前置--
  {
    _node = _node->_prev;
    return *this;
  }
  self operator--(int)//后置--
  {
    self tmp(*this);
    _node = _node->_prev;
    return tmp;
  }
   Ref operator*()//迭代器的解引用
  {
    return _node->_data;
  }
   Ptr operator->()//箭头解引用，针对数据_data为自定义类型的时候方便我们去访问数据
  {
    return &_node->_data;
  }
  bool operator!=(const self& s)
  {
    return _node != s._node;
  }
  bool operator==(const self& s)
  {
    return _node == s->_node;
  }
};

在这里我同样使用一个struct来封装类，这样方便我们后续的数据访问不会受到权限的限制，我们的成员只有一个，那便是我们的节点的指针Node* node，我们依旧是去模拟指针的作用

1.首先是构造函数，对于迭代器来说，他没有缺省值的可能性，也就是说只要使用了迭代器必然要为其赋一个初值。然后就是常规的构造过程，我在这类不多赘述了。
2.下一个便是前置加加和后置加加的问题，结合前面学过的知识，为了区分他们两个我们要在后置带上一个int以示区分，在这里注意前置和后置的返回值问题，前置由于直接操作指针，故我们返回的是之前存在的node，故我们引用返回，而对于后置来说，我们返回的是当前的指针，但实际上我们的node已经指向下一个了，这就需要我们再创建一个变量来存储原先的位置，所以我们的返回值是传值返回，这个细节要注意别弄错了。
3.对于解引用的问题，同样由于我们的data本身就是存在的，所以我们依旧使用引用返回，由于node本身是结构体的指针，故我们要使用箭头去访问而不是.。
4.对于箭头的返回，我们在这里返回的是我们data的地址而不是data本身，因为我们的data也有可能是一个自定义类型的数据，这导致我们可能还需要一层访问去确定访问我们data数据里的哪一个数值。
在这里有一个很奇怪的地方：如果我们的data真的是自定义类型，如下：

struct AA
{
  AA(int a1=0,int a2=0)//自定义类型的构造函数
    :_a1(a1)
    ,_a2(a2)
  {}
  int _a1;
  int _a2;
};
void test3()
{
  list<AA> a1;
  list<AA>::iterator it1 = a1.begin();
  while (it1 != a1.end())
  {
    cout << it1->_a1 << " " << it1->_a2 << endl;//在这里它隐藏了一个箭头，因为我们哪怕是访问it1里面的operator的data后，这里的data也是AA类型的，然后才能去访问AA里面的数据，由于我们取地址，所以我们访问也是->去访问，这是一个很奇怪的点，希望特殊去记住,这里本来是it1.operator->()->_a1，但是在这里直接省略了一个箭头
    it1++;
  }

你会发现一个问题是，我们只需要一个箭头就能访问到a1或者a2，但实际上我们的第一个箭头应该是先访问我们的data的地址，然后通过data再去访问我们里面的具体元素，也就是说在这里它省略了一个箭头，但是这样也可以访问，我认为其本质原因在于，用两个箭头对于我们来说不是很好理解，所以编译器在这里优化了一下，省略了其中的一个箭头，变得让我们更好理解了，但我们自身不能忽略，实际上它应该是it1.operator->()->_a1.

5.对于判断相等和不相等的问题，很简单，我们直接利用指针是否相等即可。

这样，通过运算符重载和封装，我们变得到了我们的迭代器类，但是此时我们还有一个问题需要解决，即对于const类型的数据访问我们要特殊处理，这时候就有人提出了一个问题：这不是很简单么？直接在我们的iterator迭代器上加一个const不就解决问题了么？

这是个很严重的误解：如果我们对iterator前面加上const，在这里我们甚至没法对指针本身进行修改了，因为它const限制的是我们类里面的数据，而我们是需要类里的node的变化去访问数据的，所以，显然直接加const是不行的，我们可以再去定义一个新的类型const_iterator，让它作为我们的const迭代器即可，但是，重新写一个未免太麻烦了，能不能用模板的知识来简化代码呢？

这是完全可以的，让我们看一看我们迭代器代码的前几行：

template<class T,class Ref,class Ptr>
struct __list_iterator
{
  typedef list_node<T> Node;
  typedef __list_iterator<T,Ref,Ptr> self;

你会发现，我同时定义了三个模板变量，那这是为什么呢？

让我们想一想我们模拟指针主要模拟的是哪些东西：解引用，指针操作，数据本身，他们实际上反映在我们的返回值上，也就是T T& T*这三个方面，其他的对于const迭代器和非const迭代器来说都是相同的，因此，我们定义三个模板变量，让编译器自己去做选择，你可以看到我迭代器的返回值直接就是Ref Ptr，然后我下面的list去typedef的时候，就直接是：

template<class T>
class list
{
  typedef list_node<T> Node;
public:
  typedef __list_iterator<T,T&,T*> iterator;
  typedef __list_iterator<T,const T&,const T*> const_iterator;

这样，编译器根据你的名字为其自动匹配迭代器是const还是非const，从而在返回值部分返回对应的模板实例化的返回类型，从而让我们实现了一份代码就可以实现双类型迭代器的作用，这个很关键，是list的核心部分，我的建议是反复研究琢磨透为止。

封装了我们的迭代器iterator 和const_iterator后，我们接下来的函数功能就很简单了，我下面几乎都上代码做简单的讲解：

3.增删：

1.任意插入：

iterator insert(iterator pos,const T& x)//任意插,在pos位置之前去插入一个值
{
  Node* cur = pos._node;
  Node* newnode = new Node(x);
  Node* prev = cur->_prev;
  prev->_next = newnode;
  newnode->_prev = prev;
  newnode->_next = cur;
  cur->_prev = newnode;
  _size++;
  return newnode;
}

2.任意删除：

iterator erase(iterator pos)//任意删,这里会涉及到迭代器失效的问题，pos对应的空间被释放后，pos的指向就无效了，故我们在这里返回它的下一个位置以防止迭代器失效
{
  Node* cur = pos._node;
  Node* prev = cur->_prev;
  Node* next = cur->_next;
  delete cur;
  prev->_next = next;
  next->_prev = prev;
  _size--;
  return next;
}

4.链表节点个数：

size_t size()//链表的节点个数
{
  return _size;
}

这里便是我为何要创建一个size成员的原因，因为链表的遍历统计个数很麻烦，所以我们实时统计，直接就省去了遍历的过程，节省运算的时间。

5.头尾迭代器位置返回：

const_iterator begin()const
{
  return _head->_next;
}
const_iterator end()const
{
  return _head;
}
iterator begin()//构成重载，自动匹配
{
  return _head->_next;
}
iterator end()
{
  return _head;
}

你会看到这里，有了我们的模板，我们的一套迭代器就可以像以前那样去使用了。

在这里我要说我对迭代器的理解：

迭代器完美体现了封装，倘若不模拟，我们之只需要一套方法使用，但是模拟是完全不同的，封装屏蔽了底层实现和封装细节，提供统一的增删查改的遍历方式，你会发现，对于任意的数据类型，他们的迭代器的底层是天差地别的，但是他们使用起来确实方法相同的，这便是迭代器最为巧妙的地方。

6.拷贝构造 赋值运算符重载：

拷贝构造：

我们的拷贝构造，在这里由于浅拷贝的原因，我们和我们的vector一样，同样使用依次遍历尾插到结尾的方式，如下：

list(const list<T>& it)//拷贝构造
{
  empty_init();
  for (auto ch : it)//遍历it，一个一个插入到我们要构造的list中
  {
    push_back(ch);
  }
}

赋值运算符重载：

利用现代写法，直接交换头节点即可：

void swap(list<T> it)
{
  std::swap(_head, it._head);//注意，我们的交换在这里要用std自带的交换，在这里直接交换头指针即可，其他的根本不用交换，成员里本身也没有
  std::swap(_size, it._size);
}
list<T>& operator=(list<T> it)//赋值运算符重载现代写法,即直接拷贝构造交换即可
{
  swap(it);
  return *this;
}

7.清除数据和析构函数：

清除数据：

注意，在这里要注意的问题是，我们的清除数据不是将整个链表销毁，而是清楚数据，所以我们要保留我们的头节点，头节点是在析构函数的时候才会被消除的，这是清除数据和析构函数的不同之处，我们要想清楚。

void clear()//清除数据，注意清理数据不是完全销毁链表，所以我们不销毁头节点
{
  iterator it = begin();
  while (it != end())
  {
    it=erase(it);//这里不用加加，it自动返回下一个节点,我们直接用it接收即可
  }
}

在这里我们采用一个一个删除的方式进行，注意我们的erase是会返回下一个位置的值的，故我们的it要接收，否则会有迭代器失效的问题。

析构函数：

本质上就是清除数据+销毁头节点：

~list()//析构函数
  {
    clear();
    delete _head;
    _head = nullptr;
    _size = 0;
  }

以上便是我们的list最关键的一些功能的模拟实现，其余的功能有了这些基础实现起来是很简单的，在这里我就不多说了。

总结：

对于list来说，封装一个迭代器，这个是很关键的，我认为这是我们对类和对象的进一步理解才能完全掌握的知识，所以我的建议是我们要反复思考和模拟实现这个迭代器，或者你可以上网去找一找我们STL–list库的底层，其琢磨为何要这样去实现库，这将有助于我们理解迭代器，同时帮助我们去更好的使用list模板库。