【STL】list的底层原理及其实现-阿里云开发者社区

list的介绍

list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

list的底层是用双向链表实现的（线性），每个元素都存在相互独立的节点中，每个节点都有一个指针分别指向前一个节点和后一个节点。

因为底层结构是链表，list的插入和删除操作是非常高效的，这与vector容器相反。但是由于链表的结构特点，list的各个节点之间的物理地址是不连续的，也就导致了任意访问某个节点的效率较低。

list的空间消耗会比vector大（存储相同个数的元素），因为每个节点还需要给前后指针开空间。

list的整体结构设计

list可以分为三部分：一个是list类本身，一个是节点类，一个是迭代器类。

list类的成员变量一般只有头节点（哨兵），除了负责初始化以外还负责声明和定义插入删除功能。

ListNode节点类封装了list的元素以及前后节点的指针，还负责new出节点时的初始化。

Iterator迭代器类封装了指向节点的指针ListNode*,还负责重载++、–、！=等运算符。为什么要在迭代器内部重载呢？

跟vector不同的是，由于list迭代器指向的是一个节点，且节点间物理地址不连续，向前移动或者向后移动都不能用指针直接去加减。

list的节点类

 // List的节点类
 template<class T>
 struct ListNode
 {
     ListNode(const T& val = T());
     ListNode<T>* _pPre;
     ListNode<T>* _pNext;
     T _val;
 };

list的迭代器类

template<class T, class Ref, class Ptr>
class ListIterator
{
    typedef ListNode<T>* PNode;
    typedef ListIterator<T, Ref, Ptr> Self;
public:
    ListIterator(PNode pNode = nullptr);
    ListIterator(const Self& l);
    T& operator*();
    T* operator->();
    Self& operator++();
    Self operator++(int);
    Self& operator--();
    Self& operator--(int);
    bool operator!=(const Self& l);
    bool operator==(const Self& l);
private:
    PNode _pNode;
};

list类

template<class T>
class list
{
    typedef ListNode<T> Node;
    typedef Node* PNode;
public:
    typedef ListIterator<T, T&, T*> iterator;
    typedef ListIterator<T, const T&, const T&> const_iterator;
public:
    ///
    // List的构造
    list();
    list(int n, const T& value = T());
    template <class Iterator>
    list(Iterator first, Iterator last);
    list(const list<T>& l);
    list<T>& operator=(const list<T> l);
    ~list();

    ///
    // List Iterator
    iterator begin();
    iterator end();
    const_iterator begin();
    const_iterator end();
    ///
    // List Capacity
    size_t size()const;
    bool empty()const;

};

list的构造

list有四个构造函数：无参构造、拷贝构造、连续赋值构造、迭代器构造。

//构造的list中包含n个值为val的元素
list (size_type n, const value_type& val = value_type())
//构造空的list，初始化哨兵节点
list() 
//拷贝构造
list (const list& x)
//用[ﬁrst, last)区间中的元素构造list
list (InputIterator ﬁrst, InputIterator last)

代码模拟实现：

    void Empty_Init() {
      head = new Node;
      head->_pre = head;
      head->_next = head;
      head->_val = -1;
      sz = 0;
    }
    //构造
    list()
    {
      Empty_Init();
    }
    list(size_t n, const T& value = T())
    {
      Empty_Init();
      for (size_t i = 0; i < n; i++) {
        push_back(value);
      }
      sz = n;
    }
    //拷贝构造
    list(const list<T>& lt) {
      Empty_Init();
      for (auto& it : lt) {
        push_back(it);
      }
    }
    //迭代器构造
    template <class IIterator>
    list(IIterator first, IIterator last) {
      Empty_Init();
      while (first != last) {
        push_back(*first);
        first++;
      }
    }

list节点类的实现

节点类的成员变量就是前后指针以及节点的元素值。此外还需注意构造节点时的初始化工作。

template<class T>
class ListNode {
public:
  ListNode(const T& val = T())
    :_val(val)
    , _pre(nullptr)
    , _next(nullptr)
  {

  }
  ListNode<T>* _pre;
  ListNode<T>* _next;
  T _val;
};

list 迭代器Iterator的使用以及实现

Iterator的使用

在上面iterator类的声明中我们可以看到，不同的容器其迭代器的实现方式是不一样的。在string和vector中的iterator本质是一个指针。但是list的迭代器是一个像指针的类。

//返回第一个元素或最后一个的迭代器
begin()
end()

