C++模擬實現list功能

Posted on by

努力的最大好處，就在於你可以選擇你想要的生活，而不是被迫隨遇而安。

在這裡插入圖片描述

🎓list介紹

1、 list是可以在**常數范圍O(1)**內在任意位置進行插入和刪除的序列式容器，並且該容器可以前後雙向迭代，但list容器不適合用來做排序。
2、list的底層是一個循環雙向鏈表結構，雙向鏈表中每個元素存儲在互不相關的獨立節點中，在節點中通過指針指向其前一個元素和後一個元素。

🎓構造函數

在C++98中list的構造函數加上拷貝構造函數為如下四個。下面我們就模擬實現這裡的全部的構造函數。當然我們這裡並沒有像標準庫一樣使用空間配置器來創建空間，使用的是new運算符，但原理都是創建一塊新的空間。

在這裡插入圖片描述

🐱‍💻無參構造函數

這裡我們模擬默認的構造函數，默認值為T()，其含義為：該類型的默認值int類型就為0，char類型為’\0′,自定義類型會調用其構造函數來初始化這個匿名對象得到默認值。

list()		//無參默認構造函數
{
	this->m_head = new node(T());
	this->m_head->m_next = this->m_head;	//創建頭結點，並讓頭結點的頭尾相連形成循環結構
	this->m_head->m_prev = this->m_head;
}

🍖有參構造函數

list(size_t size, const T& val=T())	//n個元素構造函數
{
	this->m_head = new node(T());	//創建頭結點，並讓頭結點的頭尾相連形成循環結構
	this->m_head->m_next = this->m_head;
	this->m_head->m_prev = this->m_head;
	while (size--)
	{
		this->push_back(val);
	}
}

註意：

1、該構造函數知道其需要用於存儲n個數據的空間，所以我們使用new運算符開辟好空間，後用push_back()函數來尾插入val值。2、該構造函數還需要實現兩個重載函數，如果不實現其重載函數，會導致本來想調用n個元素構造函數時，編譯器會調用到我們下面要模擬實現的模板區間構造函數。 

list(long size, const T& val = T())	//n個元素構造函數
{
	assert(size > 0);
	this->m_head = new node(T());	//創建頭結點，並讓頭結點的頭尾相連形成循環結構
	this->m_head->m_next = this->m_head;
	this->m_head->m_prev = this->m_head;
	while (size--)
	{
		this->push_back(val);
	}
}

list(int size, const T& val = T())	//n個元素構造函數
{
	assert(size > 0);
	this->m_head = new node(T());	//創建頭結點，並讓頭結點的頭尾相連形成循環結構
	this->m_head->m_next = this->m_head;
	this->m_head->m_prev = this->m_head;
	while (size--)
	{
		this->push_back(val);
	}
}

可以看到，這兩個重載函數與之不同的就是其參數size的類型不同，但這卻是必要的，否則當我們使用以下代碼時，編譯器會優先與模板區間構造函數相匹配。

ZJ::list<int>L(2,1);	//不實現重載版本會調用到模板區間構造函數

並且因為構造函數2當中對參數first和last進行瞭解引用(*)（而int類型不能進行解引用操作）而報錯。

🚀模板區間構造函數

最後就是我們上面一直說到的模板區間構造函數瞭，因為該迭代器區間可以是其他容器的迭代器區間，該函數接收到的迭代器的類型是不確定的，所以我們這裡需要將該構造函數設計為一個函數模板，在函數體內將該迭代器區間的數據一個個尾插到容器當中即可。

template <class InputIterator>
list(InputIterator first, InputIterator last)		//區間構造
{
	this->m_head = new node(T());	//創建頭結點
	this->m_head->m_next = this->m_head;
	this->m_head->m_prev = this->m_head;
	while (first != last)
	{
		node* newnode = new node(*first);
		node* tail = this->m_head->m_prev;
		tail->m_next = newnode;
		newnode->m_prev = tail;
		newnode->m_next = this->m_head;
		this->m_head->m_prev = newnode;
		++first;
	}
}

註意：

