list容器

帶頭結點的雙向循環連結清單

list操作

list容器的概念及其操作

構造和銷毀

詳解list容器(應用+模拟實作)list容器模拟實作list

list<int>L1;
	list<int>L2(10, 5);

	vector<int>v{ 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	list<int>L3(v.begin(), v.end());
	list<int>L4(L3);

元素通路

詳解list容器(應用+模拟實作)list容器模拟實作list

cout << L3.front() << endl;
cout << L2.back() << endl;

容量

詳解list容器(應用+模拟實作)list容器模拟實作list

元素修改

詳解list容器(應用+模拟實作)list容器模拟實作list

list<int>L;
L.push_back(1);
L.push_back(2);
L.push_back(3);
L.push_back(4);

cout << L.size() << endl;
L.push_front(0);
cout << L.front() << endl;

L.pop_front();
cout << L.front() << endl;


L.pop_back();
cout << L.back() << endl;

//查找元素
auto it = find(L.begin(), L.end(), 2);
//插入元素1,2,3
if (it != L.end())
	L.insert(it, 5);

L.erase(it);

疊代器

詳解list容器(應用+模拟實作)list容器模拟實作list

auto it = L2.begin();
	while (it != L2.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	for (auto& e : L3)
	{
		cout << e << " ";
	}
	cout << endl;

	cout << L3.front() << endl;
	cout << L2.back() << endl;

	auto rit = L4.rbegin();
	while (rit != L4.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;

一般容器周遊的時候都是左閉右開的區間

一般begin()都在要通路元素的第一個位置，而end()則是最後一個元素向後一個的位置，對于list而言也就是頭結點。而逆向列印時，疊代器位置正好反過來，在目前位置時，列印前一個結點。

詳解list容器(應用+模拟實作)list容器模拟實作list

list 特殊操作

詳解list容器(應用+模拟實作)list容器模拟實作list

list<int>L{ 9, 1, 2, 2, 3, 4, 2, 6, 8 };
	L.sort();
	//相鄰重複的元素才會被删除
	//是以使用時必須保證list有序
	L.unique();
	L.reverse();

疊代器失效

//List中疊代器失效的問題---疊代器指向的結點不存在
void TestListIterator()
{
	list<int>L{ 1, 2, 3, 4 };
	auto it = L.begin();

	//删除之後it已經不存在了
	//是以使用疊代器時，一但有删除元素要小心
	L.erase(it);
	//解決失效問題
	//重新指派it
	it = L.begin();
	while (it!=L.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

以上的應用隻給出了一部分，具體上面有個連結，專門講解list的應用，本文重點在模拟實作list的一些相關操作

模拟實作list

我們要模拟實作list應用中的幾個子產品

list結構定義

list是一個帶頭結點的雙向循環連結清單，是以我們要有一個頭結點的指針指向這個連結清單，因為在構造中，我們不管是什麼構造都需要先建立頭結點，是以我們将建立頭結點封裝成一個成員函數，提高代碼複用性。

雙向循環連結清單初始化就是頭結點的下個結點指向自己，上一個結點也指向自己

至于疊代器問題，我們稍後再來進行模拟

定義結點類型

// list: 帶頭結點雙向循環連結清單
template<class T>
struct ListNode
{
	ListNode(const T& data = T())
	: _pNext(nullptr)
	, _pPre(nullptr)
	, _data(data)
	{}

	ListNode<T>* _pNext;
	ListNode<T>* _pPre;
	T _data;
};

class list
	{
		typedef ListNode<T> Node;
	public:
		typedef list_iterator<T> iterator;
		typedef list_reverse_iterator<iterator, T> reverse_iterator;
	private:
		void CreateHead()
		{
			_pHead = new Node;
			_pHead->_pNext = _pHead;
			_pHead->_pPre = _pHead;
		}
	protected:
		Node* _pHead;

	};

構造與析構

首先是預設構造，預設構造隻需要建立出頭結點，即可。

list()
		{
			CreateHead();
		}

有參構造，有兩個參數，一個是建立多少個結點，第二個是每個結點的值。随後先建立頭結點，然後進行尾插，具體實作将放在

push_back

函數中，提高代碼複用性

list(int n, const T& data )
	{
		CreateHead();
		for (int i = 0; i < n; ++i)
		{
			push_back(data);
		}
	}

區間構造，我們需要用疊代器，因為給出的區間不一定就是list容器的區間，有可能是其他容器的區間，是以我們要使用類模闆，然後先建立頭結點，然後當

first

沒有走到末尾也就是

last

時，不斷的尾插

*first

裡的元素，然後

first++

,直到給所有元素賦完值

template<class Iterator>
list(Iterator first, Iterator last)
{
	CreateHead();
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

拷貝構造，傳進行類類型對象的引用，先建立頭結點，頭結點不能動，用臨時變量

pCur

指上來，當

pCur

沒有再次指向頭結點時，也就是沒有走完一圈，我們不斷的尾插給進來對象的資料,每插一個

pCur

往後走

list(const list<T>& L)
{
	CreateHead();
	Node* pCur = L._pHead->_pNext;	//從第一個元素走
	while (pCur != L._pHead)
	{
		push_back(pCur->_data);
		pCur = pCur->_pNext;
	}
}

指派操作符重載，還是傳進來類類型對象的引用，首先看是不是自己給自己指派，如果不是，我們先用

clear()

函數清除所有元素(後面會實作clear()函數)，然後再重複拷貝構造裡面的操作，最後傳回

*this

即可

//L1=L2;
list<T>& operator=(const list<T>& s)
{
	if (this != &s)
	{
		clear();			//先清空
		Node* pCur = L._pHead;
		while (pCur != _pHead)
		{
			push_back(pCur->_data);
			pCur = pCur->_pNext;
		}
	}
	return *this;
}

析構函數，我們先用

clear()

函數釋放掉所有元素，但是頭結點還在，是以我們再把頭結點釋放即可。

~list()
{
	clear();	
	delete[]_pHead;
}

元素通路

這裡的通路操作，思想很簡單，傳回第一個元素值，就是頭結點的下一個結點的值，最後一個元素的值，就是頭結點上一個元素的值。

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

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

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

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

容量

傳回目前容器中有效元素個數，我們定義一個臨時變量來記錄有效元素個數，周遊一遍整個連結清單，每周遊一個元素，個數就+1。

size_t size()const
{
	size_t count = 0;
	Node* pCur = _pHead->_pNext;
	while (pCur != _pHead)
	{
		++count;
		pCur = pCur->_pNext;
	}

	return count;
}

判空操作就是當頭結點的下一個結點指向自己就為空

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

改變容量的操作，我們要傳進來新容量，還有如果新容量大于舊容量，我們要對擴容的元素就是值填充，填充元素的值我們也要給出來，如果沒有給我們就給出一個預設值。

當新容量大于舊容量時，就讓變量i從舊容量的末尾開始走，走到新容量的末尾，然後不斷的尾插我們給進來的

data

當新容量小于舊容量時，就讓變量i從新容量開始走，走到舊容量的位置，不斷的

pop_back()

尾删元素即可。

void resize(size_t newsize, const T& data = T())
{
	size_t oldsize = size();
	if (newsize > oldsize)
	{
		// 節點增多
		for (size_t i = oldsize; i < newsize; ++i)
			push_back(data);
	}
	else
	{
		// 節點減少
		// oldsize:10   newsize:5
		for (size_t i = newsize; i < oldsize; ++i)
			pop_back();
	}
}

元素修改

我們剛才不斷的使用到了

push_back

這個函數，我們的尾插函數隻需要不斷的往尾部

insert

資料就行

insert()

我們稍後實作

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

pop_back()

我們隻需要把尾部元素删除掉，就是

end()

的前一個位置

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

頭插，在

begin()

的位置

insert

資料

data

就行

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

頭删，就是删除begin()位置的元素就行

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

我們之前相當于一直在推卸責任，不斷的把具體實作功能往後推，現在終于要實作具體的功能

insert函數傳回疊代器，在pos位置，插入T類型的資料data。

我們插入資料，對于list而言也就是插入一個結點，是以我們要先建立一個結點
新結點的前一個結點指向插入位置的前一個結點
新結點下一個結點指向目前插入位置的結點
新界點前一個結點的下一個結點指向新結點
目前位置的結點的前一個結點指向新結點
傳回疊代器類型的新結點

詳解list容器(應用+模拟實作)list容器模拟實作list

iterator insert(iterator pos, const T& data)
{
	Node* pNewNode = new Node(data);
	//連結清單為空删不了
	Node* pCur = pos._pCur;

	pNewNode->_pPre = pCur->_pPre;
	pNewNode->_pNext = pCur;
	pNewNode->_pPre->_pNext = pNewNode;
	pCur->_pPre = pNewNode;

	return iterator(pNewNode);
}

iterator erase(iterator pos)
	{
		Node* pDelNode = pos._pCur;
		if (pDelNode == _pHead)
			return end();

		Node* pRet = pDelNode->_pNext;//儲存删除結點的下一個，用于傳回
		pDelNode->_pPre->_pNext = pDelNode->_pNext;
		pDelNode->_pNext->_pPre = pDelNode->_pPre;
		delete pDelNode;

		return iterator(pRet);
	}

清除，就是一個一個把有效元素删除，用頭删法就行，當pCur沒有指向頭結點時，代表還沒有結束

不斷的讓頭結點指向pCur的下一個結點，然後删除pCur,再讓pCur指向頭結點的下一個結點

void clear()
{
	Node* pCur = _pHead->_pNext;
	// 頭删法
	// []-->1-->2-->3...
	while (pCur != _pHead)
	{
		_pHead->_pNext = pCur->_pNext;
		delete pCur;
		pCur = _pHead->_pNext;
	}

	_pHead->_pNext = _pHead;
	_pHead->_pPre = _pHead;
}

交換函數，此我們要交換兩個連結清單，我們隻需要調用庫函數swap，将兩個連結清單的頭指針傳進去即可。

void Swap(list<T>& L)
{
	swap(_pHead, L._pHead);
}

疊代器

疊代器的本身就是一個指針

我們可以看到我們最重要的

insert()

函數和

erase()

函數都需要用到疊代器來進行實作，而list的疊代器并非像

vector

那樣，一個簡單的指針就可以，如果是原生态指針，不能取到下一個結點。是以我們需将結點類型的指針重新封裝

疊代器如果要當成指針的方式進行應用，我們必須在疊代器中提供如下的方法，讓它具備類似于指針的特性

疊代器構造
移動疊代器(++/–)
兩個疊代器之間要可以進行比較(!=/==)
重載 * 運算符和 -> 運算符

// list疊代器：将節點類型的指針重新封裝
	template<class T>
	struct list_iterator
	{
		typedef ListNode<T> Node;
		typedef list_iterator<T> Self;
	public:
		list_iterator(Node* pCur)
			: _pCur(pCur)
		{}

		// 按照指針的方式進行應用
		T& operator*()
		{
			//傳回資料本身
			return _pCur->_data;
		}

		T* operator->()
		{
			//傳回資料的位址
			return &(_pCur->_data);
		}

		// 3. 移動
		Self& operator++()
		{
			_pCur = _pCur->_pNext;
			return *this;
		}

		Self operator++(int)
		{
			Self temp(*this);
			_pCur = _pCur->_pNext;
			return temp;
		}

		Self& operator--()
		{
			_pCur = _pCur->_pPre;
			return *this;
		}

		Self operator--(int)
		{
			Self temp(*this);
			_pCur = _pCur->_pPre;
			return temp;
		}

		// 4. 比較
		bool operator!=(const Self& s)
		{
			return _pCur != s._pCur;
		}

		bool operator==(const Self& s)
		{
			return _pCur == s._pCur;
		}

		Node* _pCur;
	};

總結:

如何給一個類定義疊代器：

分析：該類的疊代器是原生态的指針還是需要對指針進行封裝

取決于目前的資料結構（看是順序的結構還是其他的結構，順序結構可以是原生态的指針，鍊式或者樹形的疊代器需要進行封裝）

1.結合該類的資料結構，定義疊代器類（封裝指針）
2.将疊代器與該類進行結合：在容器類中--->typedef 疊代器類型 iterator
3.容器類中提供：begin()和end()

反向疊代器(了解)

template<class Iterator, class T>
	struct list_reverse_iterator
	{
		typedef list_reverse_iterator<Iterator, T> Self;
	public:
		list_reverse_iterator(Iterator it)
			: _it(it)
		{}

		T& operator*()
		{
			Iterator temp = _it;
			--temp;
			return *temp;
		}

		T* operator->()
		{
			return &(operator*());
		}

		Self& operator++()
		{
			--_it;
			return *this;
		}

		Self operator++(int)
		{
			Self temp(*this);
			_it--;
			return temp;
		}

		Self& operator--()
		{
			++_it;
			return *this;
		}

		Self operator--(int)
		{
			Self temp(*this);
			_it++;
			return temp;
		}

		bool operator!=(const Self& s)
		{
			return _it != s._it;
		}

		bool operator==(const Self& s)
		{
			return _it == s._it;
		}

		Iterator _it;
	};

測試

#include<vector>
void TestList1()
{
	bite::list<int>L1;
	bite::list<int>L2(10, 5);

	vector<int>v{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	bite::list<int>L3(v.begin(),v.end());
	bite::list<int>L4(L3);

	auto it = L2.begin();
	while (it != L2.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

詳解list容器(應用+模拟實作)list容器模拟實作list

list容器

list操作

構造和銷毀

元素通路

容量

元素修改

疊代器

list 特殊操作

疊代器失效

模拟實作list

list結構定義

構造與析構

元素通路

容量

元素修改

疊代器

反向疊代器(了解)

測試

繼續閱讀

c++中引用的作用

C++ 函數提高

百度2016年軟體測試開發工程師面經

深入了解c++中的函數模闆

c++中的異常---3(系統标準異常庫,編寫自己異常類)

黑馬程式員C++筆記--第三階段核心:【程式的記憶體模型】一、記憶體分區模型

c++常見并且必須記住的問題

c++中c_str()的用法詳解

windows下使用vscode調試c++

連結清單題目---4 删除連結清單中重複的結點和判斷連結清單是否為回文連結清單

C++模版模版

C++函數對象函數對象簡介

C++未定義行為-數組越界

C++中記憶體配置設定----C++學習之路

C++輸出對齊(如何使輸出對齊)

C++中關于const限定符學習筆記