//rbegin返回第一个元素的reverse_iterator,即end位置，rend返回最后一个元素下一个位置的
//reverse_iterator,即begin位置
rbegin()
rend()

begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
代码演示：

Iterator的底层实现

先实现一个正向的迭代器类。因为涉及到存在const修饰迭代器指向的节点，所以在设计迭代器的时候需要同时设计出const版本（const是修饰节点，不是迭代器本身）。这里我们可以使用模板，模板里面有三个类型：节点数据类型、引用类型、指针类型。

值得注意的是，由于我们需要在迭代器类里访问节点Node类型的成员变量，所以可以将Iterator设为Node类的友元类，或者开放Node类的权限。

迭代器的构造函数的实现：

ListIterator(Node* node)
  :_node(node)
{}

我这里设计的比较简单，只实现了单参的构造函数，可以支持基本的隐式类型转换。

重载*:

Ref operator* () {
  return _node->_val;
}

重载迭代器的移动操作符++、--:

Self& operator++() {
  _node = _node->_next;
  return *this;
}
Self& operator++(int) {//后置++
  Self temp(*this);
  _node = _node->_next;
  return temp;
}

Self& operator--() {
  _node = _node->_pre;
  return *this;
}

Self& operator--(int) {//后置--
  Self temp(_node);
  _node = _node->_pre;
  return temp;
}

重载->：

Ptr operator ->() {
  return &_node->_val;
}

由于我们想把迭代器当指针使用，重载->是必要的，那么为什么是返回节点元素的地址呢？其实当我们在使用迭代器->时，编译器会自动优化成->->。比如我们的节点元素类型是一个类，我们有时需要访问节点元素类中的成员变量，此时希望通过迭代器->能直接访问到。

观察以下代码：

其中t是一个结构体类型，当我们用list存这样的节点并试图遍历节点中的a1的值时，(*it)得到的是t类型，如果我们想要输出t中的a1，就必须写成（*it）.a1。

我们希望迭代器能像指针一样，it->a1这样就能直接访问a1的元素，于是我们重载一个->,这个->的作用其实等价于it->->a1也就是it.operator->()->a1。这是编译器帮我们优化了。

反向迭代器

方向迭代器和普通的迭代器功能基本一致，只不过由于起始位置是在哨兵位，解引用时需要先往前面移动一个节点再返回其节点元素值

Ref operator* () {
  Self temp(_node);
  temp++;
  return temp._node->_val;
}

此外移动的方向也和普通迭代器相反，是向节点的前一个节点方向移动。

  Self& operator--() {
    _node = _node->_next;
    return *this;
  }
  Self& operator--(int) {//后置--
    Self temp(*this);
    _node = _node->_next;
    return temp;
  }

  Self& operator++() {
    _node = _node->_pre;
    return *this;
  }

  Self& operator++(int) {//后置++
    Self temp(_node);
    _node = _node->_pre;
    return temp;
  }

其它功能和普通迭代器几乎一致。

list与vector的比较

list和vector各种代表着的是链表和数组。它们之间的具体区别其实在前面已经讲过了。

链表的优缺点

顺序表的优缺点

迭代器的区别：

vector的迭代器是原生态指针，list的迭代器是对原生态指针(节点指针)进行封装。

vector在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效。

而list插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响

实现list类

#define _CRT_SECURE_NO_WARNINGS 1
#include<assert.h>
#include<iostream>

namespace bite {

  //节点
  template<class T>
  class ListNode {
  public:
    ListNode(const T& val = T())
      :_val(val)
      , _pre(nullptr)
      , _next(nullptr)
    {

    }
    ListNode<T>* _pre;
    ListNode<T>* _next;
    T _val;
  };


  //反向迭代器
  template<class T, class Ref, class Ptr>
  class ReserveListIterator {
  public:
    typedef ListNode<T> Node;
    typedef ReserveListIterator<T, Ref, Ptr> Self;

    ReserveListIterator(Node* node)
      :_node(node)
    {}
    //重载
    Ref operator* () {
      Self temp(_node);
      temp++;
      return temp._node->_val;
    }

    Self& operator--() {
      _node = _node->_next;
      return *this;
    }
    Self& operator--(int) {//后置--
      Self temp(*this);
      _node = _node->_next;
      return temp;
    }

    Self& operator++() {
      _node = _node->_pre;
      return *this;
    }

    Self& operator++(int) {//后置++
      Self temp(_node);
      _node = _node->_pre;
      return temp;
    }