1、該區間必須是前閉後開[obj.begin()，obj.end());

🎓拷貝構造函數

拷貝構造的思想是我們是很容易想到的，就是遍歷一遍我們要拷貝的對象obj鏈表，並將obj每個元素的值給this對象的每一個對應的結點，並將其每個結點都鏈接起來。

list(const list<T>& obj)		//拷貝構造函數
{
	this->m_head = new node(T());	//創建頭結點，並讓頭結點的頭尾相連形成循環結構
	this->m_head->m_next = this->m_head;
	this->m_head->m_prev = this->m_head;
	const_iterator it = obj.begin();
	while (it != obj.end())
	{
		node* newnode = new node(it.m_pnode->m_val);	//創建新結點並把值賦予給它

		node* tail = this->m_head->m_prev;
		tail->m_next = newnode;
		newnode->m_prev = tail;
		newnode->m_next = this->m_head;
		this->m_head->m_prev = newnode;
		++it;
	}
}

🎓賦值運算符重載

根據我們之前的博客的往歷，這裡我們采用現代寫法，及用obj調用拷貝構造函數創建一個臨時對象temp，並將temp與我們的this指針指向的對象的指針交換即可。

list<T>& operator=(const list<T>& obj)		//賦值運算符重載
{
	if (this != &obj)	//防止自我賦值
	{
		list<T>temp(obj);
		this->swap(temp);
	}
	return *this;		//返回自己
}

註意：

1、上面的temp臨時對象出瞭if語句時就會自動調用析構函數進行釋放內存，故不會造成內存的泄漏等問題。

🎓析構函數

析構函數這裡，我就有點偷懶啦，復用瞭我們下面要模擬實現的pop_front()函數，大致思路就是從頭到尾一個一個刪除結點，並把頭結點也刪除並至空。

~list()		//析構函數
{
	iterator it = this->begin();

	while (it != this->end())	//復用我們寫的頭刪，一個一個的刪除，當然也可以復用尾刪pop_back()和erase()
	{
		++it;
		this->pop_front();
	}

	delete this->m_head;
	this->m_head = nullptr;
}

🎓迭代器

在C++中我們的迭代器有如下幾種：

在這裡插入圖片描述

下面我隻模擬begin()和end()迭代器。

iterator begin()
{
	return iterator(this->m_head->m_next);
}

const_iterator begin()	const
{
	return const_iterator(this->m_head->m_next);
}

iterator end()
{
	return iterator(this->m_head);
}

const_iterator end()	const
{
	return const_iterator(this->m_head);
}

上面我們模擬實現瞭我們的迭代器，並且有普通迭代器和const迭代器。但是我們還要瞭解迭代器的原理是上面，在之前我們的博客中我們說過並不是每個迭代器都是原生指針，其中我們的list就是封裝瞭一個指針變量來達到實現iterator的結果。

typedef list_iterator<T,T&,T*> iterator;		//普通迭代器
typedef list_iterator<T,const T&,const T*> const_iterator;	//常量迭代器

可能有人會疑惑，上面這兩個迭代器不都差不多嘛，隻是名字不一樣，為什麼不直接在類型上加const，而是在模板參數上指定加上const屬性呢？我們要知道由於const對象隻能調用常函數，但是平時我們使用std::list時是不是可以支持 ++、– 呢？如果是const對象，它隻能調用常函數，一旦加上變成const函數，那我們的const迭代器就不能進行++、–、’ * ‘等,而我們要達到的效果是可以進行++、–等，但僅僅是不能其元素的值而已。所以 我們這裡封裝瞭一個模板指針。我們通過模板的參數不同來控制它的讀取操作。

🗼迭代器構造函數

就是將一個指針傳過來，並賦給我們的成員變量m_pnode。

list_iterator(node* pnode)
			:m_pnode(pnode)
		{}

🏝迭代器關系運算符重載

因為我們要實現迭代器的相關遍歷操作例如下面的代碼：
ZJ::list<int>::iterator it = L1.begin();
it != L1.end()

bool operator!=(const myself&obj) const		//重載！=號
{
	return this->m_pnode != obj.m_pnode;
}

