【C++要笑着学】list 核心框架接口的模拟实现 | 运算符重载实现list迭代器 | 妙用模板实现const迭代器(一)

简介: 我们在上一章说过,list 其实就是带哨兵位循环双向链表而已,这种链表虽然结构复杂,但是实现起来反而是最简单的,我们在数据结构专栏中有过详细的讲解。

💭 写在前面


我们在上一章说过,list 其实就是带哨兵位循环双向链表而已,这种链表虽然结构复杂,但是实现起来反而是最简单的,我们在数据结构专栏中有过详细的讲解。


当时我们是用C语言实现,这里对 list 的实现其实也是大同小异的。当然,我们重点还是倾向于去理解它的底层实现原理,所以我们将对其实现方式进行进一步地简化,并且按照我们自己习惯的命名风格去走。


我们之前已经模拟实现过 string 和 vector 了,这是本专栏 STL 的第三个模拟实现,相信大家已经能够做到 "驾轻就熟" 了,因此在讲解的时,出现重复的知识点我们就一笔带过。我们将重点去讲解迭代器的实现!本章我们要对迭代器有一个新的认知,迭代器不一定就是一个原生指针,也有可能是一个自定义类型。本章我们将通过自定义类型的运算符重载去控制我们的迭代器的 "行为"。


Ⅰ. list 基本框架的实现


0x00 结点的建构

我们还是参考《STL源码剖析》,用 STL3.0 版本去实现一个阉割版的 list 。


既然是要实现链表,我们首先要做的应该是建构结点。


此外,为了和真正的 list 进行区分,我们这里仍然在自己的命名空间内实现。


回想一下我们的《树锯结构》专栏中,双链表是如何定义的:

c878770c7cc819279b2c58e5447f07cf_54ac1300a17c447cbec42955ef1bb4ad.png

当时我们使用 typedef 的,但我们在讲模板的时候说过,有时候 typedef 做不到 "真正的通用"。


❓ 思考:对于 list 的模拟实现,我们是否可以继续用 typedef 去定义其类型?


(范大将军从类模板章节连夜赶到这里怒斥 typedef )


而我们即将要实现的 list,需要的肯定是 "通用的 list" ,像这种情况 typedef 就帮不上忙了。


我们这里使用模板去解决:


💬 代码:建构双链表的结点:


namespace chaos {
  template<class T>    // 添加模板参数列表
  struct ListNode {
   T _data;      // 用来存放结点的数据
   ListNode<T>* _next;      // 指向后继结点的指针
   ListNode<T>* _prev;   // 指向前驱结点的指针
  };
}

❓ 思考:为什么这里 ListNode 要加 <T> ?


💡 解读:因为类模板不支持自动推类型。 结构体模板或类模板在定义时可以不加 <T>,但 使用时必须加 <T>。


准备好 _data,放置好前驱 _next 和后继结点 _prev 后,我们的结点就有了 "结构" ——

86bef9da3bde00e6a676069012fa7c35_4d8f8d8a640347dbbfc2a667a6d74cc9.png

(我们将如此表示双链表)


我们知道,结构体 struct 在 C++ 中升级成了类,因此它也有调用构造函数的权利。


也就是说,在创建结构体对象的时会调用构造函数。


既然如此,结点的初始化工作,我们可以考虑写一个构造函数去初始化,岂不美哉?


 (我们继续往下看)


0x01 结点初始化

其实结点初始化就是 "创建新结点" ,即我们之前讲数据结构时实现的 CreateNewList() 接口。

7c532dab488e43e958d1394355d9288d_56ab6804ff9a490a8ecd4fd8f8af95f0.png

我们先不考虑开空间的事,这里就完成初始化的工作:


① 将数据给给 data


② 将 next 和 prev 都置成空


这些任务我们可以写到 struct  ListNode 的构造函数中,我们还可以设计成全缺省,给一个匿名对象 T() 。如此一来,如果没有指定初识值,它就会按模板类型去给对应的初始值了。


💬 结点初始化:

namespace chaos {
  template<class T>
  struct ListNode {
   T _data;      // 用来存放结点的数据
   ListNode<T>* _next;      // 指向后继结点的指针
   ListNode<T>* _prev;   // 指向前驱结点的指针
   ListNode(const T& data = T())   // 全缺省构造(初始化)
    : _data(data)
    , _next(nullptr)
    , _prev(nullptr)
   {}
  };
}

至此,结点已经写好了。


0x02 结点连接

设计好结点后,我们现在可以开始实现 list 类了。


考虑到我们刚才实现的 "结点" ListNode<T> 类型比较长,为了美观我们将其 typedef 成 Node:

4785dffe462e684e5b3c0975ed1623d5_d8ab65cbf24a42398017623e3e0c0cb7.png

现在,我们用 Node 就表示 ListNode<T> 了,这也符合我们之前的使用习惯。


因为是带头(哨兵位)双向循环链表,我们先要带个头儿。


我们先要把头结点 _pHead 给设计出来,而 _prev 和 _next 是默认指向头结点的。


a612cdfb19b007ff4e843bfaad72725e_269a2a79d4b1414e92d3b42dff85e3e2.png

💬 代码:pHead:

namespace chaos {
  template<class T>
  class list {
  typedef ListNode<T> Node;      // 重命名为Node
  public:
  /* 构造函数:初始化头结点 */
  list() {
    _pHead = new Node();      // 开空间,调用ListNode()
    _pHead->_next = _pHead;   // 默认指向头结点
    _pHead->_prev = _pHead;   // 默认指向头结点
  }
  private:
  Node* _pHead;    // 头结点指针
  };
}


0x03 push_back 尾插

还是按老规矩,我们先去实现一下最经典的 push_back 尾插,好让我们的 list 先跑起来。


尾插我们需要做什么呢?我们来冷静分析一下:


Step1:找到尾结点并创建新节点:

949c249120c867077c18573762145694_31f92cdc69354dd389d4e9459de05c4d.png

双向带头循环链表,虽然我们没有定义 _pTail,但是找到尾结点真的是轻轻松松,


因为双向带头循环链表真的是太简单了而且全特么是 Fucking ,


尾结点就是头结点的前驱指针,直接 _pHead->_prev,  的速度去取就完事了!


然后直接 new 一个新结点 new_node,自动调用我们刚才写的 "建构结点" struct ListNode

46b82c6d3137da2b589d28353b7dc74a_5dc1514a388548b7b3bc683f28a8c218.png

至此,我们就找到了尾结点,并准备好要插入的新节点了。


Step2:拆线重缝:连接 pTail 和 new_node

d889b317c3e3f7f2f258bd85429a7124_6c89e8ce8d894cafa491a792341fde7d.png

pTail 的后继指针 _next 原来是指向 _pHead 的,因为我们插入了新结点,


所以我们改变 pTail 的后继指针的指向,让其指向 new_node,


相对的,新结点 new_node 的前驱指针也是要指向 new_node 的,形成一个 "连接" 。


(new_node 的前驱和后继指针默认都是 nullptr,它后继的连接我们继续往下看)


Step3:拆线重缝:连接 new_node 和 _pHead

ee0305db75c2db1b8b1d7feda2f660e7_8d78199efb1c4e2fb3af41f83e195b47.png

一样的,这里我们要改变的是 new_node 的后继指针和 _pHead 的前驱指针的指向。


将 new_node 的 _next 指向 _pHead,并将 _pHead 的 _prev 指向 new_node 即可。


如此一来,我们的 "缝合操作" 就大功告成了,我们可以开始代码实现了。


💬 代码:实现尾插操作(注释为思路草图)

template<class T>
class list {
  typedef ListNode<T> Node;      // 重命名为Node
public:
/* 尾插:push_back */
void push_back(const T& x) {
  /*
  *   我们可以通过 pHead->prev,找到 pTail:
  *
  *     phead <-> ... <-> ptail
  *       ↑_________________↓
  * 
  */
  Node* pTail = _pHead->_prev;     // pHead的前驱就是pTail
  Node* new_node = new Node(x);    // 创建新结点(会调用构造,自动创建)
  /*
  * 
  *  因为插入了新结点(new_node),所以我们需要把链表 “重新连接” 一下:
  * 
  *                             (A)
  *     pHead <-> ... <-> pTail <-> new_node 
  *       ↑_____________________________↓
  *                    (B)
  */
  //(A) pTail 与 new_node 的链接
  pTail->_next = new_node;
  new_node->_prev = pTail;
  // (B) new_node 与 pHead 的链接
  new_node->_next = _pHead;
  _pHead->_prev = new_node;
}
private:
  Node* _pHead;
};

尾插写好了,我们来跑一下看看效果如何。


我们随便插入一些数据,然后打开监视窗口看看 push_back 的效果如何。

void test_list1() {
   list<int> L;
   L.push_back(1);
   L.push_back(2);
   L.push_back(3);
   L.push_back(4);
  }

🐞 调试结果如下:

48ad76f02a873b3dee00b0f03951a4db_4b6bc86ed4d04ce498a3425587a80596.png


即使我们链表为空,也是可以进行尾插操作的,这就是结构的优势。


Ⅱ. list 迭代器的实现


0x00 引入:什么!迭代器不一定都是原生指针?

list 的重点是迭代器,因为这里的迭代器的实现和我们之前讲的实现方式都不同。


我们之前讲的 string 和 vector 的迭代器都是一个原生指针,实现起来是非常简单的。


但是 list 是一个链表,你的迭代器还能这样去实现吗?在空间上不是连续的,如何往后走?

6a0f1f8452eb73f7e7f35dd1afbeddf6_70f0f4dc1f28439da70af5ec1e2ff5a8.png

而这些所谓的 "链接" 其实都是我们想象出来的,实际上根本就不存在。


而这些链接的含义只是 "我存的就是你的地址" ,所以我可以找到你的位置。


而我要到下一个位置的重点是 —— 解引用能取到数据,++ 移动到下一位:

35b454f8b9628aa2d57ffeda25be9961_ab7a46a60d424c5c977b2141b6d66b70.png

而自带的 解引用* 和 ++ 的功能,是没法在链表中操作的。


但是,得益于C++有运算符重载的功能,我们可以用一个类型去对结点的指针进行封装!


然后重载运算符 operator++ 和 operator* ,是不是就可以控制其解引用并 ++ 到下一个位置了?


