【C++杂货铺】探索list的底层实现

迈不过友情╰ 2023-10-15 13:15 43阅读 0赞

![在这里插入图片描述][194ab21664ec4c9093e235e1cd7c7261.gif_pic_center]

#### **文章目录** ####

*  一、list的介绍及使用
 *   *  1.1 list的介绍
     *  1.2 list的使用
     *   *  1.2.1 list的构造
         *  1.2.2 list iterator的使用
         *  1.2.3 list capacity（容量相关）
         *  1.2.4 list element access（元素访问）
         *  1.2.5 list modifiers（链表修改）
         *  1.2.6 list operation（对链表的一些操作）
 *  二、list的模拟实现
 *   *  2.1 list的节点
     *  2.2 list的成员变量
     *  2.3 list的迭代器
     *   *  2.3.1 普通迭代器
         *  2.3.2 const 迭代器
     *  2.4 list的成员函数
     *   *  2.4.1 构造函数
         *  2.4.2 拷贝构造函数
         *  2.4.3 赋值运算符重载
         *  2.4.4 push\_back
         *  2.4.5 迭代器相关
         *  2.4.6 insert
         *  2.4.7 erase
         *  2.4.8 push\_front
         *  2.4.9 pop\_back
         *  2.4.10 pop\_front
         *  2.4.11 size
         *  2.4.12 clear
         *  2.4.13 析构函数
 *  三、结语

## 一、list的介绍及使用 ##

### 1.1 list的介绍 ###

*  list 是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
 *  list 的底层是双向链表结构，双向链表中的每个元素存储在互不相关的独立节点中，在节点中通过指针指向的前一个元素和后一个元素。
 *  list 和 forward\_list 非常相似：最主要的不同在于 forward\_list 是单链表，只能朝前迭代，已让其更简单高效。
 *  与其它的序列式容器相比（arry、vector、deque），list 通常在任意位置进行插入，移除元素的执行效率更好。
 *  与其它序列式容器相比，list 和 forward\_list 最大的缺陷是不支持任意位置的随机访问，比如：要访问 list 的第 5 个元素，必须从已知的位置（比如头部或者尾部）迭代到该位置，在这段位置上迭代需要线性的时间开销；list 还需要一些额外的空间，已保存每个节点的相关联信息。

### 1.2 list的使用 ###

list 学习时一定要学会查看文档：[list的文档介绍][list]，list 在实际中非常重要，在实际中我们熟悉常用的接口就可以，下面列出了需要我们重点掌握的接口。

#### 1.2.1 list的构造 ####

<table> 
 <thead> 
  <tr> 
   <th><b>构造函数</b></th> 
   <th><b>接口说明</b></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>list()</td> 
   <td>list 的默认构造，构造空的 list</td> 
  </tr> 
  <tr> 
   <td>list(size_type n, const value_type&amp; val = value_type())</td> 
   <td>构造的 list 中包含 n 个值为 val 的元素</td> 
  </tr> 
  <tr> 
   <td>list(const list&amp; x)</td> 
   <td>拷贝构造函数</td> 
  </tr> 
  <tr> 
   <td>list(InputIterator first, InputIterator last)</td> 
   <td>用[first,last)区间中的元素构造 list</td> 
  </tr> 
 </tbody> 
</table>

**小Tips**：size\_type 表示一个无符号整数类型，value\_type 是 list 的第一个模板参数，也就是要存储的数据类型。使用迭代器区间的构造函数是函数模板，只要是满足 Input 类型的迭代器都可以使用该构造函数。

void TestList1()
    {
        
        list<int> l1;                         // 构造空的l1
        list<int> l2(4, 100);                 // l2中放4个值为100的元素
        list<int> l3(l2.begin(), l2.end());  // 用l2的[begin(), end()）左闭右开的区间构造l3
        list<int> l4(l3);                    // 用l3拷贝构造l4
    
        // 以数组为迭代器区间构造l5
        int array[] = {
         16,2,77,29 };
        list<int> l5(array, array + sizeof(array) / sizeof(int));
    
        // 列表格式初始化C++11
        list<int> l6{
         1,2,3,4,5 };
    
        // 用迭代器方式打印l5中的元素
        list<int>::iterator it = l5.begin();
        while (it != l5.end())
        {
        
            cout << *it << " ";
            ++it;
        }
        cout << endl;
    
        // C++11范围for的方式遍历
        for (auto& e : l5)
            cout << e << " ";
    
        cout << endl;
    }

#### 1.2.2 list iterator的使用 ####

此处，大家可暂时将迭代器理解成一个像指针一样的东西，该指针指向 list 中的某个节点。

