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

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

list的介绍

  1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。
  2. list的底层是用双向链表实现的(线性),每个元素都存在相互独立的节点中,每个节点都有一个指针分别指向前一个节点和后一个节点。
  3. 因为底层结构是链表,list的插入和删除操作是非常高效的,这与vector容器相反。但是由于链表的结构特点,list的各个节点之间的物理地址是不连续的,也就导致了任意访问某个节点的效率较低。
  4. 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)
//用[first, last)区间中的元素构造list
list (InputIterator first, 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()

  1. begin与end为正向迭代器,对迭代器执行++操作,迭代器向后移动
  2. 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;
  };
}


相关文章
|
2天前
|
存储 缓存 编译器
【C++进阶】深入STL之list:模拟实现深入理解List与迭代器
【C++进阶】深入STL之list:模拟实现深入理解List与迭代器
|
2天前
|
C++ 容器
【C++进阶】深入STL之list:高效双向链表的使用技巧
【C++进阶】深入STL之list:高效双向链表的使用技巧
|
5天前
|
存储 Java 测试技术
滚雪球学Java(57):解密Java中List接口底层实现原理
【6月更文挑战第11天】🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
21 2
滚雪球学Java(57):解密Java中List接口底层实现原理
|
9天前
|
Java
JavaSE——集合框架一(4/7)-List系列集合:LinkedList集合的底层原理、特有方法、队列、栈
JavaSE——集合框架一(4/7)-List系列集合:LinkedList集合的底层原理、特有方法、队列、栈
7 0
|
9天前
|
Java 索引
JavaSE——集合框架一(3/7)-List系列集合:特点、方法、遍历方式、ArrayList集合的底层原理
JavaSE——集合框架一(3/7)-List系列集合:特点、方法、遍历方式、ArrayList集合的底层原理
7 2
|
11天前
|
存储 C++
C++初阶学习第十一弹——探索STL奥秘(六)——深度刨析list的用法和核心点
C++初阶学习第十一弹——探索STL奥秘(六)——深度刨析list的用法和核心点
20 7
|
13天前
|
C++ 容器
9.STL中list的常见操作(图文并茂)
9.STL中list的常见操作(图文并茂)
|
23天前
|
存储 C++ 容器
黑马c++ STL部分 笔记(7) list容器
黑马c++ STL部分 笔记(7) list容器
|
1月前
|
存储 编译器 C++
【C++/STL】list(常见接口、模拟实现、反向迭代器、)
【C++/STL】list(常见接口、模拟实现、反向迭代器、)
7 0
|
1月前
|
存储 缓存 编译器
【C++进阶(五)】STL大法--list模拟实现以及list和vector的对比
【C++进阶(五)】STL大法--list模拟实现以及list和vector的对比