💭 回想:运算符重载就是能让自定义类型像内置类型一样使用,回想一下我们当时讲解日期类的实现,是如何 ++ 到下一天的?当时是我们自己对 operator++ 进行重载,去实现 "进位" 操作的,之后我们使用 ++ 就可以调用那个我们实现的函数。


所以,我们首先要做的是对这两个运算符进行重载!


0x01 迭代器的构造

💬 代码:只需要用一个结点的指针就可以构造了:


template<class T>
struct __list_iterator {
  typedef ListNode<T> Node;   // 重命名
  Node* _node;
    /* 迭代器的构造 */
  __list_iterator(Node* x)
  : _node(x) 
  {}
};

0x02 operator++

加加分为前置和后置,我们这里先实现以下前置++。


92e15f7b882929f7b7ec068e0eda6701_ecce97dcd30543988b97ae65befe0fa0.png

💬 代码:前置++的实现:

/* ++it */
__list_iterator<T>& operator++() {
  _node = _node->_next;  // 让 _node 指向下一个结点
  return *this;  // 返回加加后的值
}

因为前置是直接改变本体,我们直接 return *this 即可。


因为除了作用域还在,所以可以用引用返回, __list_iterator<T>&


对应的,后置++ 我们可以拷贝构造出一个 tmp 存储原来的值,这样虽然改变本体了,


但是返回的还是之前的值,这就实现了后置++。此外,因为前置++后置++都是 operator++,


区分方式是后置++用占位符 (int) 占位,这些知识点我们在之前讲解日期类的时候都说过。


💬 代码:后置++的实现:

/* it++ */
__list_iterator<T> operator++(int) {
  __list_iterator<T> tmp(*this);   // 拷贝构造一个tmp存储原来的值
  _node = _node->_next;  // 让自己++
  return tmp;   // 返回原来的值
}

0x03 operator*

解引用就是取结点 _node 里的数据,


并且 operator* 和指针一样,不仅仅能读数据,还能写数据。


为了使 operator* 能支持修改的操作,我们这里用引用返回 & (返回 _node 中 _data 的别名)


💬 代码:解引用的重载:

/* 解引用 */
T& operator*() {
  return _node->_data;  // 返回结点的数据
}

这样,你用 *it 也就支持修改的操作了:

0ab8640dcc2a5c59140f1a516e3f5ec5_e438427551554c2d9cc7596f76125805.png


0x04 测试效果(实现一下 begin 和 end)

有了 operator++ 和 operator* ,我们就可以来测试一下我们的迭代器了。


begin 和 end 的位置,我们画个图去看:

fd81b9ed71a78ecc5366b2cdd84b35dd_4d2053dae2424b56b8a90e187ad0f15c.png


begin 是第一个存有效数据的结点,即 _pHead 的下一个位置的结点。


而 end 返回的是最后一个数据的下一个位置,即 _pHead(循环链表,懂得都懂)。


💬 代码:在 list 类中设计 begin 和 end


template<class T>
class list {
  typedef ListNode<T> Node;
public:
  typedef __list_iterator<T> iterator;  // 重命名成iterator
  iterator begin() {
  return iterator(_pHead->_next);
  }
  iterator end() {
  return iterator(_pHead);
  }
  list() {...}
    void push_back(const T& x) {...}
private:
  Node* _pHead;
};


因为判断迭代器要用到 != ,所以我们还要实现以下这两个操作符的重载。

3f0853c519c096a03578be01d9a421d6_37927bce1cf54afc9858b58652f24d2b.png


0x05 operator!=

❓ 思考:如何判断是否相等呢?


如果两个迭代器结点的指针指向的是同一个结点,那就说明是相等的迭代器。


反之,如果不是就说明不是相等的迭代器!


💬 代码:这里我们利用 bool 的性质直接 return 返回要判断的条件即可:

/* != */
bool operator!=(const __list_iterator<T>& it) {
  return _node != it._node;  // 它们结点的指针不一样吗?T or F
}

OK,现在我们可以来测试一下我们的迭代器了:

void test_list1() {
  list<int> L;
  L.push_back(1);
  L.push_back(2);
  L.push_back(3);
  L.push_back(4); 
  list<int>::iterator it = L.begin();
  while (it != L.end()) {
   cout << *it << " ";
   it++;
  }
  cout << endl;
  }

🚩 运行结果如下:

512db926a1b3100c6f71472a08af69fe_18cb258ab59f4a4e9ff7012ff1797791.png

(大功告成)


🔺 总结:

443376e6901316d2dcfcd290838823cc_983762de77794dceabe31c0c01042f46.png


0x06 感受类型的意义

经此一役,我们知道了 迭代器不一定是原生指针,也有可能是自定义类型的指针。

void f() {
    Node* pNode = _pHead->_next;
    iterator it = _pHead->_next;
    *pNode;
    *it;
    ++pNode;
    ++it;
}

Node* 原生指针和一个迭代器对象,它们占用的空间是一样大的,都是 ,


并且存的值也是一样的,但是对它们使用运算符的意义和结果是不一样的。


这就是类型的意义,类型的力量!C++ 自定义类型、运算符重载,这一切都是有意义的。


0x07 迭代器的拷贝构造、赋值和析构

❓ 思考:拷贝构造和赋值重载是否需要自己实现?析构呢?


