AI 助理
备案控制台
开发者社区 人工智能 文章 正文

STL设计之链表设计,分块分组件分析,迭代器设计思路

2023-01-10 108
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： STL设计之链表设计,分块分组件分析,迭代器设计思路

一. 思考关于list的迭代器的设计

首先关于list的迭代器设计上面，不再像vector那般的简单了，因为 List 不是连续的存储空间在存储着元素，元素的访问也就没有办法像 vector中原生指针那样直接的进行 ++ 操作去访问后序元素，  但是迭代器就是可以支持做 ++  -- * 操作的一个这样一个类, 我们需要可以通过 ++  迭代器的操作  遍历访问整个容器中的元素

正因上述的需求，我们的  List 中的节点  LIstNode* pnode  便是需要专门为其设计一个迭代器类进行管理的，使得  pnode 可以通过  ++  的操作去访问下一个的元素,  -- 操作可以去访问上一个元素

所以大体上的思路出来了，一个struct iterator迭代器类封装管理一个ListNode* 的指针，功能就是一个智能指针类，管理一个ListNode* 指针,  对齐进行各种运算符重载：使得我们的ListNode* 指针可以通过 ++  -- 操作实现容器的遍历

  • 结点类

  • 迭代器类:   此处粘贴出来的仅仅只是迭代器的重要组件，理清楚思路，其他的迭代器的运算符重载函数的书写还是蛮easy的
  • 首先：我们将迭代器设置成了三个模板参数，分别是T  Ref   Ptr, 这样做有什么必要吗？   答案肯定是肯定的，  STL源码中不可能无端设计出来三个模板参数呀

因为后序需要使用到ListIterator<T, Ref, Ptr> 还有 ListNode<T> 但是这样带着模板写有点略显麻烦了，所以起得别名, self别名 代表迭代器本体类型 上述问题的解决其实就是在此处了， 核心关键就是两种迭代器的产生, 一种是const_iterator  另外一个是  iterator ，  一旦我们将其设置成三个模板参数，我们传入const 的时候他会按照模板的模子自动帮我们生成一份const类，我们就不再需要重新单独的为const 再专门设计出来一个类了, 没有必要做这个手工花销，有模板不必再自己新手写一个const 迭代器管理类了

二. 重要函数原型分析理解,有了这些先写出来看看效果

迭代器框架必备函数刨析

  • operator * 重载就是取出其中的数据
  • opeartor-> 重载就是取出数据的地址
  • != 和 == 大家都懂, 判断是否是一个迭代器

  • ++  -- 操作迭代器必备的操作， 代表着前进和后退一个结点

List框架必备函数刨析

  • 写默认构造很简单，一个没有数据的虚拟结点充当表头, 前后指针指向表头自身.

  • 尾部插入一个结点, 三个过程
  1. 拿到尾部结点指针 pTail, 创建出新的newnode结点
  2. pTail和newnode 相连接, newnode 成为新的tail
  3. 要构成循环，newnode 尾部结点需要和 head 相互连接
  5. 上述简简单单的写一下for_each   使用迭代器作为模板参数，不为别的，只为了让大家感受一下为啥迭代器   就能做各种容器和算法之间的粘合剂，没有迭代器就无法支持容器的遍历。。。            

因为没有迭代器管理对象指针，智能指针类，让其支持  ++  --  * 操作来泛型的遍历整个容器，且将容器中的元素进行算法func处理，     (STL的哪些所有的遍历算法都没法实现了，都瘫痪了)

三. 搭出大体框架

