C++：List的使用和模拟实现

✨✨✨学习的道路很枯燥，希望我们能并肩走下来!

文章目录

前言

一 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的迭代器失效

1.2.7 List中sort的效率测试

二、list的模拟实现

2.1 正向迭代器的实现

2.1.1 正向迭代器的封装

2.1.2 迭代器的使用

2.2 list相关的成员函数

2.2.1 构造函数

2.2.1.1 默认构造函数

2.2.1.2 有参构造函数

2.2.1.3 迭代器区间构造函数

2.2.1.4 拷贝构造

1.传统

2.现代

2.2.2 析构函数和clear

2.2.2.1 析构函数

2.2.2.2 clear()

2.2.3 赋值重载

2.2.4.1 empty、size

2.2.4.2 insert

2.2.4.3 erase

2.2.4.4 尾插尾删头插头删

2.3 反向迭代器的实现

三 list模拟实现的全部代码

总

前言

本篇详细介绍了list的使用和模拟实现，让使用者了解list，而不是仅仅停留在表面，更好的模拟，为了更好的使用. 文章可能出现错误，如有请在评论区指正，让我们一起交流，共同进步！

一 list的介绍及使用

1.1 list的介绍

list文本介绍

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

2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。

4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。

5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list 的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

1.2 list的使用

list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口。

1.2.1 list的构造

构造函数（ (constructor)）	接口说明
list (size_type n, const value_type& val = value_type())	构造的list中包含n个值为val的元素
list()	构造空的list
list (const list& x)	拷贝构造函数
list (InputIterator first, InputIterator last)	用[first, last)区间中的元素构造list

1.2.2 list iterator的使用

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

函数声明	接口说明
begin + end	返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin + rend	返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的 reverse_iterator,即begin位置

【注意】

1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动

2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

1.2.3 list capacity

函数声明	接口说明
empty	检测list是否为空，是返回true，否则返回false
size	返回list中有效节点的个数

1.2.4 list element access

函数声明	接口说明
front	返回list的第一个节点中值的引用
back	返回list的最后一个节点中值的引用

1.2.5 list modifiers

函数声明	接口说明
push_front	在list首元素前插入值为val的元素
pop_front	删除list中第一个元素
push_back	在list尾部插入值为val的元素
pop_back	删除list中最后一个元素
insert	在list position 位置中插入值为val的元素
erase	删除list position位置的元素
swap	交换两个list中的元素
clear	清空list中的有效元素

list中还有一些操作，需要用到时大家可参阅list的文档说明。

1.2.6 list的迭代器失效

前面说过，此处大家可将迭代器暂时理解成类似于指针

迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。

因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

void TestListIterator1()
 {
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> l(array, array+sizeof(array)/sizeof(array[0]));
 
    auto it = l.begin();
    while (it != l.end())
    {
        // erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给
其赋值
        l.erase(it);  
        ++it;
    }
 }

 // 改正
void TestListIterator()
 {
     int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
     list<int> l(array, array+sizeof(array)/sizeof(array[0]));
     auto it = l.begin();
     while (it != l.end())
    {
         l.erase(it++);    
    }
 }

1.2.7 List中sort的效率测试

我们用一段代码来测试一下list中sort的性能

#include<iostream>
#include<algorithm>
#include<vector>
#include<list>
using namespace std;
void test_op()
{
	srand((unsigned int)time(NULL));
	const int N = 1000000;
	vector<int> v;
	v.reserve(N);
	list<int> lt1;
	list<int> lt2;
	for (int i = 0; i < N; ++i)
	{
		int e = rand();
		lt1.push_back(e);
		lt2.push_back(e);
	}
	// 拷贝到vector排序，排完以后再拷贝回来
	int begin1 = clock();
	for (auto e : lt1)
	{
		v.push_back(e);
	}
	sort(v.begin(), v.end());
	size_t i = 0;
	for (auto& e : lt1)
	{
		e = v[i++];
	}
	int end1 = clock();
	//list调用自己的sort
	int begin2 = clock();
	lt2.sort();
	int end2 = clock();
	printf("vector sort:%d\n", end1 - begin1);
	printf("list sort:%d\n", end2 - begin2);
}

会发现哪怕我先拷贝到vector排完再拷贝回去效率都比list的sort效率高，所以list的sort实际中意义不是很大！！

二、list的模拟实现

2.1 正向迭代器的实现

2.1.1 正向迭代器的封装

我们在学习vector的时候，发现vector的迭代器就是一个原生指针T*，这得益于vector的空间的连续性

那我们还能像vector一样用原生指针去修饰迭代器吗？

不能，链表空间上是不连续的，那我们对一个节点指针进行加减，就很难说能不能找到下一个节点，更多的是找不到的情况

我们在数据结构中访问下一个节点，往往是利用当前节点存的下一节点的地址来进行访问的

所以我们可以将迭代器单独封装成一个类去管理节点

template<class T, class Ref, class Ptr> //Ref == T& Ptr == T*
struct ListIterator //这里使用struct是因为我们要多次访问成员，也可使用class+public
{
    typedef ListNode<T>* PNode;
    typedef ListIterator<T, Ref, Ptr> Self;
    ListIterator(PNode pNode = nullptr) 
        :_pNode(pNode)
    {}
    ListIterator(const Self& l) 
        :_pNode(l._pNode)
    {}
    T& operator*() //解引用
    {
        return _pNode->_val;
    }
    T* operator->() 
    {
        return &_pNode->_val;
    }
    Self& operator++() //前置++
    {
        _pNode = _pNode->_pNext;
        return *this;
    }
    Self operator++(int) //后置++
    {
        Self temp(*this);
        _pNode = _pNode->_pNext;
        return temp;
    }
    Self& operator--() //前置--
    {
        _pNode = _pNode->_pPre;
        return *this;
    }
    Self& operator--(int) //后置--
    {
        Self temp(*this);
        _pNode = _pNode->_pPre;
        return temp;
    }
    bool operator!=(const Self& l) //不相等判断
    {
        return _pNode != l._pNode;
    }
    bool operator==(const Self& l) //相等判断
    {
        return !(*this != l);
    }
    PNode _pNode;
};

T* operator->() 大家可能有疑惑

当我们的节点里存的是内置类型或者STL容器是，库里面的<<重载了这些来读取数据

但如果是我们自己写的类型（如class CH），<<并不能读取该类型的数据

因此我们要取来节点自定义类的指针，来访问该类的内部的数据（因为最底层都是内置类型