<table> 
 <thead> 
  <tr> 
   <th><b>函数声明</b></th> 
   <th><b>接口说明</b></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>begin() + end()</td> 
   <td>返回第一个元素的迭代器 + 返回最后一个元素下一个位置的迭代器</td> 
  </tr> 
  <tr> 
   <td>rebegin() + ren()</td> 
   <td>返回第一个元素的 reverse_iterator，即 end 位置，返回最后一个一个元素下一个位置的 reverse_iterator，即 begin 位置</td> 
  </tr> 
 </tbody> 
</table>

**注意**：begin 与 end 为正向迭代器，对迭代器执行 ++ 操作，迭代器向后移动。rbegin 与 rend 为反向迭代器，对迭代器执行 ++ 操作，迭代器向前移动。由于 list 的底层物理空间并不连续，所以 list 的迭代器不再是原生指针，并且 list 的迭代器没有对 + 和 - 进行重载，只重载了 ++ 和 – ，因为空间不连续，重载 + 会比较复杂。即 `l.begin() + 5` 是不被允许的。

void PrintList(const list<int>& l)
    {
        
        // 注意这里调用的是list的 begin() const，返回list的const_iterator对象
        for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
        {
        
            cout << *it << " ";
            // *it = 10; 编译不通过
        }
    
        cout << endl;
    }
    
    void TestList2()
    {
        
        int array[] = {
         1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
        list<int> l(array, array + sizeof(array) / sizeof(array[0]));
        // 使用正向迭代器正向list中的元素
        // list<int>::iterator it = l.begin();   // C++98中语法
        auto it = l.begin();                     // C++11之后推荐写法
        while (it != l.end())
        {
        
            cout << *it << " ";
            ++it;
        }
        cout << endl;
    
        // 使用反向迭代器逆向打印list中的元素
        // list<int>::reverse_iterator rit = l.rbegin();
        auto rit = l.rbegin();
        while (rit != l.rend())
        {
        
            cout << *rit << " ";
            ++rit;
        }
        cout << endl;
    }

**注意**：遍历链表只能使用迭代器和范围 for。

#### 1.2.3 list capacity（容量相关） ####

<table> 
 <thead> 
  <tr> 
   <th><b>函数声明</b></th> 
   <th><b>接口说明</b></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>empty</td> 
   <td>检测 list 是否为空，是返回 true，否则返回 false</td> 
  </tr> 
  <tr> 
   <td>size</td> 
   <td>返回 list 中有效节点个数</td> 
  </tr> 
 </tbody> 
</table>

#### 1.2.4 list element access（元素访问） ####

<table> 
 <thead> 
  <tr> 
   <th><b>函数声明</b></th> 
   <th><b>接口说明</b></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>front</td> 
   <td>返回 list 的第一个节点中值的引用</td> 
  </tr> 
  <tr> 
   <td>back</td> 
   <td>返回 list 的最后一个节点中值的引用</td> 
  </tr> 
 </tbody> 
</table>

#### 1.2.5 list modifiers（链表修改） ####

<table> 
 <thead> 
  <tr> 
   <th><b>函数声明</b></th> 
   <th><b>接口说明</b></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>push_front</td> 
   <td>在 list 的第一个节点前插入值为 val 的节点</td> 
  </tr> 
  <tr> 
   <td>pop_front</td> 
   <td>删除 list 中第一个节点</td> 
  </tr> 
  <tr> 
   <td>push_back</td> 
   <td>在 list 尾部插入一个值为 val 的节点</td> 
  </tr> 
  <tr> 
   <td>pop_back</td> 
   <td>删除 list 中最后一个节点</td> 
  </tr> 
  <tr> 
   <td>insert</td> 
   <td>在 list 的 position 位置中插入一个值为 val 的节点</td> 
  </tr> 
  <tr> 
   <td>erase</td> 
   <td>删除 list position 位置的节点</td> 
  </tr> 
  <tr> 
   <td>swap</td> 
   <td>交换两个 list 的节点</td> 
  </tr> 
  <tr> 
   <td>clear</td> 
   <td>清空 list 中的有效元素</td> 
  </tr> 
 </tbody> 
</table>

**小Tips**：insert 插入元素并不会导致迭代器失效，例如：相较于 vector 中的 insert，list 中的 insert 并不会去扩容挪动数据，而 vector 中的 insert 可能会进行扩容挪动数据，最终导致迭代器失效。list 中的删除元素接口会导致迭代器失效，失效的只有指向被删除节点的迭代器，其他迭代器不会受到影响。

#### 1.2.6 list operation（对链表的一些操作） ####

<table> 
 <thead> 
  <tr> 
   <th><b>函数声明</b></th> 
   <th><b>接口说明</b></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>reverse</td> 
   <td>对链表进行逆置</td> 
  </tr> 
  <tr> 
   <td>sort</td> 
   <td>对链表中的元素进行排序（稳定排序）</td> 
  </tr> 
  <tr> 
   <td>merge</td> 
   <td>对两个有序的链表进行归并，得到一个有序的链表</td> 
  </tr> 
  <tr> 
   <td>unique</td> 
   <td>对链表中的元素去重</td> 
  </tr> 
  <tr> 
   <td>remove</td> 
   <td>删除具有特定值的节点</td> 
  </tr> 
  <tr> 
   <td>splice</td> 
   <td>将 A 链表中的节点转移到 B 链表</td> 
  </tr> 
 </tbody> 
</table>

**小Tips**：链表逆置可以使用 list 自身的接口，也可以使用算法库中的 reverse，二者没有什么区别。链表排序只能使用 list 自身的 sort() 接口（底层是利用归并排序），不能使用算法库的 sort，因为算法库中的 sort 底层是通过快排来实现的，而快排中会涉及到三数取中需要迭代器 - 迭代器，链表不能很好的支持。虽然链表提供了排序接口，但是用链表对数据排序意义不大，效率太低了，更希望用 vector 来对数据进行排序。

void TestSort()
    {
        
        srand(time(0));
        const int N = 5000000;
        vector<int> v;
        list<int> l;
    
        v.reserve(N);//提前开好空间
    
        for (int i = 0; i < N; i++)
        {
        
            auto e = rand();
            v.push_back(e);
            l.push_back(e);
        }
    
        //开始比较vector 和 list 的排序
        int begin1 = clock();
        sort(v.begin(), v.end());
        int end1 = clock();
    
        int begin2 = clock();
        l.sort();
        int end2 = clock();
    
        printf("vector sort:%d\n", end1 - begin1);
        printf("list sort:%d\n", end2 - begin2);
    }

![在这里插入图片描述][2ed88eb5760c4c6198d141ab45cabbd0.png_pic_center]

**扩展**：可以从功能角度对迭代器分为以下 3 类：

<table> 
 <thead> 
  <tr> 
   <th><b>迭代器类型</b></th> 
   <th><b>功能</b></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>单向（InputIterator）</td> 
   <td>支持 ++</td> 
  </tr> 
  <tr> 
   <td>双向（BidirectionalItreator）</td> 
   <td>支持 ++/- -</td> 
  </tr> 
  <tr> 
   <td>随机（RandomAccessIterator）</td> 
   <td>支持 ++ / - - / + / -</td> 
  </tr> 
 </tbody> 
</table>

其中 `forward_list`、`unordered_xxx` 都是单向迭代器；`list`、`map`、`set` 都是双向迭代器；`vector`、`string`、`deque` 都是随机迭代器。对迭代器的这种分类方式，是由容器的底层结构来决定的。

## 二、list的模拟实现 ##

### 2.1 list的节点 ###

template<class T>
    struct ListNode
    {
        
    	ListNode<T>* _next;
    	ListNode<T>* _prev;
    	T _val;
    
    	ListNode(const T& val = T())
    	{
        
    		_next = nullptr;
    		_prev = nullptr;
    		_val = val;
    	}
    };

### 2.2 list的成员变量 ###

class list
    {
        
    	typedef ListNode<T> Node;
    public:
    	//一些成员函数
    private:
    	Node* _head;
    }

**小Tips**：typedef 会受到访问限定符的限制，这里没写默认是 private，意味着 Node 这个类型只能在 list 这个类里面使用。链表本质上是一种数据结构，我们只需要维护好一个链表的头节点即可，所以 list 的成员变量就只有一个头节点的指针。

### 2.3 list的迭代器 ###

list 的迭代器不能再使用原生指针，如果 list 的迭代器使用原生指针的话，那对迭代器解引用得到的是一个节点，而我们希望对迭代器解引用可以得到节点里面存储的元素，并且 list 在底层的物理空间并不连续，如果使用原生指针作为 list 的迭代器，那对迭代器执行 ++ 操作，并不会让迭代器指向下一个节点。因此我们需要对 list 的迭代器进行封装，然后将一些运算符进行重载，以实现迭代器本该有的效果。

#### 2.3.1 普通迭代器 ####

template<class T>
    struct _list_iterator
    {
        
    	typedef ListNode<T> Node;
    
    	Node* _node;
    
    	_list_iterator(Node* val)
    	{
        
    		_node = val;
    	}
    
    	T& operator* ()
    	{
        
    		return _node->_val;
    	}
    
    	T* operator-> ()//迭代器通过->应该指向节点中的元素，因此返回的是一个T类型的地址
    	{
        
    		return &(_node->_val);
    	}
    
    	bool operator!= (const _list_iterator<T>& right)
    	{
        
    		return _node != right._node;
    	}
    
    	_list_iterator<T> operator++()
    	{
        
    		_node = _node->_next;
    
    		return *this;
    	}
    
    	_list_iterator<T> operator++(int)
    	{
        
    		_list_iterator<T> tmp(this->_node);
    
    		_node = _node->_next;
    
    		return tmp;
    	}
    };

**小Tips**：这里的类名不能直接叫 iterator，因为每种容器的迭代器底层实现可能都有所不同，即可能会为每一种容器都单独实现一个迭代器类，如果都直接使用 iterator，会导致命名冲突。其次，迭代器类不需要我们自己写析构函数、拷贝构造函数、赋值运算符重载函数，直接使用默认生成的就可以，言外之意就是这里使用浅拷贝即可，因为迭代器只是一种工具，它不需要对资源进行释放清理，资源释放清理工作是在容器类中实现的，浅拷贝的问题就出在会对同一块空间释放两次，而迭代器无需对空间进行释放，所以浅拷贝是满足我们需求的。

#### 2.3.2 const 迭代器 ####

上面我们实现了普通迭代器，那 const 迭代器该如何实现呢？直接在容器类里面写上一句 `typedef const _list_iterator<T> const_iterator` 可以嘛？答案是不可以，const 迭代器本质是限制迭代器指向的内容不能修改，而 const 迭代器自身可以修改，它可以指向其他节点。前面这种写法，const 限制的就是迭代器本身，会让迭代器无法实现 ++ 等操作。那如何控制迭代指向的内容不能修改呢？可以通过控制 operator\* 的返回值来实现。但是仅仅只有返回值类型不同，是无法构成函数重载的。那要怎样才能在一个类里面实现两个 operator\* 让他俩一个返回普通的 T&，一个返回 const T& 呢？一般人可能想着那就再单独写一个 \_list\_const\_iterator 的类，这样也行，就是会比较冗余，我们可以通过在普通迭代器的基础上，再传递一个模板参数，让编译器来帮们生成呀。除此之外， operator->也需要实现 const 版本，因此还需要第三个模板参数。

template<class T,class Ref, class Ptr>
    struct _list_iterator
    {
        
    	typedef ListNode<T> Node;
    	typedef _list_iterator<T, Ref, Ptr> self;
    
    	Node* _node;
    
    	_list_iterator(Node* val)
    	{
        
    		_node = val;
    	}
    
    	Ref operator* ()
    	{
        
    		return _node->_val;
    	}
    
    	Ptr operator-> ()
    	{
        
    		return &(_node->_val);
    	}
    
    	bool operator!= (const self& right) const
    	{
        
    		return _node != right._node;
    	}
    	bool operator== (const self& right) const
    	{
        
    		return _node == right._node;
    	}
    
    
    	self operator++()
    	{
        
    		_node = _node->_next;
    
    		return *this;
    	}
    
    	self operator++(int)
    	{
        
    		self tmp(this->_node);
    
    		_node = _node->_next;
    
    		return tmp;
    	}
    
    	self operator--()
    	{
        
    		_node = _node->_prev;
    
    		return *this;
    	}
    
    	self operator--(int)
    	{
        
    		self tmp(*this);
    		_node = _node->_prev;
    
    		return tmp;
    	}
    };

//operator->的使用场景
    struct A
    {
        
    	A(int a = 0, int b = 0)
    	{
        
    		_a = a;
    		_b = b;
    	}
    
    	int _a;
    	int _b;
    };
    
    void Textlist3()
    {
        
    	wcy::list<A> l;
    	l.push_back(A(1, 2));
    	l.push_back(A(3, 4));
    	l.push_back(A(5, 6));
    	l.push_back(A(7, 8));
    
    	wcy::list<A>::iterator it = l.begin();
    	while (it != l.end())
    	{
        
    		cout << it->_a << ',' << it->_b << " ";
    		cout << endl;
    		it++;
    	}
    }

**小Tips**：上面代码中的 `it->_a` 会去调用 `operator->`，返回一个 A 类型的指针，所以这里应该是两个 `->`，即 `it->->_a` ，但是编译器进行了优化，只需要一个 `->` 即可。

### 2.4 list的成员函数 ###

#### 2.4.1 构造函数 ####

list()
    {
        
    	_head = new Node;
    	_head->_prev = _head;
    	_head->_next = _next;
    }

**小Tips**：list 本质上是一个带头双向循环链表。

#### 2.4.2 拷贝构造函数 ####

list(const list& ll)
    //list(const list<T>& ll)
    {
        
    	_head = new Node;
    	_head->_prev = _head;
    	_head->_next = _head;
    
    	for (auto& e : ll)
    	{
        
    		push_back(e);
    	}
    }

#### 2.4.3 赋值运算符重载 ####

void swap(list<T> l2)
    {
        
    	std::swap(_head, l2._head);
    }
    
    list& operator=(const list ll)
    //list<T>& operator=(const list<T> ll)
    {
        
    	//现代写法
    	swap(ll);
    
    	return *this;
    }

**小Tips**：构造函数和赋值运算符重载函数的形参和返回值类型可以只写类名 `list`，无需写完整的类型 `list<T>`，但是不推荐这样写，容易造成混淆，其次现代写法和常规写法在效率上没有任何区别，只是将本来需要我们做的事情交给了编译器去做。

#### 2.4.4 push\_back ####

void push_back(const T& val)
    {
        
    	//先找尾
    	Node* tail = _head;
    	while (tail->_next != _head)
    	{
        
    		tail = tail->_next;
    	}
    
    	//插入元素
    	Node* newnode = new Node(val);
    	tail->_next = newnode;
    	newnode->_prev = tail;
    
    	newnode->_next = _head;
    	_head->_prev = newnode;
    }

#### 2.4.5 迭代器相关 ####

iterator begin()
    {
        
    	return _head->_next;//单参数的构造函数支持隐式类型转换
    }
    
    iterator end()
    {
        
    	return _head;
    }
    
    const_iterator begin() const
    {
        
    	return _head->_next;//单参数的构造函数支持隐式类型转换
    }
    
    const_iterator end() const
    {
        
    	return _head;
    }

#### 2.4.6 insert ####

iterator insert(iterator pos, const T& val)
    {
        
    	//找到 pos 位置的前一个位置
    	Node* cur = pos._node;
    	Node* prev = cur->_prev;
    
    	//插入元素
    	Node* newnode = new Node(val);
    	prev->_next = newnode;
    	newnode->_prev = prev;
    
    	newnode->_next = cur;
    	cur->_prev = newnode;
    
    	return newnode;
    }

#### 2.4.7 erase ####

iterator erase(iterator pos)
    {
        
    	assert(pos != end());
    	Node* cur = pos._node;//保存当前节点
    	Node* prev = cur->_prev;//保存前一个节点
    	Node* next = cur->_next;//保存后一个节点
    	
    	prev->_next = next;
    	next->_prev = prev;
    
    	delete cur;
    	cur = nullptr;
    
    	return next;
    }

#### 2.4.8 push\_front ####

void push_front(const T& val)
    {
        
    	insert(begin(), val);
    }

#### 2.4.9 pop\_back ####

void pop_back()
    {
        
    	erase(--end());
    }

#### 2.4.10 pop\_front ####

void pop_front()
    {
        
    	erase(begin());
    }

#### 2.4.11 size ####

size_t size()
    {
        
    	size_t sz = 0;
    	iterator it = begin();
    
    	while (it != end())
    	{
        
    		it++;
    		sz++;
    	}
    
    	return sz;
    }

#### 2.4.12 clear ####

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

#### 2.4.13 析构函数 ####

~list()
    {
        
    	clear();
    
    	delete _head;
    	_head = nullptr;
    }

**小Tips**：clear 和 析构函数的主要区别在于是否释放头节点。

## 三、结语 ##

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，[春人的主页][Link 1]还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是春人前进的动力！

![在这里插入图片描述][edc78985d03043828f98dcd5a8d2983e.gif_pic_center]

[194ab21664ec4c9093e235e1cd7c7261.gif_pic_center]: https://img-blog.csdnimg.cn/194ab21664ec4c9093e235e1cd7c7261.gif#pic_center
[list]: https://legacy.cplusplus.com/reference/list/list/
[2ed88eb5760c4c6198d141ab45cabbd0.png_pic_center]: https://img-blog.csdnimg.cn/2ed88eb5760c4c6198d141ab45cabbd0.png#pic_center
[Link 1]: https://blog.csdn.net/weixin_63115236?spm=1000.2115.3001.5343
[edc78985d03043828f98dcd5a8d2983e.gif_pic_center]: https://img-blog.csdnimg.cn/edc78985d03043828f98dcd5a8d2983e.gif#pic_center