Data-Structure3

Before: 最近装了个虚拟机（ 为了Games101配的环境 ），结果很不幸出了一点小小的问题，使得正宫WSL用不了辣（正在紧急维修中）。但是DS的学习是不可中断的！冲！（ 打下这段文字时JaneZ正坐在拥挤的省人民医院诊室门口的地上，脚都麻了 ）

Data Structure 3 双链表 容器 迭代器

在上一节中，我们非常详细地实现了一个单链表类（算是对上学期所学进行了一个复习），我个人认为，双链表与单链表并不存在多么显著的区别。所以本章节中关于双链表的部分会相对比较简洁。

双链表

• 定义：（和单链表不同的地方）每个结点既保存直接后继结点的地址，也保存直接前驱结点的地址（单链表只保存直接后继结点的地址）
• 拥有直接前驱结点的地址实际上意味着双链表可以从后向前访问
• 双链表中既包含了一个头结点head ,还包含了一个尾结点tail；保存一个双链表事实上就是保存头尾两个结点的地址
  下面是一个双链表类的定义：

  template<class elemType>
  class dLinkList: public list <elemType>{
  private:
      struct node{
          elemType data;
          node *prev;
          node *next;
  
          node(const elemType& x ,node *p = nullptr, node *n = nullptr){
              data = x;
              prev = p;
              next = n;
          }
          node():prev(nullptr),next(nullptr){}
          ~node(){}
      };
  node *head;
  node *tail;
  int currentLength;
  node *move(int i)const;
  
  public:
      dLinkList();
      ~dLinkList(){
          clear();
          delete head;
          delete tail;
      }
      void clear();
      int length() const{
          return currentLength;
      }
      void insert(int i , const elemType &x);
      void remove(int i);
      int search(const elemType &x)const;
      elemType visit(int i) const;
      void traverse() const;
  };

容器与迭代器

• 本质上我们所说的数据结构，就是在保存一组相互之间具有某种关系的数据元素。而C++把每个数据结构的实现称为一个容器
• 在设计容器时，我们通常为每种容器定义一个相应的表示其中对象位置的类型，称作迭代器，相当于指向容器中对象的指针
• 设计一个迭代器包括2个部分:
  (1) 如何标识容器中某一对象的位置
  (2) 如何实现迭代器的操作
• 为了方便用户使用，STL将迭代器类（iterator , const_iterator）定义成相应容器类的公有内嵌类
• 注意：iterator类可通过迭代器修改指向元素的值，而const_iterator只可以通过迭代器读取指向元素的值

下面是一些迭代器自身的常见操作：

这是我手搓的STL list类中内嵌iterator类（ const_iterator类几乎同理，只是const版本🤣🤣🤣 ）的实现：

class iterator {
    private:
        node* ptr;
    public:
        iterator(node* p = nullptr) : ptr(p) {}

        iterator& operator++() {
            ptr = ptr->next;
            return *this;
        }

        iterator& operator--() {
            ptr = ptr->prev;
            return *this;
        }

        iterator operator++(int) {
            iterator tmp = *this;
            ++(*this);
            return tmp;
        }

        iterator operator--(int) {
            iterator tmp = *this;
            --(*this);
            return tmp;
        }

        T& operator*() const noexcept {
            return ptr->data;
        }

        T* operator->() const noexcept {
            return &(ptr->data);
        }

        /* A operator to check whether two iterators are same (pointing to the same memory) */
        friend bool operator==(const iterator& a, const iterator& b) {
           return (a.ptr == b.ptr);
        }

        friend bool operator!=(const iterator& a, const iterator& b) {
            return (a.ptr != b.ptr);
        }

        friend class list;
};

以线性表为例

下面是一些list类和vector类中的迭代器相关操作：

这是我手搓的STL list类中与迭代器相关的一些操作的实现🫡🫡🫡：

注：其实存在一些问题（ 因为我的实现并没有考虑模板类型T 不具有默认构造函数的情况 😢 ）

/* Return an iterator pointing to the first element. */
iterator begin() noexcept {
    return iterator(head->next);
}

const_iterator cbegin() const noexcept {
    return const_iterator(head->next);
}

/* Return an iterator pointing to one past the last element. */
iterator end() noexcept {
    return iterator(tail);
}

const_iterator cend() const noexcept {
    return const_iterator(tail);
}

iterator insert(iterator pos, const T& value) {
    node* n = new node(value, pos.ptr->prev, pos.ptr);
    pos.ptr->prev->next = n;
    pos.ptr->prev = n;
    ++ currentLength;
    return iterator(n);
}

iterator erase(iterator pos) noexcept {
    if (pos == end()) {
        return end();
    }
    node* tmp = pos.ptr;
    iterator it(tmp->next);
    tmp->prev->next = tmp->next;
    tmp->next->prev = tmp->prev;
    delete tmp;
    -- currentLength;
    return it;
}