#include <iostream>
#include <list>
#include <assert.h>
using namespace std;
namespace tyj {
  //链表节点的设计, 双向循环链表
  template<class T>
  struct ListNode {
    ListNode(const T& _val = T())
      : pre(nullptr)
      , next(nullptr)
      , val(_val) {
    }
    ListNode<T>* pre;
    ListNode<T>* next;
    T val;
  };
  //分析一下三个模板??? 为啥要三个，其实这个是STL源码里面这样设计的
  template<class T, class Ref, class Ptr>
  struct ListIterator {
    typedef ListNode<T> Node;
    typedef ListIterator<T, Ref, Ptr > self;
    Node* pnode;  //Iterator管理的指针
    ListIterator(Node* _pnode = nullptr)
      : pnode(_pnode) { 
    }
    Ref operator*() {
      return pnode->val;  //*重载访问val
    }
    Ptr operator->() {    //支持->访问
      return &pnode->val;
    }
    bool operator!=(const self& obj) const {
      return pnode != obj.pnode;
    }
    bool operator==(const self& obj) const {
      return pnode == obj.pnode;
    }
    self& operator++() {  //前置++ -- 操作返回本体
      pnode = pnode->next;
      return *this;
    }
    self operator++(int) {
      self before(*this); //返回的是之前的
      pnode = pnode->next;
      return before;
    }
    self& operator--() {
      pnode = pnode->pre;
      return *this;
    }
    self operator--(int) {
      self before(*this);
      pnode = pnode->pre;
      return before;
    }
  };
  template<class T>
  class List {
    typedef ListNode<T> Node;//
  public:
    typedef ListIterator<T, T&, T*> iterator;
    typedef ListIterator<T, const T&, const T*> const_iterator;
    //此处体现出来了  Ref  Ptr模板化的好处了  
    List() : head(new Node) {
      head->pre = head->next = head;//双向链表的最初状态
    }
    iterator begin() {//第一个结点
      return iterator(head->next);
    }
    const_iterator begin() const {
      return const_iterator(head->next);
    }
    iterator end() {
      return iterator(head);//返回虚拟头部结点
    }
    const_iterator end() const {
      return const_iterator(head);//虚拟头部结点
    }
    void push_back(const T& val) {
      Node* pTail = head->pre;
      Node* newnode = new Node(val);
      //连接到尾部
      pTail->next = newnode;
      newnode->pre = pTail;
      //成环连接到head上
      newnode->next = head;
      head->pre = newnode;
    }
  private:
    Node* head;//头部指针指向头部结点
  };
  template<class InputIterator, class Function>
  void for_each(InputIterator first, InputIterator last, Function f) {
    while (first != last) {
      f(*first++);
    }
  }
  template<class T>
  struct Print {
    void operator()(const T& val) const {
      cout << val << " ";
    }
  };
}
template<class T>
void PrintList(tyj::List<T>& lt) {
  tyj::for_each(lt.begin(), lt.end(), tyj::Print<T>());
    cout << endl;
}
int main() {
  tyj::List<int> lt;
  for (int i = 0; i < 5; ++i) {
    lt.push_back(i);
  }
  PrintList(lt);
  return 0;
}

四. 函数细节分块分析 (和vector差不大多)

  • 区间范围range构造

  • vector  和 list 都是这种方式实现的, 遍历传入区间，然后调用push_back 复用代码实现传入，一种常用的套路方式.
  • swap为复用代码做准备
void swap(List& lt) {
  ::swap(head, lt.head);
}
  • swap: 非常纯粹简单的换, 将你的成员换给我, 我就成了你，你就成为了我
  • 拷贝构造    (因为有了swap, 我自身初始化为nullptr 避免野指针, 然后将复用range构造代码构造出来的tmp对象换来构造自身)
List(const List& lt) 
  : head(nullptr) {
  List tmp(lt.begin(), lt.end());
  swap(tmp);  //换, 复用范围构造
}


  • 赋值重载
//直接复用拷贝构造出来的lt
List& operator=(List lt) {
  head = nullptr;
  swap(lt);
  return *this;
}
  • 纯纯的复用拷贝构造出来的lt对象，你反正是临时对象，出来作用域就要析构，我直接换掉你底层的堆区资源构造this，复用拷贝构造  (本质还是复用range构造)
  • 移动构造(抢夺将亡对象的堆区资源进行构造)
List(List&& lt) {
    head = nullptr;
  swap(lt);
}

移动构造，直接换，其他啥都不干，为啥它可以这样，拷贝构造都需要复用range范围构造构造构造出来一个tmp才能换,  但是移动构造是直接换,  