先说结论 —— list 的拷贝构造和赋值不需要自己实现,默认生成的即可。

it2(it1)
it2 = it1 浅拷贝

当前迭代器赋值给另一个迭代器是不需要深拷贝的,浅拷贝就可以。


我们再来谈谈析构函数,为什么不需要自己实现。

template<class T> struct __list_iterator {
    typedef ListNode<T> Node; 
    Node* _node;
    ...
}

迭代器这里虽然有一个结点的指针,但是它并不是迭代器管的,是链表 list 管的,


链表 list 的析构函数会把这个结点 _node 给释放掉的。


所以它的释放和迭代器没什么关系,所以我们不需要关心它的析构。


🌰 举个比较形象的例子:


这就好比你在家吃饭和在饭店吃饭,你在家吃饭,自己吃饭自己洗碗。


而你在饭店吃饭就不一样了,吃就行了,吃完是不需要自己洗碗的。(霸王餐除外啊)


你在这里管就是越俎代庖了,东厂管得了的我西厂要管,东厂管不了的我西厂更要管!


(雨化田是吧,纯纯的 "多管闲事" )


你去饭店吃饭吃完还帮人家把碗洗了,什么绝世大好人……


当然你去写也没人拦你,写 STL3.0 的大哥就自己实现了拷贝构造,并且是浅拷贝,


也就是你不写,自动生成出来的那个浅拷贝,其实默认生成的就可以了。


大哥可能考虑到可能会要构造一个无参的迭代器的情况,所以自己去实现了一下:


c697ae5f8311ba9fb16bb1d0f5c39340_b8fd8494e1074d329881338234548ff1.png

(具体可以去看看的TL3.0的源代码,反正我是没找到有要构造无参迭代器的场景)


总结:迭代器是借助结点的指针访问修改链表的,结点是属于链表的,而不属于迭代器,所以不用去管它的释放问题。 因此,拷贝构造、赋值重载和析构函数,这些都不需要自己实现,默认生成的可以。


0x08 引入:print_list 链表打印函数

我们刚才实现好了迭代器,我们是这么去用的:

list<int>::iterator it = L.begin();
  while (it != L.end()) {
    cout << *it << " ";
    it++;
  }
  cout << endl;

不用范围 for 的前提下去用迭代器似乎挺麻烦的,我们可以把它放到一个函数里:

749b2f535b11f1d42d87ca82f2f8211b_caa4fcc6de484dfda22260dad3bb9ec4.png

这里考虑到减少拷贝,我们使用引用返回,我们之前也说过这种情况能用 const 就用 const。


所以这里就成 const_iterator 了,而我们刚才实现的是普通迭代器,会导致没法遍历。


🔨 测试:我们可以来试试


void print_list(const list<int>& L) {
  list<int>::const_iterator it = L.begin();
  while (it != L.end()) {
    cout << *it << " ";
    it++;
  }
  cout << endl;
  }
  void test_list2() {
  list<int> L;
  L.push_back(2);
  L.push_back(4);
  L.push_back(6);
  L.push_back(8);
  print_list(L);
  }


🚩 运行结果:报错  (而且聪明的编译器都给你画波浪线提醒了)

0cde0787285930a21e44d007798ee4df_a3f02ddd58ce481fac36111fe0e30c95.png


❓ 思考:想想本质 —— const 迭代器和普通迭代器的区别是什么?


💡 解答:普通迭代器访问普通对象,可读可写;const 迭代器访问 const 对象,可读但不可写。


所以我们这里自然是 需要实现 const 迭代器,即实现一个 "可读但不可写" 的迭代器。


(可以 ++ 可以解引用,但解引用的时候不能修改)

d3efc1f1deb71c7ff4b0059784b68f77_12639e72ee7243cd86cadf3e01a4ac7a.png

所以直接在 __list_iterator 里面重载一个 const 类型的 operator* 解决不了问题,


我们得重新实现一个 __const_list_iterator 出来。(当然,更好的方法我们放到后面讲)


0x09 const 迭代器的实现

传统的方法是把  list_iterator 这个类  一下,然后把名称改成 __const_list_iterator


(话不多说我们直接CV大法用起来)


💬 代码:定义 const 迭代器

/* 定义const迭代器 */
template<class T>
struct __const_list_iterator {
  typedef ListNode<T> Node;
  Node* _node;
  __const_list_iterator(Node* x)
  : _node(x)
  {}
  /* 解引用 */
  const T& operator*() {
  return _node->_data;       // 返回结点的数据
  }
  /* ++it */
  __const_list_iterator<T>& operator++() {
  _node = _node->_next;  // 让 _node 指向下一个结点
  return *this;  // 返回加加后的值
  }
  /* it++ */
  __const_list_iterator<T> operator++(int) {
  __const_list_iterator<T> tmp(*this);   // 拷贝构造一个tmp存储原来的值
  _node = _node->_next;
  return tmp;
  }
  /* != */
  bool operator!=(const __const_list_iterator<T>& it) {
  return _node != it._node;  // 它们结点的指针不一样吗?T or F
  }
}

这里我们把 __list_iterator 都修改成 __const_list_iterator,


并且对于解引用 operator* 的重载,我们将其改成 const 引用返回,这样就只能读不能写了。


