【C++初阶】List的模拟实现

1 List 的介绍

List 是带头双向循环链表，不支持 [] 的随机访问和没有扩容相关的函数。
看一下下面的模拟实现就懂了吧，懒

List 迭代器的失效

在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
所以在进行删除操作后，要将迭代器往后迭代。

2. List 的模拟实现

未出现的函数都会在后面出现

2.1 List 的结点类

template<class T>
struct ListNode
{
	ListNode<T>* _next;
	ListNode<T>* _prev;
	T _data;

	ListNode(const T& x = T())
		//缺省值不能直接给0，因为不知道T的类型，可能是string

		:_next(nullptr)
		, _prev(nullptr)
		, _data(x)
	{}
};

在构造函数中使用默认参数 val = T() 是为了提供一种灵活的方式来初始化节点：

• 默认构造函数：==T() 表示调用 T 类型的默认构造函数。如果没有提供参数 val，那么 _val 将被默认构造一个 T 类型的对象来初始化。==例如，如果 T 是 int 类型，T() 会生成一个值为 0 的整数；如果 T 是一个自定义的类，那么 T() 会调用这个类的默认构造函数。
• 提供参数：如果提供了参数 val，那么节点的 _val 将被初始化为 val 的值。例如，ListNode<int> node(42); 将创建一个存储值 42 的节点。

2.2 List 的迭代器类

2.2.1 再论迭代器

迭代器就是访问数据结构的工具，一个称呼，就像是数组的下标。

大致分为两类，一类是原生指针，另一类是封装

• 原生指针：在前面的 string 类和 vector 类，我们在实现的时候是直接采用原生指针封装的，所以才可以直接的进行解引用，自增自减等指针的操作。这么使用的原因是：这两个类的内存空间是顺序的。
• 封装：对于 list 这种内存空间不连续的，不能使用原生指针作为它的迭代器，便无法直接使用指针的操作。例如自增，我们不能直接使用 ++，而是 _node = _node->next

迭代器存在的意义：让用户不用关心底层实现，而是直接根据平常习惯对数据进行访问操作。

List 的迭代器类

 //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;
 };

2.2.2 模板参数

template<class T, class Ref, class Ptr>

在 list 的模拟实现中，我们会 typedef 两个迭代器类型，普通迭代器和 const 迭代器

typedef ListNode<T>* PNode;
typedef ListIterator<T, Ref, Ptr> Self;

在 List 类中

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

迭代器模板参数列表当中的 Ref 和 Ptr 分别代表的是引用类型和指针类型
可以允许我们使用哪种普通迭代器，编译器会相应地实现对应的迭代器。

2.2.3 迭代器的构造函数

 ListIterator(PNode pNode = nullptr)//默认构造函数
     :_pNode(pNode) {}
 ListIterator(const Self& l)//拷贝构造函数
     :_pNode(l._pNode){}

2.2.4 运算符的重载

operator*
使用解引用操作符，是想获取该位置的数据，所以是 _pNode->val，但因为解引用后可能需要修改，所以是引用返回。返回当前结点指针所指结点的数据

//解引用操作符
 Ref operator*()
 {
     return _pNode->val;
 }

operator->
使用场景：list 容器存储的结点不是内置类型，而是自定义类型。我们就要用 -> 去访问该类的成员。返回结点当中所存储数据的地址
回顾： -> : ptr->member 等价于 (*ptr).member

 Ptr operator->()
 {
    return &(operator*());
	//return &(_node->_val);
 }

当代码使用这个 operator->，会自动再加入一个原生的 ->

语法中的特殊处理就是本质有些语法逻辑不自洽，所以特殊处理

!= 、==

bool operator!=(const Self& l)
{
	return _pNode != l._pNode;
}

bool operator==(const Self& l)
{
	return _pNode == l._pNode;
}

自增、自减

//前置++ ++i
Self& operator++()
{
	_node = _node->next;// 将迭代器前进到下一个节点
	return *this;// 返回迭代器自身的引用
}

//后置++ i++
Self operator++(int)
{
	self tmp(*this);// 创建当前迭代器对象的副本
	_pNode = _pNode->_pNext;
	return tmp;// 返回操作之前的迭代器状态的副本
}
//后置++返回的是临时变量
// 出了作用域就销毁，所以传值返回

//前置-- --i
Self& operator--()
{
	_pNode = _pNode->_pPre;
	return *this;
}

//后置-- i--
Self operator--(int)
{
	Self tmp(*this);
	_pNode = _pNode->_pPre;
}

2.3 List 类

总览

 //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 Access
     T& front();
     const T& front()const;
     T& back();
     const T& back()const;
     
     // List Modify
     void push_back(const T& val) { insert(end(), val); }
     void pop_back() { erase(--end()); }
     void push_front(const T& val) { insert(begin(), val); }
     void pop_front() { erase(begin()); }
     // 在pos位置前插入值为val的节点
     iterator insert(iterator pos, const T& val);
     // 删除pos位置的节点，返回该节点的下一个位置
     iterator erase(iterator pos);
     void clear();
     void swap(list<T>& l);
 private:
     void CreateHead();
     PNode _pHead;
 };

2.3.1 定义结点

//list类
 template<class T>
 class list
 {
     typedef ListNode<T> Node;
     typedef Node* PNode;
 //...
 private:
     void CreateHead();
     PNode _pHead;
 };

结点的创建
list是一个带头双向循环链表，在构造一个list对象时，直接申请一个头结点，并让其前驱指针和后继指针都指向自己即可。

void CreateHead() {
	_pHead = new Node;
	_pHead->_pNext = _pHead;
	_pHead->_pPre = _pHead;
}

2.3.2 构造函数

