解密list的底层奥秘

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨
🐻强烈推荐优质专栏: 🍔🍟🌯C++的世界(持续更新中)
🐻推荐专栏1: 🍔🍟🌯C语言初阶
🐻推荐专栏2: 🍔🍟🌯C语言进阶
🔑个人信条: 🌵知行合一
金句分享:
✨即使人生还有无数次失望的可能性,✨
✨但我还是想活在理想主义的乌托邦里.✨

本篇通过模拟实现list的构造函数,迭代器,和部分成员函数以帮助大家更加深层的理解list的原理,希望看完这篇文章使得友友们对list有了更加深层的理解.

一、list底层框架

list的底层是一个带头双向循环链表.

(1) 节点类

因为list中节点可能存储各种类型的值,所以这里使用了一个模板参数T.

list
list
…

 	// List的节点类
    template<class T>
    struct list_node
    {
        list_node(const T& val = T())
            :_val(val)
        {}
        //这里的 T() 表示使用类型 T 的默认构造函数创建一个对象，
        //它将调用 T 类型的默认构造函数来初始化 val。如果类型 T 没有提供默认构造函数，那么代码将无法编译通过。
        list_node<T>* _prev=nullptr;	//指向前驱结点
        list_node<T>* _next=nullptr;	//指向后继结点
        T _val;							//存储数据
    };
1
2
3
4
5
6
7
8
9
10
11
12
13

(2) 迭代器类

很多小伙伴会疑问,为什么一个迭代器类却使用了三个模板参数,是不是有些多余呢?

其实不然,牛牛依次为大家解释.

1. class T: 是结点类的存储不同数据所需要使用的模板参数.该模板参数表示要处理的元素的类型。它可以是任意类型，例如整数、浮点数、自定义类等等。在模板实例化时，需要提供一个具体的类型。

2. Ref: 该模板参数表示指向元素类型 T 的引用。它定义了对元素的引用类型，在实例化模板时，将使用指定的引用类型来操作元素。

3. Ptr: 该模板参数表示指向元素类型 T 的指针。它定义了指向元素的指针类型，在实例化模板时，将使用指定的指针类型来操作元素。

template
意味着
list_iterator;

list的迭代器用来遍历链表中的元素,外部通过迭代器的++和--进行链表的元素访问,这是一种封装,隐藏内部list的实现细节,外部只能通过迭代器的方式访问.

	//迭代器类
	template<class T, class Ref, class Ptr>
  	struct list_iterator
  	{
      typedef list_node<T> Node;
      typedef list_iterator<T, Ref, Ptr> self;//self表示自己
     
      list_iterator(Node* node);	//构造
      list_iterator(const self& list);     //拷贝构造
      Ref operator*();
      Ptr operator->();
      //前置++
      self& operator++();  
      //后置++
      self operator++(int);
      //前置--
      self& operator--();
      //后置--
      self& operator--(int);
      bool operator!=(const self& list) const; 
      bool operator==(const self& list);
      
      //成员变量
      Node* _node;
 	 };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

(3) list类

  template<class T>
    class list
    {
        typedef list_node<T> Node;
    public:
        typedef list_iterator<T, T&, T*> iterator;
        typedef list_iterator<T, const T&, const T*> const_iterator;
        
        list()//(无参构造)
        //n个value构造
        list(int n, const T& value = T());
        //迭代器区间构造
        template <class Iterator>
        list(Iterator first, Iterator last);    
        //拷贝构造
        list(const list<T>& list);
        //各种成员函数
        /...
        //析构函数
        ~list();
        iterator begin();       
        iterator end();
        //常属性迭代器
        const_iterator begin()const;
        const_iterator end()const; 
    private:
        Node* _head;
        size_t _size;
    };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

二、构造函数

对于带头双向循环链表,它的初始化操作是必须的,因为必须创建一个头指针.

对于list的构造函数,它是很多种方式的,例如:无参构造,n个val构造,迭代器区间构造等.
对于每个构造,必须前进行最初的初始化操作,为了避免代码冗余,我们将这个部分单独写成一个初始化操作的函数.

