【探索C++中的链表】手动实现list容器

深碍√TFBOYSˉ_ 2024-04-26 11:01 64阅读 0赞

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

> ?write in front?  
> ?所属专栏： [C++学习][C]  
> ?️博客主页：[睿睿的博客主页][Link 1]  
> ?️代码仓库：?[VS2022\_C语言仓库][VS2022_C]  
> ?您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！  
> **关注我，关注我，关注我**，你们将会看到更多的优质内容！！

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

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

*  前言
 *  一.list的算法：
 *   *  1.reverse：
     *  2.sort:
     *  3.remove：
     *  3.splice:
     *  4.unique：
     *  5.merge:
 *  二.list的模拟实现：
 *   *  1.迭代器的封装：
     *  2.模板的进阶使用：
     *  3.几个易错点
 *  总结

## 前言 ##

尊敬的读者们，今天我们将一起深入探讨C++中list（链表）的模拟实现。list是C++标准库中的一种双向链表容器，它允许我们在任意位置高效地插入和删除元素。为了更好地理解list的内部工作原理，我们将手动实现一个简化版的list，并介绍它的基本操作。

这里是list的功能库：[list功能库][list]

## 一.list的算法： ##

![在这里插入图片描述][08436c0e9fb04f3bbe3b002f93684d40.png]

### 1.reverse： ###

![在这里插入图片描述][087872b412e94db0b1b371967ec77e2b.png]

简单的说，list里面的逆置其实是**没有必要的**，因为算法库里面也提供了逆置：

list<int> lt;
    	lt.push_back(1);
    	lt.push_back(2);
    	lt.push_back(3);
    	lt.push_back(4);
    
    	lt.push_front(10);
    	lt.push_front(20);
    	//list容器里面提供的逆置
    	lt.reverse();
    	//算法库里面提供的逆置
    	reverse(lt.begin(),lt.end());

### 2.sort: ###

![在这里插入图片描述][4c6698482ac141a0a1063e48d6e247e3.png]

那么，sort函数也是白写的吗？这就涉及到迭代器的匹配问题了。况且我们也知道，库里面的sort排序是快排，不能排链表。list容器里面的排序使用的是归并，空间复杂度远高于高于库里面的。我们可以做以下实验：

void op()
    {
        
    	list<int> a1;
    	//list<int> a2;
    	srand((unsigned int)time(0));
    	const int N = 10000000;
    
    	for (int i = 0; i < N; i++)
    	{
        
    		a1.push_back(rand());
    	}
    	list<int> a2(a1);
    
    	//用list容器里面的sort直接排序：
    	cout << "用list容器里面的sort直接排序时间：";
    	int begin = clock();
    	a1.sort();
    	int end = clock();
    	cout << end-begin << endl;
    
    	//把list拷贝到vector,在使用算法库里面的sort排序时间：
    	
    	
    	cout << "把list拷贝到vector,在使用算法库里面的sort排序时间：";
    	begin = clock();
    	vector<int> a3(a2.begin(), a2.end());
    	sort(a3.begin(), a3.end());
    	int i = 0;
    	for (auto &e : a2)
    	{
        
    		e = a3[i++];
    	}
    	end = clock();
    	cout << end - begin;
    	
    
    }

![在这里插入图片描述][48cf1b20129249bbac1183a7c974cce3.png]  
  由此可见，对于链表，如果我们要对**少量数据**排序，那么list容器里面的sort函数是足够的，但是对于大量数据，为了降低时间复杂度，我们使用**先将其拷贝到vector容器，用算法库快排排序，在将结果拷贝回去的方法来排序**！

### 3.remove： ###

![在这里插入图片描述][8f971625bac34fe8af7de78e585dd9c5.png]

这个函数和erase()函数很像，但是erase是根据位置删除数据，remove是根据val(删除数据的值)删除数据.

### 3.splice: ###

![在这里插入图片描述][ec4c39d9afb54cbeb43d594d384a1efa.png]  
  这个函数就和我们之前做的oj题很像，将一个链表的一些元素转移到另一个链表的某个位置。