    bool operator!=(const Self& p) {
      return _node != p._node;
    }
    //T*/const T*
    Ptr operator ->() {
      return &_node->_val;
    }
    bool operator==(const Self& p) {
      return _node == p._node;
    }
    Node* _node;
  };


  //迭代器
  template<class T, class Ref, class Ptr>//T表示节点数据类型，Ref表示T&、Ptr表示T*类型
  class ListIterator {
  public:
    typedef ListNode<T> Node;
    typedef ListIterator<T, Ref, Ptr> Self;

    ListIterator(Node* node)
      :_node(node)
    {}
    //重载
    Ref operator* () {
      return _node->_val;
    }

    Self& operator++() {
      _node = _node->_next;
      return *this;
    }
    Self& operator++(int) {//后置++
      Self temp(*this);
      _node = _node->_next;
      return temp;
    }

    Self& operator--() {
      _node = _node->_pre;
      return *this;
    }

    Self& operator--(int) {//后置--
      Self temp(_node);
      _node = _node->_pre;
      return temp;
    }

    bool operator!=(const Self& p) {
      return _node != p._node;
    }
    //T*/const T*
    Ptr operator ->() {
      return &_node->_val;
    }
    bool operator==(const Self& p) {
      return _node == p._node;
    }
    Node* _node;
  };

  template<class T>
  class list {
  public:
    //节点
    typedef ListNode<T> Node;
    typedef Node* pNode;

    //迭代器
    typedef ListIterator<T, T&, T*> Iterator;
    typedef ListIterator<T, const T&, const T*> const_Iterator;
    typedef ReserveListIterator<T, T&, T*> Reserve_Iterator;
    typedef ReserveListIterator<T, const T&, const T*> const_Reserve_Iterator;
    

  public:

    void Empty_Init() {
      head = new Node;
      head->_pre = head;
      head->_next = head;
      head->_val = -1;
      sz = 0;
    }

    //构造
    list()
    {
      Empty_Init();
    }

    list(size_t n, const T& value = T())
    {
      Empty_Init();
      for (size_t i = 0; i < n; i++) {
        push_back(value);
      }
      sz = n;
    }

    //拷贝构造
    list(const list<T>& lt) {
      Empty_Init();
      for (auto& it : lt) {
        push_back(it);
      }
    }

    //迭代器构造
    template <class IIterator>
    list(IIterator first, IIterator last) {
      Empty_Init();
      while (first != last) {
        push_back(*first);
        first++;
      }
    }

    //析构
    ~list() {
      Iterator it = begin();
      while (it != end()) {
        it = erase(it);
      }
      delete head;
      sz = 0;
    }

    void swap(list<T> lt) {
      std::swap(lt.head, head);
      std::swap(sz, lt.sz);
    }


    //普通迭代器
    Iterator begin() {
      return head->_next;
    }
    Iterator end() {
      return head;
    }
    //const迭代器
    const_Iterator begin() const {
      return head->_next;
    }
    const_Iterator end() const {
      return head;
    }
    //反向迭代器
     Reserve_Iterator  rbegin() {
       return head;
     }
     Reserve_Iterator  rend() {
       return head->_next;
     }

     const_Reserve_Iterator rbegin() const {
       return head;
     }
     const_Reserve_Iterator rend() const {
       return head->_next;
     }

    //插入
    void insert(Iterator pos, const T& val) {
      Node* newnode = new Node(val);
      Node* cur = pos._node;

      newnode->_pre = cur->_pre;
      newnode->_next = cur;
      cur->_pre->_next = newnode;
      cur->_pre = newnode;
      sz++;
    }
    //删除
    Iterator erase(Iterator pos) {
      assert(sz > 0);
      Node* cur = pos._node;
      Node* t = cur->_next;
      cur->_pre->_next = cur->_next;
      cur->_next->_pre = cur->_pre;
      delete cur;
      sz--;
      return t;
    }
    //尾插
    void push_back(const T& val) {
      insert(end(), val);
      //size++;
    }


    //操作符重载
    list<T>& operator = (list<T> lt) {
      swap(lt);
      return *this;
    }


    // List Capacity
    size_t size()const {
      return sz;
    }
    bool empty()const {
      return sz == 0;
    }

  private:
    pNode head;
    size_t sz;
  };
}

【STL】list的底层原理及其实现

list的介绍

list的整体结构设计

list的构造

代码模拟实现：

list节点类的实现

list 迭代器Iterator的使用以及实现

Iterator的使用

Iterator的底层实现

反向迭代器

list与vector的比较

实现list类

热门文章

最新文章

相关课程

相关电子书

相关实验场景