bool operator==(const myself& obj) const	//重載==號
{
	return this->m_pnode == obj.m_pnode;
}

🧸迭代器++ –運算符重載

其中下面返回的myself類型其實就是我們的迭代器這個類的類型，隻是我們將其typedef瞭一下代碼如下：

typedef list_iterator<T, Ref, Ptr>myself;

這裡重載的前置與後置要分別開來，後置需要使用int占位符來占位，不然會發生錯誤。

myself& operator++()		//重載前置++
{
	//由於我們的list是雙向循環鏈表，我們的++，就是指向下一個結點
	this->m_pnode = this->m_pnode->m_next;
	return *this;
}

myself operator++(int)		//重載後置++
{
	const myself temp(*this);
	this->m_pnode = this->m_pnode->m_next;
	return temp;
}

myself& operator--()		//重載前置--
{
	//由於我們的list是雙向循環鏈表，我們的--就是得到它上一個結點的迭代器
	this->m_pnode = this->m_pnode->m_prev;
	return *this;
}

myself operator--(int)		//重載後置--
{
	const myself temp(*this);
	this->m_pnode = this->m_pnode->m_prev;
	return temp;
}

🗽迭代器 * 運算符重載

由於我們知道Ref是由兩種類型的，一種是T&,另一種是const T&,所以當我們的對象是const對象時，我們可以控制它不讓其修改。

Ref operator* ()		//重載  *
{
	return this->m_pnode->m_val;
}

🪐迭代器 -> 運算符重載

為什麼要重載->運算符呢？這是因為如果我們list中存儲的是自定義類型時，我們的迭代器無法使用->去得到其成員。

Ptr operator->()		//重載 ->
{
	return &this->m_pnode->m_val;
}

🐱‍👓總結

到瞭這裡可能會有人會問為什麼我們不寫迭代器的拷貝構造函數和析構函數呢？
答：這是因為我們的迭代器是用來遍歷容器中的部分或全部元素，每個迭代器對象代表容器中的確定的地址，並且這些結點元素析構和拷貝並不歸我們管，結點應該歸我們的list管，所以編譯器默認提供的淺拷貝就已經足夠瞭。

🎓容量相關函數

 🐱‍🐉empty()

功能：是用來獲取容器中是否為空。返回值：bool。 

bool empty()	const		//判空
{
	return this->begin() == this->end();	//就是begin()與end()同時指向頭結點時的情況
}

🎃size()

功能：是用來獲取元素的個數。返回值：size_t(無符號整型)。註意：但是在鏈表中這個接口並不常用。如果頻繁的調用該接口會造成性能的下降。 

//遍歷一遍鏈表來得到元素個數，為什麼使用遍歷一遍鏈表呢？
//這是因為我們使用鏈表時很少會去知道它的元素個數，但如果頻繁的調用該接口會造成性能的下降
//此時我們應該在list類中將增加一個記錄元素個數的變量size
//如果有元素插入就增加，刪除就減少
size_t size()	const	//獲得元素個數
{
	size_t size = 0;
	const_iterator it = this->begin();
	while(it!=this->end())
	{
		++it;
		++size;
	}
	return size;
}

🎓元素訪問相關函數

 🎋back()

功能：獲取最後一個元素的值。返回值：存儲的類型的引用。 

T& back()
{
	assert(!this->empty());
	return this->m_head->m_prev->m_val;
}

const T& back()   const
{
	assert(!this->empty());
	return this->m_head->prev->m_val;
}

🎑front()

功能：獲取第一個元素的值。返回值：存儲的類型的引用。 

T& front()
{
	assert(!this->empty());
	return  this->m_head->m_next->m_val;
}

const T& front() const
{
	assert(!this->empty());
	return this->m_head->m_next->m_val;
}

🎓修改相關函數

🥙push_back()

功能：在尾部插入一個元素。返回值：void（無返回值）。 