std::list<int> mylist1, mylist2;
      std::list<int>::iterator it;
    
      // set some initial values:
      for (int i=1; i<=4; ++i)
         mylist1.push_back(i);      // mylist1: 1 2 3 4
    
      for (int i=1; i<=3; ++i)
         mylist2.push_back(i*10);   // mylist2: 10 20 30
    
      it = mylist1.begin();
      ++it;                         // points to 2
    
      mylist1.splice (it, mylist2); // mylist1: 1 10 20 30 2 3 4
                                    // mylist2 (empty)
                                    // "it" still points to 2 (the 5th element)
                                              
      mylist2.splice (mylist2.begin(),mylist1, it);
                                    // mylist1: 1 10 20 30 3 4
                                    // mylist2: 2
                                    // "it" is now invalid.
      it = mylist1.begin();
      std::advance(it,3);           // "it" points now to 30
    
      mylist1.splice ( mylist1.begin(), mylist1, it, mylist1.end());
                                    // mylist1: 30 3 4 1 10 20
    
      std::cout << "mylist1 contains:";
      for (it=mylist1.begin(); it!=mylist1.end(); ++it)
        std::cout << ' ' << *it;
      std::cout << '\n';
    
      std::cout << "mylist2 contains:";
      for (it=mylist2.begin(); it!=mylist2.end(); ++it)
        std::cout << ' ' << *it;
      std::cout << '\n';

当然，在这里我们也一定要考虑迭代器失效的问题！

### 4.unique： ###

![在这里插入图片描述][cbb5cc8bb28d461c804aaf5940cc2a0b.png]

该函数就是移除链表里面相同元素的多余元素，**但是但是！我们要先排序了之后才能使用这个函数。**

double mydoubles[]={
         12.15,  2.72, 73.0,  12.77,  3.14,
                           12.77, 73.35, 72.25, 15.3,  72.25 };
      std::list<double> mylist (mydoubles,mydoubles+10);
      
      mylist.sort();             //  2.72,  3.14, 12.15, 12.77, 12.77,
                                 // 15.3,  72.25, 72.25, 73.0,  73.35
    
      mylist.unique();           //  2.72,  3.14, 12.15, 12.77
                                 // 15.3,  72.25, 73.0,  73.35

### 5.merge: ###

![在这里插入图片描述][6d69f86a2eb64498b721de525f44fd08.png]  
  将有两个顺序的链表合并起来并排序。其实就是归并排序。

## 二.list的模拟实现： ##

### 1.迭代器的封装： ###

在前面的博客[stl神奇的指针“迭代器”][stl]中我们提到，迭代器是连接算法和容器的桥梁，通过迭代器我们就可以通过算法来操作容器。  
  在前面的vector容器的模拟实现中，我们使用了原生指针来作为其迭代器，因为指针的`++`，`--`，`*`都正好符合这些操作。但是我们的list是双向链表，物理可见不连续，如果我们用其指针来当作其迭代器，对于`++`，`--`，`*`这些操作符都是不能直接使用的。  
  所以为了和其他容器的迭代器相似，要能正确使用这些操作符，我们就要通过封装来实现他的迭代器。

我们直接来看看其迭代器的模拟实现：

template<class T, class Ref, class Ptr>
    	struct __list_iterator
    	{
        
    		typedef list_node<T> Node;
    		typedef __list_iterator<T, Ref, Ptr> self;
    		Node* _node;
    
    		__list_iterator(Node* node)
    			:_node(node)
    		{
        }
    
    		Ref operator*()
    		{
        
    			return _node->_val;
    		}
    
    		Ptr operator->()
    		{
        
    			return &_node->_val;
    		}
    
    		self& operator++()
    		{
        
    			_node = _node->_next;
    			return *this;
    		}
    
    		self operator++(int)
    		{
        
    			self tmp(*this);
    
    			_node = _node->_next;
    
    			return tmp;
    		}
    
    		self& operator--()
    		{
        
    			_node = _node->_prev;
    			return *this;
    		}
    
    		self operator--(int)
    		{
        
    			self tmp(*this);
    
    			_node = _node->_prev;
    
    			return tmp;
    		}
    
    		bool operator!=(const self& it) const
    		{
        
    			return _node != it._node;
    		}
    
    		bool operator==(const self& it) const
    		{
        
    			return _node == it._node;
    		}
    	};

封装完这个类之后，我们在list类里面对其重命名一下就可以了：

typedef __list_iterator<T, T&, T*> iterator;
    typedef __list_iterator<T, const T&, const T*> const_iterator;

### 2.模板的进阶使用： ###

在上面的代码中我们可以看出，我们又套用了模板。这是因为对于const\_iterator的时候，如果我们不用模板，我们的`typedef`会出现问题：

typedef const __list_iterator<T> const_iteraator;

如果我们直接加`const`在前面，那么说明这个`const_iterator`不能改变，那么什么`++`等操作就不能完成了。这个与之前`vector`的原生指针不同，因为`const T*`是指T指向的内容不能边，但是还是可以`++`的。

所以在这里为了解决这个问题，我们有两种方法：

第一种就是重新复制一遍，改一下返回值，但是很冗余。

第二种就是通过模板参数传参来实现。最后在重命名一下：