如下:

 void  Init_List()
  {
	_head = new Node;	//创建头指针
    _head->_prev = _head;
    _head->_next = _head;
    _size = 0;
  }

1
2
3
4
5
6
7
8

(1) 无参构造

调用Init_List();初始化函数即可.

 list()//初始化很重要(无参构造)
  {
      Init_List();
  }
1
2
3
4

(2) n个value构造

1. 进行初始化操作.
2. 尾插n个value.

	//n个value构造
   list(int n, const T& value = T())
   {
       Init_List();
       while (n--)
       {
           push_back(value);
       }
   }
1
2
3
4
5
6
7
8
9

(3) 迭代器区间构造

1. 进行初始化操作.
2. 利用迭代器的特性,一次将区间中的数据尾插入链表.

//迭代器区间构造
  template <class Iterator>
  list(Iterator first, Iterator last)
  {
      Init_List();
      while (first != last)
      {
          push_back(*first);
          ++first;
      }
  }
1
2
3
4
5
6
7
8
9
10
11

(4) 拷贝构造

链表在物理空间上是不连续的,所以,对于参数是另一个链表的拷贝构造,只能遍历链表进行依次插入数据.

	//拷贝构造
	list(const list<T>& list)
	{
	    Init_List();
	    auto it = list.begin();
	    while (_size!=list._size)
	    {
	        push_back(*it);
	        it++;
	    }
	}
1
2
3
4
5
6
7
8
9
10
11

三、迭代器

迭代器的实现

① 构造

迭代器本质就是一个 Node* _node;结点类的指针.
对于迭代器的构造函数,只需要将结点的地址传过来即可.

list_iterator(Node* node)			//默认构造
 :_node(node) {}
list_iterator(const self& list)     //拷贝构造
 :_node(list._node){}
1
2
3
4

② *和->

(1) *
*运算符重载,表示对迭代器进行解引用.
使用场景:

list<int>::iterator it = L1.begin();
int start=*it;
1
2

很明显,*运算符是需要获取结点所存储的数据.为了减少拷贝以及对数据进行修改,这里采用传引用(Ref )返回.

 Ref operator*() {
     return _node->_val;//获取该结点的数据
 }
1
2
3

(2) ->

上面链表中的数据是简单的类型int

Ptr operator->() {
       return &_node->_val;
       // 等价于 return &(_node->_val);
   }
1
2
3
4

③ 前置++与后置++

对于链表,迭代器++表示向后访问下一个(后继)结点.学过链表的友友们应该知道.
也就是 _node = _node->_next;

前置++,返回++后的结点的迭代器
后置++,返回++前的结点的迭代器

 //前置++
  self& operator++() {
      _node = _node->_next;
      return *this;
  }

  //后置++
  self operator++(int) {
      Node* tmp=_node;        //保存++之前的值
      _node = _node->_next;
      return tmp;             //返回++之前的值
  }
1
2
3
4
5
6
7
8
9
10
11
12

④ 前置–与后置–

同理,返回当前结点迭代器的前驱结点.
也就是:_node = _node->_prev;

前置–,返回–后的结点的迭代器
后置–,返回–前的结点的迭代器

 //前置--
 self& operator--(){
     _node = _node->_prev;
     return *this;
 }

 //后置--
 self& operator--(int){
     Node* tmp = _node;          //保存 -- 之前的值
     _node = _node->_prev;
     return tmp;                 //返回 -- 之前的值
 }
1
2
3
4
5
6
7
8
9
10
11
12

⑤ 比较运算符

比较迭代器是否相等,实际就是比较迭代器所指向的结点是否相等.

 bool operator!=(const self& list) const
  {
      return _node != list._node;
  }
  
  bool operator==(const self& list){
      return _node == list._node;
  }
1
2
3
4
5
6
7
8

list类中的迭代器