void push_back(const T& val)	//尾插
{
	node* tail = this->m_head->m_prev;	//指向尾部結點
	node* newnode = new node(val);		//創建新結點
	newnode->m_next = tail->m_next;		//將新結點的m_next指向頭結點
	newnode->m_prev = tail;				//將新結點m_prev指向tail結點
	tail->m_next = newnode;				//並將原來的尾結點的m_next指向newnode
	this->m_head->m_prev = newnode;		//並將頭結點的m_prev指向新的尾
}

🐱‍🚀push_front()

功能：在頭部插入一個元素。返回值：void（無返回值）。 

void push_front(const T& val)	//頭插
{
	node* newnode = new node(val);	//創建新結點
	node*  next = this->m_head->m_next;	//指向第一個結點
	newnode->m_next = next;		//將創建的新結點newnode的m_next指向我們原來的第一個元素next
	this->m_head->m_next = newnode;	//在將我們的頭結點的m_next指向新創建的結點
	newnode->m_prev = this->m_head;	//在將新結點的m_prev指向頭結點
	next->m_prev = newnode;	//在將原先第一個結點元素的m_prev指向新創建的結點
}

🚩pop_back()

功能：在尾部刪除一個元素。返回值：void（無返回值）。 

void pop_back()		//尾刪
{
	assert(!empty());	//斷言 如果list已經為空，則刪除不瞭
	node* tail = this->m_head->m_prev;	//先找到我們要刪除的尾結點
	node* prev = tail->m_prev;		//再找到要刪除的尾結點的前一個結點
	this->m_head->m_prev = prev;	//將頭結點的m_prev指向新的尾prev
	prev->m_next = this->m_head;	//再將prev的m_next指向頭結點
	tail->m_next = tail->m_prev = nullptr;	//把要刪除的元素的成員至nullptr
	tail->m_val = T();		//將要刪除的元素的值置為匿名對象的默認值
	delete tail;			//刪除尾結點
}

🐱‍🏍pop_front()

功能：在頭部刪除一個元素。返回值：void（無返回值）。 

void pop_front()	//頭刪
{
	assert(!empty());	//斷言 如果list已經為空，則刪除不瞭
	node* delnode = this->m_head->m_next;	//先找到我們要刪除的第一個結點位置
	node* next = delnode->m_next;			//在找到刪除結點的下一個結點的位置
	this->m_head->m_next = next;			//再將頭結點的m_next指向我們新的第一個結點
	next->m_prev = this->m_head;			//再將我們的新的第一個結點的m_prev指向頭結點
	delnode->m_next = delnode->m_prev = nullptr;	//把要刪除的元素的成員至nullptr
	delnode->m_val = T();		//將要刪除的元素的值置為匿名對象的默認值
	delete delnode;		//刪除第一個結點
}

🎐insert()

在c++98中我們的insert()函數有如下三種版本：

在這裡插入圖片描述

下面我們就將其模擬實現：

指定位置插入一個元素

功能：在指定位置插入一個元素。返回值：插入的元素的位置的迭代器。 

//插入元素到指定位置，返回的是插入的元素的迭代器
iterator insert(iterator pos, const T& val)
{
	assert(pos.m_pnode != nullptr);		//斷言 迭代器是否為空指針錯誤
	node* newnode = new node(val);		//創建新結點

	node* cur = pos.m_pnode;		//記錄當前結點的指針
	node* prev = cur->m_prev;		//記錄當前結點的前一個結點的指針

	newnode->m_next = cur;
	newnode->m_prev = prev;
	prev->m_next = newnode;
	cur->m_prev = newnode;

	return iterator(newnode);		//返回一個用當前的插入的元素的結點構建的匿名對象的迭代器
}

指定位置插入n個相同的元素

功能：在指定位置插入一個元素。返回值：void(無返回值)。 

void insert(iterator pos, size_t n, const T& val)	//插入n個val
{
	assert(pos.m_pnode != nullptr);		//斷言 迭代器是否為空指針錯誤
	while (n--)
	{
		node* newnode = new node(val);

		node* cur = pos.m_pnode;
		node* prev = cur->m_prev;

		newnode->m_prev = prev;
		prev->m_next = newnode;
		newnode->m_next = cur;
		cur->m_prev = newnode;
	}
}