核心原因：移动构造传入的参数是一个右值，啥叫作右值，将死对象，临时对象，既然参数本来就是将亡对象，我直接就可使用它的底层堆区资源来构造自身

  • 写完insert() + erase()接口，相当于是写好了六个接口
  • insert()

  • insert(pos, val);  在pos迭代器位置的前面插入一个值为val的结点newnode
  • push_back()  复用insert函数
void push_back(const T& val) {
  insert(end(), val);
    //在end()前插入一个newnode结点
}
  • push_front()  复用insert函数
void push_front(const T& val) {
  insert(begin(), val);
    //在begin前插入一个newnode结点    
}
  • erase();

erase(pos)总结就是三句话:

  1. 拿取pos前pre后next结点
  2. delete pos
  3. pre 和 next结点相连
  • pop_back() 复用erase
void pop_back() {
  erase(--end());
    //删除end()前一个迭代器
    //end() == head 
    //--end() == head->pre == pTail
}
  • pop_front() 复用erase
void pop_front() {
  erase(begin());
    //begin() head->next;
    //head->next == firstnode
    //head是一个空头结点, firstnode才是真实的第一个元素
}

五. 总体代码 + 测试

#include <iostream>
#include <list>
#include <algorithm>
#include <assert.h>
using namespace std;
namespace tyj {
  //链表节点的设计, 双向循环链表
  template<class T>
  struct ListNode {
    ListNode(const T& _val = T())
      : pre(nullptr)
      , next(nullptr)
      , val(_val) {
    }
    ListNode<T>* pre;
    ListNode<T>* next;
    T val;
  };
  //分析一下三个模板??? 为啥要三个，其实这个是STL源码里面这样设计的
  template<class T, class Ref, class Ptr>
  struct ListIterator {
    typedef ListNode<T> Node;
    typedef ListIterator<T, Ref, Ptr > self;
    Node* pnode;  //Iterator管理的指针
    ListIterator(Node* _pnode = nullptr)
      : pnode(_pnode) { 
    }
    Ref operator*() {
      return pnode->val;  //*重载访问val
    }
    Ptr operator->() {    //支持->访问
      return &pnode->val;
    }
    bool operator!=(const self& obj) const {
      return pnode != obj.pnode;
    }
    bool operator==(const self& obj) const {
      return pnode == obj.pnode;
    }
    self& operator++() {  //前置++ -- 操作返回本体
      pnode = pnode->next;
      return *this;
    }
    self operator++(int) {
      self before(*this); //返回的是之前的
      pnode = pnode->next;
      return before;
    }
    self& operator--() {
      pnode = pnode->pre;
      return *this;
    }
    self operator--(int) {
      self before(*this);
      pnode = pnode->pre;
      return before;
    }
  };
  template<class T>
  class List {
    typedef ListNode<T> Node;
  public:
    typedef ListIterator<T, T&, T*> iterator;
    typedef ListIterator<T, const T&, const T*> const_iterator;
    //此处体现出来了  Ref  Ptr模板化的好处了  
    List() : head(new Node) {
      head->pre = head->next = head;//双向链表的最初状态
    }
    template<class InputIterator>
    List(InputIterator first, InputIterator last)
      : head(new Node) {
      head->pre = head->next = head;
      while (first != last) {
        push_back(*first++);
      }
    }
    void swap(List& lt) {
      ::swap(head, lt.head);
    }
    List(const List& lt)
      : head(nullptr) {
      List tmp(lt.begin(), lt.end());
      swap(tmp);  //换, 复用范围构造
    }
    //直接复用拷贝构造出来的lt
    List& operator=(List lt) {
      head = nullptr;
      swap(lt);
      return *this;
    }
    List(List&& lt) {
      swap(lt);
    }
    iterator begin() {//第一个结点
      return iterator(head->next);
    }
    const_iterator begin() const {
      return const_iterator(head->next);
    }
    iterator end() {
      return iterator(head);//返回虚拟头部结点
    }
    const_iterator end() const {
      return const_iterator(head);//虚拟头部结点
    }
    //在pos位置插入一个val 
    void insert(iterator pos, const T& val) {
      assert(pos.pnode);//先断言结点位置存在, 不存在就无法插入
      Node* cur = pos.pnode;//先拿取到结点指针
      Node* pre = cur->pre;
      Node* newnode = new Node(val);//创建新的结点
      pre->next = newnode;
      newnode->pre = pre;
      //新的结点连接pre
      newnode->next = cur;
      cur->pre = newnode;
      //新的结点连接cur
    }
    void push_back(const T& val) {
      //Node* pTail = head->pre;
      //Node* newnode = new Node(val);
      连接到尾部
      //pTail->next = newnode;
      //newnode->pre = pTail;
      成环连接到head上
      //newnode->next = head;
      //head->pre = newnode;
      insert(end(), val);
    }
    void push_front(const T& val) {
      insert(begin(), val);
    }
    void pop_front() {
      erase(begin());
    }
    void pop_back() {
      erase(--end());
    }
    //删除pos迭代器位置元素返回下一个元素
    iterator erase(iterator pos) {
      assert(pos.pnode);//存在才可以做删除操作
      assert(pos != end());
      //拿取到前面一个结点和后一个结点
      Node* pre = pos.pnode->pre;
      Node* next = pos.pnode->next;
      //删除现在iterator
      delete pos.pnode;
      pre->next = next;
      next->pre = pre;
      return iterator(next);
    }
    void clear() {
      Node* p = head->next, *q;
      while (p != head) {
        q = p->next;
        delete p;
        p = q;
      }
      delete head;
    }
    size_t size() {
      size_t ans = 0;
      Node* p = head->next;
      while (p != head) {
        ans += 1;
        p = p->next;
      }
      return ans;
    }
    ~List() {
      if (head != nullptr)
        clear();
      head = nullptr;
    }
  private:
    Node* head;//头部指针指向头部结点
  };
  template<class InputIterator, class Function>
  void for_each(InputIterator first, InputIterator last, Function f) {
    while (first != last) {
      f(*first++);
    }
  }
  template<class T>
  struct Print {
    void operator()(const T& val) const {
      cout << val << " ";
    }
  };
}
template<class T>
void PrintList(tyj::List<T>& lt) {
  tyj::for_each(lt.begin(), lt.end(), tyj::Print<T>());
  cout << endl;
}
// 测试List的构造
void TestList1()
{
  tyj::List<int> l1;
  int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
  tyj::List<int> l3(array, array + sizeof(array) / sizeof(array[0]));
  PrintList(l3);
  tyj::List<int> l4(l3);
  PrintList(l4);
  l1 = l4;
  PrintList(l1);
}
void TestList2()
{
  // 测试PushBack与PopBack
  tyj::List<int> l;
  l.push_back(1);
  l.push_back(2);
  l.push_back(3);
  PrintList(l);
  l.pop_back();
  l.pop_back();
  PrintList(l);
  l.pop_back();
  cout << l.size() << endl;
  // 测试PushFront与PopFront
  l.push_front(1);
  l.push_front(2);
  l.push_front(3);
  PrintList(l);
  l.pop_front();
  l.pop_front();
  PrintList(l);
  l.pop_front();
  cout << l.size() << endl;
}
void TestList3()
{
  int array[] = { 1, 2, 3, 4, 5 };
  tyj::List<int> l(array, array + sizeof(array) / sizeof(array[0]));
  auto pos = l.begin();
  l.insert(l.begin(), 0);
  PrintList(l);
  ++pos;
  l.insert(pos, 2);
  PrintList(l);
  l.erase(l.begin());
  l.erase(pos);
  PrintList(l);
  // pos指向的节点已经被删除，pos迭代器失效
  cout << *pos << endl;
  auto it = l.begin();
  while (it != l.end())
  {
    it = l.erase(it);
  }
  cout << l.size() << endl;
}
int main() {
  //tyj::List<int> lt;
  //for (int i = 0; i < 5; ++i) {
  //  lt.push_back(i);
  //}
  //PrintList(lt);
  //int arr[5] = { 1, 2, 3, 4, 5 };
  //tyj::List<int> lt2(arr, arr + 5);
  //PrintList(lt2);
  /*TestList1();*/
  /*TestList2();*/
  TestList3();
  return 0;
}