💬 代码:然后我们这里再在 list 中 typedef 一下 const 迭代器:


/* 定义链表 */
template<class T>
class list {
  typedef ListNode<T> Node;      // 重命名为Node
public:
  /* 迭代器 */
  typedef __list_iterator<T> iterator;
  typedef __const_list_iterator<T> const_iterator;  // 👈 重命名const迭代器
  iterator begin() {   
  return iterator(_pHead->_next);  // 调用 __list_iterator<T>
  }
  iterator end() {
  return iterator(_pHead);
  }
    ...
}


💡 解读:const 迭代器和普通迭代器就不是一个类型了,是另外一个类型。


我们说了,不是迭代器是 const,而是对象是 const,所以要调用 const 的 begin 和 end 才行,


所以还要写 __const_list_iterator 类型的 begin 和 end,我们用 const 去修饰,限制它写的权限。


💬 代码:实现 const 类型的 begin 和 end

// 👇 const 迭代器的 begin 和 end
const_iterator begin() const {
  return const_iterator(_pHead->_next);  
}
const_iterator end() const {
  return const_iterator(_pHead);
}

搞定了,这种  重新实现一个 __const_list_iterator 的方式确实是可以的。


🔨 测试代码:我们再来调用一下 print_list 函数:

void print_list(const list<int>& L) {
  list<int>::const_iterator it = L.begin();
  while (it != L.end()) {
    cout << *it << " ";
    it++;
  }
  cout << endl;
  }
  void test_list2() {
  list<int> L;
  L.push_back(2);
  L.push_back(4);
  L.push_back(6);
  L.push_back(8);
  print_list(L);
  }


🚩 运行结果:(运行成功)

a4e30658b73777cd896039c4199b42b8_b60efae3d5c84cf6b7c045297cf5df7e.png


我们再来看看我们的 const 迭代器效果如何:

ce04ce9269dd152bc754e46b2a154b5b_4f132fa2e456429aa520e710062e313c.png


这里 *it 调用的是 __const_list_iterator 的 operator*,它返回的是 const T&,限制了写了功能。


大功告成了,我们成功实现了 list 的 const 迭代器,


这种实现方式可以是可以,但是这么实现好像有点搓啊!代码是完全冗余的有木有!


这个 const 迭代器和普通迭代器也就是类型名称和返回值不一样而已……


有没有办法可以优化一下呢?我们继续往下看!


0x0A 妙用模板实现 const 迭代器

通过加一个额外的模板参数去控制 operator 的返回值,你能想到吗?


🐂🍺!太妙了,我们来看看大哥是怎么做的 —— 在定义 template 模板的时增加一个参数 Ref :

e9400c4d5f26b774ba6879cf0ac864dd_8f6f51bd232f410085e502ab2288c3d9.png

这样的话,我们 operator* 的返回值我们不要用 T&了,我们改成 Ref:


也就是说,让 operator* 的返回值变成 Ref 这个模板参数!


💬 代码:之后我们就可以在 list 中 typedef 的时候就可以做到 "分流" ,传 T& 或 const T&:

/* 定义链表 */
template<class T>
class list {
  typedef ListNode<T> Node; 
public:
  /* 迭代器 */
  typedef __list_iterator<T, T&> iterator;
  typedef __list_iterator<T, const T&> const_iterator;
  iterator begin() {   
  return iterator(_pHead->_next);
  }
  iterator end() {
  return iterator(_pHead);
  }
  const_iterator begin() const {
  return const_iterator(_pHead->_next);  
  }
  const_iterator end() const {
  return const_iterator(_pHead);
  }

情况一:Ref 是 T&,可读可写

59cc271c6d84e23d119b049aa0e42e77_f207782511cf4664929706156e091077.png


🔑 解读:这里 test_list1 是一个普通对象,调用的自然是普通的 begin。 begin 返回的是普通迭代器 __list_iterator<T, T&>,第二个模板参数是 T&,Ref 就是 T& 了。operator* 的返回值 Ref 是 T& 了,这样就做到了可读可写了。


情况二:Ref 是 const T&,可读但不可写

2b240be77684428a94804180de60c7f2_219aeb31771643439711f7014d4ed0ce.png


💡 解读:比如这里的 print_list 就是一个 const 对象,它调用的就是 const 的 begin。const begin 返回的是 const 迭代器 __list_iterator<T, const T&>,第一个值传的都是 T,第二个值 const T& 传给 Ref。那么 operator* 的返回值 Ref 就是 const T& 了,这样就做到了可读但不可写的。


我们本来是要实现两个类的,但是这里就额外加一个模板参数就搞定了,


这就是高手写的代码,而我自己去写可能就是写一个重复的类去实现了。


0x0B 将模板重命名

8a928d4cc394936c1ec28a48e0dffba2_44a2d2882c1948c581bc63af15cd73d9.png

此时去编译,是编译不通过的。


因为我们多定义了一个 Ref,所以  __list_iterator 中的所有类模板都得加上它,比如:

ff2d3647ee0e80016975c7f9704c275e_b460ef2d35b043e39c4b9a0b4b2069eb.png

这太烦了,马上我们甚至还要再加个模板参数 Ptr 呢(剧透一下),


这样加来加去是不是太不方便了?我们来看看设计 STL 的大佬是怎么做的:

39ab80bca3ad5424479e9200378f8f65_7961b2fc1a5c4ee7871a0b630686112b.png

把这些都 typedef 一下,这样我们就可以把 __list_iterator<T, Ref> 写成 self 了:

13f2f88cbd4db50ce671e922eeae977b_631eab1859d64e4688874b94cf1aaa80.png

💬 代码:真的是非常方便,我们来替换一下:

/* 定义迭代器 */
template<class T, class Ref>
struct __list_iterator {
  typedef ListNode<T> Node;
  typedef __list_iterator<T, Ref> self;    // 为了方便我们重命名为self
  Node* _node;
  __list_iterator(Node* x)
  : _node(x) 
  {}
  /* 解引用 */
  Ref operator*() {
  return _node->_data;       // 返回结点的数据
  }
  const T& operator*() const {
  return _node->_data;      // 返回结点的数据
  }
  /* ++it */
  self& operator++() {
  _node = _node->_next;  // 让 _node 指向下一个结点
  return *this;  // 返回加加后的值
  }
  /* it++ */
  self operator++(int) {
  self tmp(*this);   // 拷贝构造一个tmp存储原来的值
  _node = _node->_next;
  return tmp;
  }
  /* != */
  bool operator!=(const self& it) {
  return _node != it._node;  // 它们结点的指针不一样吗?T or F
  }
    // 顺手再把 -- 写了
  /* --it */
  self& operator--() {
  _node = _node->_prev;  
  return *this;
  }
  /* it-- */
  self operator--(int) {
  self tmp(*this); 
  _node = _node->_prev;
  return tmp;
  }
};

🚩 运行结果如下:(运行成功)

5a838839bbc20a8eca3461a1ac653376_06630bf01e4c4a1b843b4374f79afbba.png


0x0C 箭头操作符

迭代器是像指针一样的,所以要重载两个解引用。


为什么?指针如果指向的类型是原生的普通类型,要取对象是可以用解引用,


但是如果指向而是一个结构,并且我们又要取它的每一个成员变量,就像这样:


💬 示例:比如是一个日期类,假设我们没有实现其流插入,我们自己访问

struct Date {
  int _year;
  int _month;
  int _day;
  Date(int year = 1, int month = 1, int day = 1) 
    : _year(year)
    , _month(month)
    , _day(day) 
  {}
  };
  void test_list3() {
  list<Date> L;
  L.push_back(Date(2022, 5, 1));
  L.push_back(Date(2022, 5, 2));
  L.push_back(Date(2022, 5, 3));
  list<Date>::iterator it = L.begin();
  while (it != L.end()) {
    // cout << *it << " ";  假设我们没有实现流插入,我们自己访问
    cout << (*it)._year << "/" << (*it)._month << "/" << (*it)._day << endl;
    it++;
  }
  cout << endl;
  }


🚩 运行结果如下:

ba0d9ce9ccbb63ffee9afae61b6d1235_00c5e50802154abdb430815613804834.png


我们发现,在我们没有实现日期类的流提取运算符的前提下,想去迭代链表 L,


我们就需要 *(it)._xxx 去访问,而大多数主流习惯应该是用 -> 去访问的:

9145993cee34bbb696ff81ff32503e70_a326349447f644a6b3fff41ba412ab16.png

(诚然,用 *. 去访问完全没有问题,这个在本人《维生素C语言》专栏中提到过)


所以我们这里可以去实现一下箭头操作符 ->


💬 代码:其实现方式似乎有些出乎意料,思考下原理是什么?

/* 解引用 */
Ref operator*() {
  return _node->_data;       // 返回结点的数据
}
T* operator->() {
  return &_node->_data;     
}

cd6be3990980727296693c4c93157918_165e87336d5d4b4592179870d4d2e90e.png

🔺 总结:所有类型重载 operator-> 时都会省略一个箭头。(后期讲智能指针还会再提)


还没完,这里也面临一个问题  —— 就是我们刚才提到的 const 迭代器。


如果你是一个 const 迭代器你用箭头也是可以去修改数据的,基于这样的一个原因,


我们还要增加一个模板参数:Ptr   (刚才剧透的)

5bff0bb7b27a105e30a0e2c9e93bf45c_4d4f68e7dd6345db8a4252e637ec7bc5.png

此时我们刚才 typedef 的 self 是不是就体现出方便的价值了?


我们这里增加一个新的模板参数,其他地方都不用改,只需要 self 里加个 Ptr:

b64e1f20e1187c9d3396ce7a5ec27608_7d5005fdd93e4de4a32dfd17bf35ac8a.png

太方便了!我们直接把 operator-> 的返回值修改成 Ptr 就行了,


到时候我们传一个 T* 或 const T* 给 Ptr 就做到适配普通迭代器和 const 迭代器的 operator-> 了。

d83d0331b0223840c079d70c8500215c_5b5defeaacca41c68b01ffa8de4343ec.png

(和 operator* 一样的原理,我们下面传的时候增加一个参数)


💬 代码:

/* 定义迭代器 */
template<class T, class Ref, class Ptr>
struct __list_iterator {
  typedef ListNode<T> Node;
  typedef __list_iterator<T, Ref, Ptr> self;    // 为了方便我们重命名为self
  Node* _node;
  __list_iterator(Node* x)
  : _node(x) 
  {}
  /* 解引用 */
  Ref operator*() {
  return _node->_data;       // 返回结点的数据
  }
  Ptr operator->() {
  return &_node->_data;     
  }
    ...
};
/* 定义链表 */
template<class T>
class list {
  typedef ListNode<T> Node;      // 重命名为Node
public:
  /* 迭代器 */
  typedef __list_iterator<T, T&, T*> iterator;
  typedef __list_iterator<T, const T&, const T*> const_iterator;
    ...
}


这里我们把传递的值增加一个 T* 和 const T* ,如此一来就做到了完美的适配。


0x0D 反向迭代器的实现

我们来看一下源代码是如何实现的:

a5b5e5131337c324a5f614f9764a7741_2a926f8b9da84dbba3dfe41f9149396a.png


反向迭代器其实就是对正向迭代器的一种封装 —— 适配器模式(配接器模式)。


(这里我们先做一个简单的了解,我们将在下一章进行详细的探讨)


💬 代码:反向迭代器的实现:

namespace chaos
{
  // Iterator是哪个容器的迭代器,reverse_iterator<Iterator>就可以
  // 适配出哪个容器的反向迭代器。复用的体现
  template <class Iterator, class Ref, class Ptr>
  class reverse_iterator {
  typedef reverse_iterator<Iterator, Ref, Ptr> self;
  public:
  reverse_iterator(Iterator it)
    :_it(it)
  {}
  Ref operator*() {
    //return *_it;
    Iterator prev = _it;
    return *--prev;
  }
  Ptr operator->() {
    return &operator*();
  }
  self& operator++() {
    --_it;
    return *this;
  }
  self& operator--() {
    ++_it;
    return *this;
  }
  bool operator!= (const self& rit) const {
    return _it != rit._it;
  }
  private:
  Iterator _it;
  };
}

Iterator 是那个容器的迭代器,reverse_iterator<Iterator> 就可以适配出哪个容器的反向迭代器。复用的体现。


Ⅲ. list 增删查改的实现


0x00 在 pos 位置前插入 - insert

在 pos 位置插入,我们通过 pos 去找到前驱 prev,之后创建新结点,再进行 "缝合" 操作,


这个我们在前面讲 push_back 的时候详细说过了,这里不在细说。具体看图:

926a664ad2d5f490e98d76dab0e9538c_a49b1e7958d14edea41552620b3ea014.png

💬 代码:在 pos 位置前插入

/* 在pos位置前插入 */
void insert(iterator pos, const T& x) {
  Node* cur = pos._node;     // 找到pos位置的结点
  Node* cur_prev = cur->_prev;     // 因为要在pos位置前插入,所以要找到当前pos位置的前一个结点
  Node* new_node = new Node(x);  // 创建新节点
  // 缝合: cur_prev <-> new_node <-> cur
  cur_prev->_next = new_node;
  new_node->_prev = cur_prev;
  new_node->_next = cur;
  cur->_prev = new_node;
}

❓ 思考:erase 以后,pos 是否失效?不会。


⚡ 优化:

/* 在pos位置前插入 */
iterator insert(iterator pos, const T& x) {
  Node* cur = pos._node;     // 找到pos位置的结点
  Node* cur_prev = cur->_prev;     // 因为要在pos位置前插入,所以要找到当前pos位置的前一个结点
  Node* new_node = new Node(x);  // 创建新节点
  // 缝合: cur_prev <-> new_node <-> cur
  cur_prev->_next = new_node;
  new_node->_prev = cur_prev;
  new_node->_next = cur;
  cur->_prev = new_node;
    return iterator(new_node);
}

有了 insert,我们就可以让之前为了快速把 list 跑起来而实现的 push_back 用 insert 复用一下。


⚡ 代码复用:push_back

/* 尾插:push_back */
void push_back(const T& x) {
  //Node* pTail = _pHead->_prev;     // pHead的前驱就是pTail
  //Node* new_node = new Node(x);    // 创建新结点(会调用构造,自动创建)
  //
  //pTail->_next = new_node;
  //new_node->_prev = pTail;
  //new_node->_next = _pHead;
  //_pHead->_prev = new_node;
  insert(end(), x);   // 在end(pHead)前插入,即尾插
}

push_back 复用 insert,pos 我们给 end() 。因为 end() 是头结点 _pHead,


在头结点前面插入,insert 的 cur_prev 就会代表尾结点,会在 cur_prev 后面插入 new_node,


并完成 "缝合",这就做到了尾插。如果不明白这里为啥要传 end 作为 pos,可以看图理解:

fac7dca3747eeea353d3200c67ccd987_fe317a7b3ce3415eba5a563d65e79b5f.png


0x01 push_front 头插

push_back 有了,我们顺手再把 push_front 写了。


💬 代码:push_front

/* 头插:push_front */
void push_back(const T& x) {
  insert(begin(), x);  // 在begin(头结点的下一个结点)前插入,即头插
}

1edbe4f1a18f52a7835e522ce789f700_e4376978448c4e8d8a9384ce291cd3b4.png

0x02 删除 pos 位置的结点 erase

删除 pos 位置结点,步骤如下:


① 找到 pos 的前驱和后继


② 释放 pos 位置结点


③ 将已删除的 pos 结点的前驱和后继 "缝合"

14c2e272fd16056bd130aa4ead1a1cbf_1da6ddfa4a27454caaa9f3042cb20a7b.png


📌 注意:当然我们还要防止哨兵位头结点 _pHead 被删的情况,头不小心卸了就没法玩了。


这里我还是习惯用暴力的方式去解决,用 assert 断言处理。

780212dc622b338142328d1fade8d792_2ca4c3603e0f4d3794a26566a9ebf761.png

💬 代码:删除 pos 位置结点

/* 任意位置删除 */
void erase(iterator pos) {
  assert(pos != end());   // 防止头结点被删除
  Node* cur = pos._node;   // 找到pos位置的结点
  Node* cur_prev = cur->_prev;   // 找到pos的前驱
  Node* cur_next = cur->_next;   // 找到pos的后继
  // 删除cur
  delete[] cur;
    cur = nullptr;
  // 缝合:  cur_prev <-> cur(删) <-> cur_next
  cur_prev->_next = cur_next;
  cur_next->_prev = cur_prev;
}


❓ 思考:erase 以后,pos 是否失效?


一定会失效!因为结点的指针指向的结点被干掉了,这当然会失效。


为了救迭代器,我们可以学着文档里的处理方式 —— 返回刚刚被删除的元素的下一个元素。


⚡ 改进:erase


/* 任意位置删除 */
iterator erase(iterator pos) {
  assert(pos != end());   // 防止头结点被删除
  Node* cur = pos._node;   // 找到pos位置的结点
  Node* cur_prev = cur->_prev;   // 找到pos的前驱
  Node* cur_next = cur->_next;   // 找到pos的后继
  // 删除cur
  delete cur;
  // 缝合:  cur_prev <-> cur(删) <-> cur_next
  cur_prev->_next = cur_next;
  cur_next->_prev = cur_prev;
  return iterator(cur_next);
}


0x03 pop_back 尾删

删除 pos 位置结点的 erase 写好了,我们实现 pop_back 也是易如反掌的。


💬 代码:直接复用就完事了:


/* 尾删 */
void pop_back() {
  erase(_pHead->_prev);  // 删除最后一个元素,即尾结点
}
因为是删除 pos 位置,我们传过去的得是要删的结点。
而尾删删除的是最后一个结点,即尾结点。_pHead->_prev 就是尾结点了,传过去即可。
当然你也可以这么写,效果是一样的:
/* 尾删 */
void pop_back() {
  erase(--end());  // 删除最后一个元素,即尾结点
}

我们知道 end() 是头结点 _pHead 的位置,我们对 end() 减减,就跑到尾节点的位置了:

1588058b6a4dad5689588dd06327b979_66c60ad9b9ad4fb68005af5682ff7fc3.png


0x04 pop_front 头删

pop_front 头删,即删除头结点的下一个结点,即 begin() 位置的结点。

44eb0bc61708095c22ca60ac69878cd8_013575f4441642c180bf72487706da9f.png


💬 代码:仍然是复用

/* 头删 */
void pop_front() {
  erase(begin());  // 删除头结点的下一个结点(即begin位置的结点)
}


相关文章
|
1月前
|
存储 算法 C++
C++ STL 初探:打开标准模板库的大门
C++ STL 初探:打开标准模板库的大门
89 10
|
3月前
|
编译器 C++
【C++】——初识模板
【C++】——初识模板
【C++】——初识模板
|
10天前
|
安全 Java 程序员
深入Java集合框架:解密List的Fail-Fast与Fail-Safe机制
本文介绍了 Java 中 List 的遍历和删除操作,重点讨论了快速失败(fail-fast)和安全失败(fail-safe)机制。通过普通 for 循环、迭代器和 foreach 循环的对比,详细解释了各种方法的优缺点及适用场景,特别是在多线程环境下的表现。最后推荐了适合高并发场景的 fail-safe 容器,如 CopyOnWriteArrayList 和 ConcurrentHashMap。
38 5
|
17天前
|
编译器 程序员 C++
【C++打怪之路Lv7】-- 模板初阶
【C++打怪之路Lv7】-- 模板初阶
13 1
|
29天前
|
编译器 C语言 C++
C++入门6——模板(泛型编程、函数模板、类模板)
C++入门6——模板(泛型编程、函数模板、类模板)
34 0
C++入门6——模板(泛型编程、函数模板、类模板)
|
1月前
|
算法 编译器 C++
【C++篇】领略模板编程的进阶之美:参数巧思与编译的智慧
【C++篇】领略模板编程的进阶之美:参数巧思与编译的智慧
69 2
|
1月前
|
存储 编译器 C++
【C++篇】引领C++模板初体验:泛型编程的力量与妙用
【C++篇】引领C++模板初体验:泛型编程的力量与妙用
36 2
|
1月前
|
存储 算法 编译器
【C++】初识C++模板与STL
【C++】初识C++模板与STL
|
1月前
|
编译器 C++
【C++】模板进阶:深入解析模板特化
【C++】模板进阶:深入解析模板特化
|
2月前
|
存储 算法 程序员
C++ 11新特性之可变参数模板
C++ 11新特性之可变参数模板
50 0