void insert(iterator pos, int n, const T& val)	//插入n個val
{
	assert(pos.m_pnode != nullptr);		//斷言 迭代器是否為空指針錯誤
	assert(n > 0);
	while (n--)
	{
		node* newnode = new node(val);

		node* cur = pos.m_pnode;
		node* prev = cur->m_prev;

		newnode->m_prev = prev;
		prev->m_next = newnode;
		newnode->m_next = cur;
		cur->m_prev = newnode;
	}
}

void insert(iterator pos, long n, const T& val)	//插入n個val
{
	assert(pos.m_pnode != nullptr);		//斷言 迭代器是否為空指針錯誤
	assert(n > 0);
	while (n--)
	{
		node* newnode = new node(val);

		node* cur = pos.m_pnode;
		node* prev = cur->m_prev;

		newnode->m_prev = prev;
		prev->m_next = newnode;
		newnode->m_next = cur;
		cur->m_prev = newnode;
	}
}

註意：這裡的insert在指定位置插入為什麼要實現三種重載版本呢？這與上面的構造函數問題是相同類型的，都是與模板區間構造有關，這裡就不多贅述瞭。
指定位置插入區間內的元素

功能：在指定位置插入區間內的元素。返回值：void(無返回值)。註意：1、該區間必須是前閉後開; 

template <class InputIterator>
void insert(iterator pos, InputIterator first, InputIterator last)	//區間插入
{
	assert(pos.m_pnode != nullptr);		//斷言 迭代器是否為空指針錯誤
	while (first != last)
	{
		node* newnode = new node(*first);

		node* cur = pos.m_pnode;
		node* prev = cur->m_prev;

		newnode->m_prev = prev;
		prev->m_next = newnode;
		newnode->m_next = cur;
		cur->m_prev = newnode;
		++first;
	}
}

🎍erase()

在C++98中erase()有兩種版本，一個是刪除指定位置，另一個是刪除區間內的元素。如下圖所示：

在這裡插入圖片描述

刪除指定位置

功能：刪除指定位置的元素。返回值：刪除指定位置的元素的下一個結點的迭代器。 

//刪除指定位置的元素，返回下一個元素的迭代器，但要註意的是：
//如果刪除的最後一個元素，此時返回的是頭結點也就是end()位置的迭代器
iterator erase(iterator pos)			
{
	assert(pos.m_pnode != nullptr);		//斷言 迭代器是否為空指針錯誤
	assert(pos != end());				//斷言 list內元素為空及刪除頭結點的情況
	
	node* next = pos.m_pnode->m_next;
	node* prev = pos.m_pnode->m_prev;

	prev->m_next = next;
	next->m_prev = prev;

	pos.m_pnode->m_next = pos.m_pnode->m_prev = nullptr;
	pos.m_pnode->m_val = T();
	delete pos.m_pnode;

	return iterator(next);		
}

刪除區間內的元素

功能：刪除區間內的元素。返回值：刪除區間內的元素的下一個結點的迭代器。也就是返回last迭代器這個位置。註意： 1、該區間必須是前閉後開; 

iterator erase(iterator first, iterator last)		//區間刪除
{
	node* prev = first.m_pnode->m_prev;
	node* next = last.m_pnode;

	while (first != last)
	{
		node* cur = first.m_pnode;
		++first;
		cur->m_next = cur->m_prev = nullptr;
		cur->m_val = T();
		delete cur;
		cur = nullptr;
	}

	prev->m_next = next;
	next->m_prev = prev;

	return iterator(next);
}

💸clear()

功能：用於清空我們list中的所有元素的值，但不是要把list對象也刪除。返回值：void（無返回值）。 

void clear()		//清空元素，而不是把整個鏈表刪除掉
	{
		iterator it = this->begin();	

		while (it != this->end())	
		//復用我們寫的頭刪，一個一個的刪除，當然也可以復用尾刪pop_back()和erase()
		{
			++it;
			this->pop_front();
		}
	}

🧨swap()