// List的构造
list()
{
	CreateHead();//在上面
}
list(int n, const T& value = T())
{
	CreateHead();
	for (int i = 0; i < n; i++)
	{
		push_back(value);
	}
}
	//const T&：
	//这里 T& 表示引用类型，const T& 表示常量引用类型。常量引用意味着在函数内部无法修改传递进来的参数 value。
	//使用常量引用有两个主要优点：
	//避免复制：当传递大对象时，使用引用避免了对象的复制，从而提高了性能。
	//保护参数：使用 const 可以确保函数不会修改传递进来的参数，增强代码的安全性和可读性。

	//value = T()：
	//这是一个默认参数，表示如果调用函数时不传递 value 参数，那么 value 会被初始化为 T()。T() 是类型 T 的默认构造函数调用，创建一个默认初始化的 T 对象。

template <class Iterator>
list(Iterator first, Iterator last)//迭代器构造
{
	CreateHead();
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

list(const list<T>& l)//拷贝构造
{
	CreateHead();
	
	//使用l中的元素，用迭代器构造出临时的temp，再与当前的对象交换
	list<T> temp(l.begin(), l.end());
	swap(temp);
}

list<T>& operator=(const list<T> l)
{
	swap(l);//在后面
	return *this;
}

2.3.3 析构函数

对对象进行析构时，首先调用clear函数清理容器当中的数据，然后将头结点释放，最后将头指针置空即可。

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

2.3.4 迭代器相关

为什么这里是 Node* 却可以用 iterator 来接收呢？
因为单参数的函数构造支持隐式类型转换。

-> 操作符：用于指针解引用并访问对象成员。ptr->member 等价于 (*ptr).member。

对于双向带头循环链表，其第一个有效数据的迭代器就是使用头结点后一个结点的地址构造出来的迭代器，而其最后一个有效数据的下一个位置的迭代器就是使用头结点的地址构造出来的迭代器。

iterator begin()
{
	//return iterator(_pHead->_pNext);
	return _pHead->_pNext;//这个就是Node*
}

iterator end()
{
	return _pHead;
}

---

const 的回顾

1. 成员函数参数中的 const
   作用对象：保护传入函数的参数不被修改。
   应用场景：用于任何希望传递但不希望修改的参数。

2. 成员函数末尾的 const
   作用对象：保护成员函数在调用时不会修改类的成员变量。
   应用场景：用于任何希望在 const 对象上调用的成员函数，或者任何不需要修改成员变量的成员函数。

---

2.3.5 容量相关

size ：获取容器中元素的个数

size_t size()const
{
	PNode cur = _pHead->_pNext;
	size_t count = 0;
	while (cur != _pHead)
	{
		count++;
		cur = cur->_pNext;
	}
	return count;
}

empty: 判断容器是否为空

bool empty()const
{
	return _pHead->_pNext == _pHead;
}

resize

1. 当所给值大于当前的size时，将size扩大到该值，扩大的数据为第二个所给值，若未给出，则默认为容器所存储类型的默认构造函数所构造出来的值；
2. 当所给值小于当前的size时，将size缩小到该值。

void resize(size_t newsize, const T& data = T())
{
	size_t oldsize = size();
	if (newsize <= oldsize)
	{
		while (newsize < oldsize)
		{
			pop_back();
			oldsize--;
		}
	}
	else
	{
		while (oldsize < newsize)
		{
			push_back(data);
			oldsize++;
		}
	}
}

2.3.6 访问容器

front() 和 back()
返回第一个有效数据和最后一个有效数据的引用，并提供两个版本 const 和非 const

T& front()
{
	return _pHead->_pNext->_val;
}

const T& front()const
{
	return _pHead->_pNext->_val;
}

T& back()
{
	return _pHead->_pPre->_val;
}

const T& back()const
{
	return _pHead->_pPre->_val;
}

2.3.7 插入和删除

insert

// 在pos位置前插入值为val的节点
iterator insert(iterator pos, const T& val)
{
	//构造一个新结点
	Node* pNewNode = new Node(val);
	Node* pCur = pos._pNode;
	//将新结点插入
	pNewNode->_pPre = pCur->_pPre;
	pNewNode->_pNext = pCur;
	pCur->_pPre->_pNext = pNewNode;
	pCur->_pPre = pNewNode;

	return pNewNode;
}

erase

iterator erase(iterator pos)
{
	//找到待删除的结点和下一个位置
	Node* pDel = pos._Node;
	Node* pRet = pDel->_pNext;

	//将该结点从链表中拆下来并删除
	pDel->_pPre->_pNext = pDel->_pNext;
	pDel->_pNext->_pPre = pDel->_pPre;
	delete pDel;

	return pRet;
}

push_back

void push_back(const T& val) 
{ 
	insert(end(), val); 
}

pop_back

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

push_front

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

pop_front

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

clear

void clear()
{
	Node* cur = _pHead->_pNext;
	
	//头删节点
	while (cur != _pHead)
	{
		_pHead->_pNext = cur->_pNext;
		delete cur;
		cur = _pHead->_pNext;
	}
	_pHead->_pNext = _pHead->_pPre = _pHead;
}

swap

void swap(list<T>& l)
{
	std::swap(_pHead, l._pHead);
}

3 list 和 vector 的对比

目录	vector	list
底层结构	顺序表, 空间连续	带头双向循环链表
随机访问	支持随机访问, 访问效率为 O(1)	不支持随机访问, 访问效率为 O(N)
插入和删除	任一位置插入删除效率低, 还需扩容	任一位置插入效率高
空间利用率	空间, 缓存利用率高	不连续空间, 容易造成内存碎片
迭代器	原生态的指针	对原生指针的封装
迭代器失效	插入和删除都会导致	只有删除会导致
使用场景	高效存储，支持随机访问	有大量插入和删除操作，不关心随机访问