六. 总结

就list对比vector而言, list更能够体现出来迭代器的设计重要性


本质来说STL的list底层就是一个双向循环的链表(数据结构)而已,  其中最最有价值的部分是  iterator的设计上面.   iterator是如何粘合  容器 + 算法的，这一点特别的重要


首先我们写链表需要先封装出来一个ListNode结构体:    


我们需要管理ListNode* 的指针于是我们需要设计出ListIterator类来支持各种指针的运算符重载，来支持特定的容器遍历方式，粘合算法


写STL 或者写一些小东西的经验之谈


首先看是否存在一定的框架，或者官方文档，如果存在，将其总体框架分成组件，将重要组件分别设计实现，针对重要的接口进行文档阅读，分析实现.


写出框架简单测试，框架没有问题之后我们可以看见小小的效果，喜悦心理，然后再慢慢的一点一点的啃食重点接口。。写完接口要及时测试


最终，对于整体代码进行各种特别情景下的测试。。。 找debug


感谢你阅读完了小杰的本篇文章，小杰后序还会根据自身掌握水平持续推出一些STL的设计书写思路，如果您觉着小杰写的还不错，劳烦关注支持一下，非常感谢，最后还是祝福大家都学习的学业专业有成，工作的都升职加薪


文章标签：
C++
容器
算法
存储
关键词：
stl链表
链表分析
链表迭代器
链表组件
链表stl
游客yarbwh6ylvlvk
目录
相关文章
我是夜阑的狗
|
6月前
|
存储
LeetCode刷题---817. 链表组件（哈希表）
LeetCode刷题---817. 链表组件（哈希表）
我是夜阑的狗
40 0
Sessy
|
6月前
＜数据结构＞五道LeetCode链表题分析.环形链表，反转链表，合并链表，找中间节点.
＜数据结构＞五道LeetCode链表题分析.环形链表，反转链表，合并链表，找中间节点
Sessy
53 1
Eternity._
|
5月前
|
C++ 容器
【C++进阶】深入STL之list：高效双向链表的使用技巧
【C++进阶】深入STL之list：高效双向链表的使用技巧
Eternity._
59 0
小李很执着
|
6月前
|
存储 C语言
链表—初始化指针变和创建新的节点------区别应用分析
链表—初始化指针变和创建新的节点------区别应用分析
小李很执着
45 0
YoungMLet
【Leetcode -817.链表组件 -1019.链表中的下一个更大节点】
【Leetcode -817.链表组件 -1019.链表中的下一个更大节点】
YoungMLet
47 0
泡沫o0
|
6月前
|
存储 算法 C语言
【C/C++ 链表结构】探索链表迭代器：C++实现的深入分析与优化策略
【C/C++ 链表结构】探索链表迭代器：C++实现的深入分析与优化策略
泡沫o0
136 0
是谢添啊
力扣203移除链表元素：思路分析+代码实现+方法总结（伪头节点法&递归）
力扣203移除链表元素：思路分析+代码实现+方法总结（伪头节点法&递归）
是谢添啊
102 0
菊头蝙蝠
|
6月前
leetcode-817：链表组件
leetcode-817：链表组件
菊头蝙蝠
41 0
爱因诗贤
链表翻转循环和递归写法(画图分析)
链表翻转循环和递归写法(画图分析)
爱因诗贤
33 0
aliyun_11084
|
存储 算法 C++
4.1 C++ STL 动态链表容器
List和SList都是C++ STL中的容器，都是基于双向链表实现的，可以存储可重复元素的特点。其中，List内部的节点结构包含两个指针一个指向前一个节点，一个指向后一个节点，而SList只有一个指针指向后一个节点，因此相对来说更节省存储空间，但不支持反向遍历，同时也没有List的排序功能。双向链表的数据元素可以通过链表指针串接成逻辑意义上的线性表，不同于采用线性表顺序存储结构的`Vector`和`Deque`容器，双向链表中任一位置的元素，查找，插入和删除，都具有高效的常数阶算法时间复杂度O(1).
aliyun_11084
54 0