功能：swap顧名思義就是交換的意思，這裡我們將這個swap作為我們的成員函數，用來交換兩個list鏈表。返回值: void（無返回值）。 

void swap(list<T>& obj)
{
	node* temp = this->m_head;
	this->m_head = obj.m_head;
	obj.m_head = temp;
}

🍜完整代碼如下

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<assert.h>
using  namespace std;

namespace ZJ
{
	template<class T>	
	class list_node		//結點
	{
	public:
		list_node(T val=T())		//構造函數
			:m_val(val)
			,m_prev(nullptr)
			,m_next(nullptr)
		{}
	public:
		T m_val;		//值
		list_node<T>* m_prev;	//指向前一個的指針
		list_node<T>* m_next;	//指向下一個的指針

	};

	template<class T,class Ref,class Ptr>		//封裝一個node型指針，制作成迭代器類
	class list_iterator
	{
	public:
		typedef list_node<T> node;
		typedef list_iterator<T, Ref, Ptr>myself;
		list_iterator(node* pnode)
			:m_pnode(pnode)
		{}

		Ref operator* ()		//重載  *
		{
			return this->m_pnode->m_val;
		}

		Ptr operator->()		//重載 ->
		{
			return &this->m_pnode->m_val;
		}

		bool operator!=(const myself&obj) const		//重載！=號
		{
			return this->m_pnode != obj.m_pnode;
		}

		bool operator==(const myself& obj) const	//重載==號
		{
			return this->m_pnode == obj.m_pnode;
		}

		myself& operator++()		//重載前置++
		{
			this->m_pnode = this->m_pnode->m_next;
			return *this;
		}

		myself operator++(int)		//重載後置++
		{
			const myself temp(*this);
			this->m_pnode = this->m_pnode->m_next;
			return temp;
		}

		myself& operator--()		//重載前置--
		{
			this->m_pnode = this->m_pnode->m_prev;
			return *this;
		}

		myself operator--(int)		//重載後置--
		{
			const myself temp(*this);
			this->m_pnode = this->m_pnode->m_prev;
			return temp;
		}

	public:
		node* m_pnode;
	};

	template<class T>
	class list
	{
	public:
		typedef list_node<T> node;		
		typedef list_iterator<T,T&,T*> iterator;		//普通迭代器
		typedef list_iterator<T,const T&,const T*> const_iterator;	//常量迭代器

	public:
		list()		//無參默認構造函數
		{
			this->m_head = new node(T());
			this->m_head->m_next = this->m_head;
			this->m_head->m_prev = this->m_head;
		}

		list(size_t size, const T& val=T())	//n個元素構造函數
		{
			this->m_head = new node(T());
			this->m_head->m_next = this->m_head;
			this->m_head->m_prev = this->m_head;
			while (size--)
			{
				this->push_back(val);
			}
		}

		list(long size, const T& val = T())	//n個元素構造函數
		{
			assert(size > 0);
			this->m_head = new node(T());
			this->m_head->m_next = this->m_head;
			this->m_head->m_prev = this->m_head;
			while (size--)
			{
				this->push_back(val);
			}
		}

		list(int size, const T& val = T())	//n個元素構造函數
		{
			assert(size > 0);
			this->m_head = new node(T());
			this->m_head->m_next = this->m_head;
			this->m_head->m_prev = this->m_head;
			while (size--)
			{
				this->push_back(val);
			}
		}

		template <class InputIterator>
		list(InputIterator first, InputIterator last)		//區間構造
		{
			this->m_head = new node(T());
			this->m_head->m_next = this->m_head;
			this->m_head->m_prev = this->m_head;
			while (first != last)
			{
				node* newnode = new node(*first);
				node* tail = this->m_head->m_prev;
				tail->m_next = newnode;
				newnode->m_prev = tail;
				newnode->m_next = this->m_head;
				this->m_head->m_prev = newnode;
				++first;
			}
		}
		