iterator begin(): 返回第一个有效元素位置的迭代器
iterator end(): 返回最后一个有效元素位置的迭代器

	typedef list_iterator<T, T&, T*> iterator;
	typedef list_iterator<T, const T&, const T*> const_iterator;
	iterator begin()
	 {
      return _head->_next;
      //也可以强转一下
      //return iterator(_head->_next);
 	 }
 	 
	iterator end()
	{
      return _head;
      //也可以强转一下
     // return iterator(_head);
     }
     
	//常属性迭代器
	const_iterator begin()const
	{
	    return _head->_next;
	}
	const_iterator end()const
	{
	    return _head;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

front和back

 T& front()
 {
     return _head->_next->_val;//返回值
 }
 const T& front()const
 {
     return _head->_next->_val;
 }
 T& back()
 {
     return _head->_prev->_val;
 }
 const T& back()const
 {
     return _head->_prev->_val;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

四、Modifiers:

其实带头双向循环链表的增删改查较于单链表,更加简单,我们画图分析还是很容易实现的.

(1) insert()

(图片为博主原创,不得随意截图使用)

特殊情况:这是尾插:
(图片为博主原创,不得随意截图使用)

代码示例

 // 在pos位置前插入值为val的节点
 iterator insert(iterator pos, const T& val)
 {
     //pos.node  而不是pos->node
     Node* newnode = new Node(val);
     Node* _prev_node = pos._node->_prev;      //pos位置结点的 原前置 结点
     Node* _cur_node = pos._node;             //pos位置的结点

     _prev_node->_next = newnode;
     newnode->_prev = _prev_node;

     _cur_node->_prev = newnode;
     newnode->_next = _cur_node;

     ++_size;//有效数据的个数+1.
     
     return newnode;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

(2) erase()

  // 删除pos位置的节点，返回该节点的下一个位置
  iterator erase(iterator pos)
  {
      
      Node* _prev_node = pos._node->_prev;             //pos位置结点的 原前置(prev) 结点
      Node* _next_node = pos._node->_next;            //pos位置结点的 原后置(next) 结点

      _next_node->_prev = _prev_node;
      _prev_node->_next = _next_node;

      delete pos._node;
      --_size;
      return _next_node;
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

(3) push_back() 和 push_front()

 //尾插
 //void push_back(const T& val)
 //{
 //    Node* newnode = new Node(val);
 //    Node* _tail_node = _head->_prev;      // 原尾结点
 //    _tail_node->_next = newnode;
 //    newnode->_prev = _tail_node;

 //    _head->_prev = newnode;
 //    newnode->_next = _head;
 //    
 //    ++_size;//有效数据的个数+1.
 //}
 
 //复用insert更加方便
 void push_back(const T& val){
     insert(end(),val);//在头结点前面插入,即为尾插
 }
 
 //头插
 void push_front(const T& val) { 
     insert(begin(), val);
 }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

(4) pop_back() 和 pop_front()

复用即可,不过多介绍了.

  //尾删
  void pop_back() { 
      erase(--end()); 
  }
  //头删
  void pop_front() { 
      erase(begin()); 
  }
1
2
3
4
5
6
7
8

(5) clear()

clear:清除list中的有效数据
遍历链表进行依次删除结点,并将size置为0.

  void clear()
  {
      iterator it = begin();
      while (it != end())
      {
          it = erase(it);
      }

      _size = 0;
  }
1
2
3
4
5
6
7
8
9
10

(6) swap()

交换两个链表的成员变量即可.

 void swap(list<T>& list)
 {
     swap(_head, list._head);
     swap(_size, list._size);
 }
1
2
3
4
5

结语

看完这篇文章,相信大家对list有了更加深层的理解,对于list的迭代器,它并不像前面的string和vector那种原生指针,而是封装成了类,使得链表的迭代器也可以执行++和--等操作,因为迭代器类重载了这些运算符.

今天就分享到这里了,如果觉得有帮助的话,可以给牛牛来一个一键三连吗?谢谢支持!