list

╰半橙微兮° 2022-05-17 01:21 82阅读 0赞

#### 写在前面 ####

> STL源码剖析：list

#### 主要内容 ####

> list也就是链表结构。list本身和list节点是不同的结构。

**list节点**

template <class T>
    struct __list_node {
      typedef void* void_pointer;
      void_pointer next;
      void_pointer prev;
      T data;
    };

显然list是一个双向链表。

**list迭代器**：  
支持递增，递减，取值，成员存取操作。所以list迭代器是一个Bidirectional iterators。list的重要性质：插入操作连接操作都不会造成原有的list迭代器失效。删除操作只会使得被删除节点的迭代器失效。

template<class T, class Ref, class Ptr>
    struct __list_iterator {
      typedef __list_iterator<T, T&, T*>             iterator;
      typedef __list_iterator<T, const T&, const T*> const_iterator;
      typedef __list_iterator<T, Ref, Ptr>           self;
    
      typedef bidirectional_iterator_tag iterator_category;
      typedef T value_type;
      typedef Ptr pointer;
      typedef Ref reference;
      typedef __list_node<T>* link_type;//嵌套类型定义
      typedef size_t size_type;
      typedef ptrdiff_t difference_type;
    
      link_type node;//list迭代器围绕这个节点操作list。迭代器封装了这个节点指针。
    
      __list_iterator(link_type x) : node(x) {}
      //提供节点指针到iterator的构造函数，可以进行隐式类型转换。
      __list_iterator() {}
      __list_iterator(const iterator& x) : node(x.node) {}
    
      bool operator==(const self& x) const { return node == x.node; }
      bool operator!=(const self& x) const { return node != x.node; }
      reference operator*() const { return (*node).data; }
    
    #ifndef __SGI_STL_NO_ARROW_OPERATOR
      pointer operator->() const { return &(operator*()); }
    #endif /* __SGI_STL_NO_ARROW_OPERATOR */
    
      self& operator++() { 
        node = (link_type)((*node).next);
        return *this;
      }
      self operator++(int) { 
        self tmp = *this;
        ++*this;
        return tmp;
      }
      self& operator--() { 
        node = (link_type)((*node).prev);
        return *this;
      }
      self operator--(int) { 
        self tmp = *this;
        --*this;
        return tmp;
      }
    };

> list还是一个环状双向链表，只需要一个指针就可以完整的表现整个链表。

protected:
      link_type node;

让指针node指向置于尾端的一个空白节点，就能达到前闭后开的要求。

iterator begin() { return (link_type)((*node).next); }
    const_iterator begin() const { return (link_type)((*node).next); }
    iterator end() { return node; }
    const_iterator end() const { return node; }

> insert() 插入是指在…之前插入。

iterator insert(iterator position, const T& x) {
        link_type tmp = create_node(x);
        tmp->next = position.node;
        tmp->prev = position.node->prev;
        (link_type(position.node->prev))->next = tmp;
        position.node->prev = tmp;
        return tmp;
      }

> push\_back() push\_front()

void push_front(const T& x) { insert(begin(), x); }
    void push_back(const T& x) { insert(end(), x); }