		list(const list<T>& obj)		//拷貝構造函數
		{
			this->m_head = new node(T());
			this->m_head->m_next = this->m_head;
			this->m_head->m_prev = this->m_head;
			const_iterator it = obj.begin();
			while (it != obj.end())
			{
				node* newnode = new node(it.m_pnode->m_val);

				node* tail = this->m_head->m_prev;
				tail->m_next = newnode;
				newnode->m_prev = tail;
				newnode->m_next = this->m_head;
				this->m_head->m_prev = newnode;
				++it;
			}
		}

		list<T>& operator=(const list<T>& obj)		//賦值運算符重載
		{
			if (this != &obj)
			{
				list<T>temp(obj);
				this->swap(temp);
			}
			return *this;
		}


		~list()		//析構函數
		{
			iterator it = this->begin();

			while (it != this->end())	//復用我們寫的頭刪，一個一個的刪除，當然也可以復用尾刪pop_back()和erase()
			{
				++it;
				this->pop_front();
			}

			delete this->m_head;
			this->m_head = nullptr;
		}

		iterator begin()
		{
			return iterator(this->m_head->m_next);
		}

		const_iterator begin()	const
		{
			return const_iterator(this->m_head->m_next);
		}

		iterator end()
		{
			return iterator(this->m_head);
		}

		const_iterator end()	const
		{
			return const_iterator(this->m_head);
		}

		bool empty()	const		//判空
		{
			return this->begin() == this->end();	//就是begin()與end()同時指向頭結點時的情況
		}

		//遍歷一遍鏈表來得到元素個數，為什麼使用遍歷一遍鏈表呢？
		//這是因為我們使用鏈表時很少會去知道它的元素個數，但如果頻繁的調用該接口會造成性能的下降
		//此時我們應該在list類中將增加一個記錄元素個數的變量size
		//如果有元素插入就增加，刪除就減少
		size_t size()	const	//獲得元素個數
		{
			size_t size = 0;
			const_iterator it = this->begin();
			while(it!=this->end())
			{
				++it;
				++size;
			}
			return size;
		}

		T& back()
		{
			assert(!this->empty());
			return this->m_head->m_prev->m_val;
		}

		const T& back()   const
		{
			assert(!this->empty());
			return this->m_head->prev->m_val;
		}

		T& front()
		{
			assert(!this->empty());
			return  this->m_head->m_next->m_val;
		}

		const T& front() const
		{
			assert(!this->empty());
			return this->m_head->m_next->m_val;
		}

		void push_front(const T& val)	//頭插
		{
			node* newnode = new node(val);
			node*  next = this->m_head->m_next;
			newnode->m_next = next;
			this->m_head->m_next = newnode;
			newnode->m_prev = this->m_head;
			next->m_prev = newnode;
		}

		void push_back(const T& val)	//尾插
		{
			node* tail = this->m_head->m_prev;
			node* newnode = new node(val);
			newnode->m_next = tail->m_next;
			newnode->m_prev = tail;
			tail->m_next = newnode;
			this->m_head->m_prev = newnode;
		}


		//插入元素到指定位置，返回的是插入的元素的迭代器
		iterator insert(iterator pos, const T& val)
		{
			assert(pos.m_pnode != nullptr);		//斷言 迭代器是否為空指針錯誤
			node* newnode = new node(val);		//創建新結點

			node* cur = pos.m_pnode;		//記錄當前結點的指針
			node* prev = cur->m_prev;		//記錄當前結點的前一個結點的指針

			newnode->m_next = cur;
			newnode->m_prev = prev;
			prev->m_next = newnode;
			cur->m_prev = newnode;

			return iterator(newnode);		//返回一個用當前的插入的元素的結點構建的匿名對象的迭代器
		}

		void insert(iterator pos, size_t n, const T& val)	//插入n個val
		{
			assert(pos.m_pnode != nullptr);		//斷言 迭代器是否為空指針錯誤
			while (n--)
			{
				node* newnode = new node(val);

				node* cur = pos.m_pnode;
				node* prev = cur->m_prev;

				newnode->m_prev = prev;
				prev->m_next = newnode;
				newnode->m_next = cur;
				cur->m_prev = newnode;
			}
		}