typedef __list_iterator<T, T&, T*> iterator;
    typedef __list_iterator<T, const T&, const T*> const_iterator;

### 3.几个易错点 ###

在我测试代码的时候遇到了一些问题：

问题一：

list<int>::const_iterator it = lt.begin();

在之前的学习里面用const修饰的变量接收非const变量，是权限的缩小，是可以实现的：

int a=10;
    const int b=a;

**但是为什么这里报错了呢？**  
![在这里插入图片描述][0e477a3725da444a818139a21a108858.png]  
  其实这里只是我自己个人的一个误区，以为加了const只是权限不同，但是实际上这个代码左右两边的类型都不一样！！模板类根据参数的不同生成不同的对象，这个时候两个自定义类型就已经不相同了，就不能用他赋值了。

问题二：  
  为什么我们重载`!=`，`==`的时候参数一定要const？

因为如果不加const，我们的（it!=lt.end())就会错误。因为我们end()实现的时候，是这样实现的：

iterator end()
    		{
        
    			return _head;
    		}

这里返回的是一个**临时拷贝**，如果我们不用`const`修饰，**引用**肯定就会出错。当然，这里也涉及了**单参数的构造函数支持隐式类型转换**。

## 总结 ##

这就是list容器的学习，具体代码在这里[list模拟实现][list 1]，欢迎大家指出我的问题！

更新不易，辛苦各位小 伙伴们动动小手，?三连走一走?? ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

> **专栏订阅：**  
> [每日一题][Link 2]  
> [C语言学习][C 1]  
> [算法][Link 3]  
> [智力题][Link 4]  
> [初阶数据结构][Link 5]  
> [Linux学习][Linux]  
> [C++学习][C]  
> 更新不易，辛苦各位小伙伴们动动小手，?三连走一走?? ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

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

[6ac7346dc5944908b5dd227e55fab217.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/6b3400e24a64409abef21ac02e1c99ff.gif
[C]: https://blog.csdn.net/qq_74310471/category_12289978.html
[Link 1]: https://blog.csdn.net/qq_74310471?spm=1000.2115.3001.5343
[VS2022_C]: https://gitee.com/zhangxuruihhhh/c-language-learning
[85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/bc1d97f5631e442fb652b21f9086b208.gif
[list]: https://legacy.cplusplus.com/reference/list/list/?kw=list
[08436c0e9fb04f3bbe3b002f93684d40.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/a487bf8f5c464eab9be0a3a105f580a8.png
[087872b412e94db0b1b371967ec77e2b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/bc3f366c32df44d7af1ce4bb7cbe2b78.png
[4c6698482ac141a0a1063e48d6e247e3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/5c6050c15c1a4995b54b6ea2f5e2dcf5.png
[48cf1b20129249bbac1183a7c974cce3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/93fc148bd95d46ff846cc3b9f9e16532.png
[8f971625bac34fe8af7de78e585dd9c5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/b0e4d9f98b57488180e8eacc39bb7be7.png
[ec4c39d9afb54cbeb43d594d384a1efa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/455acfa2fee84c4dac6e359437cf7aee.png
[cbb5cc8bb28d461c804aaf5940cc2a0b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/d7cff8cd1ced42aeac073c01a3f30c2f.png
[6d69f86a2eb64498b721de525f44fd08.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/e25a952062fe4fb784e58839c9c0f3a4.png
[stl]: https://blog.csdn.net/qq_74310471/article/details/131988762?spm=1001.2014.3001.5501
[0e477a3725da444a818139a21a108858.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/291fe4818a0d46608bfd54416fd267fc.png
[list 1]: https://gitee.com/zhangxuruihhhh/data-structure/tree/master/list%E6%A8%A1%E6%8B%9F%E5%AE%9E%E7%8E%B0/list%E6%A8%A1%E6%8B%9F%E5%AE%9E%E7%8E%B0
[Link 2]: https://blog.csdn.net/qq_74310471/category_12166401.html?spm=1001.2014.3001.5482
[C 1]: https://blog.csdn.net/qq_74310471/category_12157207.html?spm=1001.2014.3001.5482
[Link 3]: https://blog.csdn.net/qq_74310471/category_12144452.html?spm=1001.2014.3001.5482
[Link 4]: https://blog.csdn.net/qq_74310471/category_12166402.html
[Link 5]: https://blog.csdn.net/qq_74310471/category_12216969.html?spm=1001.2014.3001.5482
[Linux]: https://blog.csdn.net/qq_74310471/category_12291120.html
[55270e2552774a17a711aa978da84193.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/89c16c4f2a304874bb417064913dadd3.gif