		void insert(iterator pos, int n, const T& val)	//插入n個val
		{
			assert(pos.m_pnode != nullptr);		//斷言 迭代器是否為空指針錯誤
			assert(n > 0);
			while (n--)
			{
				node* newnode = new node(val);

				node* cur = pos.m_pnode;
				node* prev = cur->m_prev;

				newnode->m_prev = prev;
				prev->m_next = newnode;
				newnode->m_next = cur;
				cur->m_prev = newnode;
			}
		}

		void insert(iterator pos, long n, const T& val)	//插入n個val
		{
			assert(pos.m_pnode != nullptr);		//斷言 迭代器是否為空指針錯誤
			assert(n > 0);
			while (n--)
			{
				node* newnode = new node(val);

				node* cur = pos.m_pnode;
				node* prev = cur->m_prev;

				newnode->m_prev = prev;
				prev->m_next = newnode;
				newnode->m_next = cur;
				cur->m_prev = newnode;
			}
		}

		template <class InputIterator>
		void insert(iterator pos, InputIterator first, InputIterator last)	//區間插入
		{
			assert(pos.m_pnode != nullptr);		//斷言 迭代器是否為空指針錯誤
			while (first != last)
			{
				node* newnode = new node(*first);

				node* cur = pos.m_pnode;
				node* prev = cur->m_prev;

				newnode->m_prev = prev;
				prev->m_next = newnode;
				newnode->m_next = cur;
				cur->m_prev = newnode;
				++first;
			}
		}

		void pop_front()	//頭刪
		{
			assert(!empty());	//斷言 如果list已經為空，則刪除不瞭
			node* delnode = this->m_head->m_next;
			node* next = delnode->m_next;
			this->m_head->m_next = next;
			next->m_prev = this->m_head;
			delnode->m_next = delnode->m_prev = nullptr;
			delnode->m_val = T();
			delete delnode;
		}

		void pop_back()		//尾刪
		{
			assert(!empty());	//斷言 如果list已經為空，則刪除不瞭
			node* tail = this->m_head->m_prev;
			node* prev = tail->m_prev;
			this->m_head->m_prev = prev;
			prev->m_next = this->m_head;
			tail->m_next = tail->m_prev = nullptr;
			tail->m_val = T();
			delete tail;
		}


		//刪除指定位置的元素，返回下一個元素的迭代器，但要註意的是：
		//如果刪除的最後一個元素，此時返回的是頭結點也就是end()位置的迭代器
		iterator erase(iterator pos)			
		{
			assert(pos.m_pnode != nullptr);		//斷言 迭代器是否為空指針錯誤
			assert(pos != end());				//斷言 list內元素為空及刪除頭結點的情況
			
			node* next = pos.m_pnode->m_next;
			node* prev = pos.m_pnode->m_prev;

			prev->m_next = next;
			next->m_prev = prev;

			pos.m_pnode->m_next = pos.m_pnode->m_prev = nullptr;
			pos.m_pnode->m_val = T();
			delete pos.m_pnode;

			return iterator(next);		
		}

		iterator erase(iterator first, iterator last)		//區間刪除
		{
			node* prev = first.m_pnode->m_prev;
			node* next = last.m_pnode;

			while (first != last)
			{
				node* cur = first.m_pnode;
				++first;
				cur->m_next = cur->m_prev = nullptr;
				cur->m_val = T();
				delete cur;
				cur = nullptr;
			}

			prev->m_next = next;
			next->m_prev = prev;

			return iterator(next);
		}

		void clear()		//清空元素，而不是把整個鏈表刪除掉
		{
			iterator it = this->begin();	

			while (it != this->end())	//復用我們寫的頭刪，一個一個的刪除，當然也可以復用尾刪pop_back()和erase()
			{
				++it;
				this->pop_front();
			}
		}

		void swap(list<T>& obj)
		{
			node* temp = this->m_head;
			this->m_head = obj.m_head;
			obj.m_head = temp;
		}
	private:
		node* m_head;		//頭指針
	};
}

到此這篇關於C++模擬實現list的文章就介紹到這瞭,更多相關C++list實現內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：