文章目錄

1 什麼是list？
- 1.1 模拟實作預備知識
2 list原型測試與實作
- 2.1 構造函數（拷貝構造，指派構造，析構）
- 2.2 疊代器
- 2.3 capacity
- 2.4 modifiers
- - 2.4.1 assign
  - 2.4.2 push_back/pop_back/push_front/pop_front
  - 2.4.3 insert
  - 2.4.4 erase
  - 2.4.5 swap
  - 2.4.6 resize
  - 2.4.7 clear
- 2.5 list 疊代器補充
3 list疊代器失效
附贈思考

1 什麼是list？

list是可以在常數範圍内在任意位置插圖和删除的序列式容器，并且支援前後雙向疊代。
list的低層本質是雙向連結清單結構，且其節點存儲在互不相關的獨立節點中，節點通過指針通路其前面和後面的元素。
list在插入和删除時效率高于vector。
list不支援随機通路，但vector支援随機通路。

簡單的list結果如圖：

list中有_prev指針、_next指針分别指向目前節點的上一個元素和下一個元素。

STL之list介紹及實作（list接口、模拟實作list）1 什麼是list？2 list原型測試與實作3 list疊代器失效附贈思考

1.1 模拟實作預備知識

先定義一個list節點類：

//List節點類 （雙向帶頭訓練連結清單）
	template<class T>
	struct _list_node
	{
		T _val;
		_list_node<T>* _next;
		_list_node<T>* _prev;

		_list_node(const T& val = T())
			:_val(val)
			, _prev(nullptr)
			, _next(nullptr)
		{}
	};

list實作部分：

template<class T>
	class list
	{
		typedef _list_node<T> node;
	public:
		typedef _list_iterartor<T, T&, T*> iterator;
		typedef _list_iterartor<T, const T&, const T*> const_iterator;
	
		//list模拟實作部分，在下文中有描述		

	private:
		node* _head;
	};

2 list原型測試與實作

2.1 構造函數（拷貝構造，指派構造，析構）

構造函數測試：

STL之list介紹及實作（list接口、模拟實作list）1 什麼是list？2 list原型測試與實作3 list疊代器失效附贈思考

模拟實作代碼：

//預設的
		list()
		{
			//_head = new node(T());
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		// 拷貝構造 copy(lt)
		list(const list<T>& lt)
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
			for (const auto& e : lt) //& 避免值過大 
			{
				push_back(e);
			}
		}

		// 深拷貝 copy = lt1; 傳統寫法
		/*	list<T>& operator=(const list<T>& lt)
		{
			if (this != &lt)
			{
				clear();
				for (const auto& e : lt)
				{
				push_back(e);
				}
			}
				return *this;
		}*/

		// copy = lt1; 現代寫法
		list<T>& operator=(list<T> lt)
		{
			swap(_head, lt._head);

			return *this;
		}

		//析構
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

2.2 疊代器

将疊代器了解成為一個指針，該指針指向list中某個節點。

STL之list介紹及實作（list接口、模拟實作list）1 什麼是list？2 list原型測試與實作3 list疊代器失效附贈思考

模拟實作：

STL之list介紹及實作（list接口、模拟實作list）1 什麼是list？2 list原型測試與實作3 list疊代器失效附贈思考

參考代碼：

iterator begin()
		{
			return iterator(_head->_next);
		}

		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}

		iterator end()
		{
			return iterator(_head);
		}

		const_iterator end() const
		{
			return const_iterator(_head);
		}

2.3 capacity

list容器的容量測試：

STL之list介紹及實作（list接口、模拟實作list）1 什麼是list？2 list原型測試與實作3 list疊代器失效附贈思考

capacity的部分實作代碼：

（分析：當begin位置沒有元素時，即begin()=end()時，list為空；關于求size，隻需要使用疊代器依次疊代，并對size++，就可以實作size函數）

bool empty()
		{
			return begin() == end()；
		}

		size_t size()
		{
			size_t sz = 0;
			iterator it = begin();
			while (it != end())
			{
				++sz;
				++it;
			}

			return sz;
		}

2.4 modifiers

list容器的元素修改，有下圖所示幾種可能，我們分别進行分析。

STL之list介紹及實作（list接口、模拟實作list）1 什麼是list？2 list原型測試與實作3 list疊代器失效附贈思考

2.4.1 assign

STL之list介紹及實作（list接口、模拟實作list）1 什麼是list？2 list原型測試與實作3 list疊代器失效附贈思考

2.4.2 push_back/pop_back/push_front/pop_front

系統調用接口測試：

STL之list介紹及實作（list接口、模拟實作list）1 什麼是list？2 list原型測試與實作3 list疊代器失效附贈思考

模拟實作代碼：

備注：這裡不做具體分析，因為下文已經對insert做了詳細分析，這四個接口都可以根據insert接口來實作。

void push_back(const T& x)
		{
			//寫法一
			//node *newnode = new node(x);//new一個新節點
			//node *tail = _head->_prev;//頭指針的_prev指向尾
			//tail->_next = newnode;
			//newnode->_prev = tail;
			//newnode->_next = _head;
			//_head->_prev = newnode;

			//寫法二
			insert(end(), x);//end()位置之前插入
		}

		void push_front(const T& x)
		{
			//寫法一
			//node *newnode = new node(x);
			//node *next = _head->_next;
			//_head->_next = newnode;
			//newnode->_prev=_head;
			//newnode->_next = next;
			//next->_prev = newnode;

			//寫法二
			insert(begin(), x);
		}

		void pop_back()
		{
			//寫法一
			/*assert(!empty());
			node *popnode = _head->_prev;
			node *prev = popnode->_prev;
			_head->_prev;
			prev->_next = _head;*/

			//寫法二
			erase(--end()); //end是哨兵位，--之後是最後一個
		}

		void pop_front()
		{
			//寫法一
			/*assert(!empty());
			node *popnode = _head->_next;
			node *next = popnode->_next;
			_head->_next = next;
			next->_prev = _head;*/

			//寫法二
			erase(begin());
		}

2.4.3 insert

insert接口測試：

STL之list介紹及實作（list接口、模拟實作list）1 什麼是list？2 list原型測試與實作3 list疊代器失效附贈思考

insert模拟實作：

（注：這裡隻實作插入一個字元）

STL之list介紹及實作（list接口、模拟實作list）1 什麼是list？2 list原型測試與實作3 list疊代器失效附贈思考

參考代碼：

//插入
		void insert(iterator pos, const T& x)
		{
			assert(pos._pnode);

			node* cur = pos._pnode;
			node* prev = cur->_prev;
			node* newnode = new node(x);

			// prev newnode cur
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
		}

2.4.4 erase

erase接口測試：

STL之list介紹及實作（list接口、模拟實作list）1 什麼是list？2 list原型測試與實作3 list疊代器失效附贈思考

模拟實作erase:

STL之list介紹及實作（list接口、模拟實作list）1 什麼是list？2 list原型測試與實作3 list疊代器失效附贈思考

iterator erase(iterator pos)
		{
			assert(pos._pnode);
			assert(pos != end());

			node* prev = pos._pnode->_prev;
			node* next = pos._pnode->_next;

			delete pos._pnode;
			prev->_next = next;
			next->_prev = prev;
			//删除完成之後，疊代器指針指向下一個位置，故傳回iterator(next)
			return iterator(next);//傳回下一個位置疊代器
		}

2.4.5 swap

STL之list介紹及實作（list接口、模拟實作list）1 什麼是list？2 list原型測試與實作3 list疊代器失效附贈思考

2.4.6 resize

接口測試：

（模拟實作參考vector）

STL之list介紹及實作（list接口、模拟實作list）1 什麼是list？2 list原型測試與實作3 list疊代器失效附贈思考

2.4.7 clear

clear接口測試：

STL之list介紹及實作（list接口、模拟實作list）1 什麼是list？2 list原型測試與實作3 list疊代器失效附贈思考

模拟實作clear:

STL之list介紹及實作（list接口、模拟實作list）1 什麼是list？2 list原型測試與實作3 list疊代器失效附贈思考

2.5 list 疊代器補充

上文中已經有了list的iterator，并能實作end，begin等操作。下面分析list疊代器必須有的幾種能力：

有能力指向list的節點，并有能力進行正确的遞增、遞減、取值、成員存取等操作；

下面實作了：

operator*
operator->
operator++(前置++，後置++)
operator–（前置–，後置–）
operator==
operator!=

參考代碼：

//讀者看到此處，肯定有所收獲，那麼思考下面這個模闆定義語句作用？？？
	template<class T, class Ref, class Ptr>
	struct _list_iterartor
	{
		typedef _list_node<T> node;
		typedef _list_iterartor<T, Ref, Ptr> self;
		node* _pnode;//疊代器内部必有一個普通指針，指向list的節點

		//疊代器
		_list_iterartor(node* pnode=nullptr)
			:_pnode(pnode)
		{}

		//const 疊代器
		_list_iterartor(const self& l)
			:_pnode(l._pnode)
		{}

		//T& operator*()
		Ref operator*()
		{
			return _pnode->_val;
		}

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

		bool operator!=(const self& s) const
		{
			return _pnode != s._pnode;
		}

		bool operator==(const self& s) const
		{
			return _pnode == s._pnode;
		}

		// ++it -> it.operator++(&it)
		self& operator++()
		{
			_pnode = _pnode->_next;
			return *this;
		}

		// it++ -> it.operator++(&it, 0)
		self operator++(int)
		{
			self tmp(*this);
			_pnode = _pnode->_next;
			return tmp;
		}

		self& operator--()
		{
			_pnode = _pnode->_prev;
			return *this;
		}

		self operator--(int)
		{
			self tmp(*this);
			_pnode = _pnode->_prev;
			return tmp;
		}
	};

3 list疊代器失效

list疊代器失效，隻會發生在erase函數中，不會發生在insert等操作。即插入才做不會導緻list疊代器失效，隻有在删除時才會失效。（并且失效的隻是指向被删除節點的疊代器，其他疊代器不會受影響）。

下面一圖看懂list疊代器失效：

STL之list介紹及實作（list接口、模拟實作list）1 什麼是list？2 list原型測試與實作3 list疊代器失效附贈思考

其實，疊代器失效無非就是其指針出現了問題，是以我們操作時，必須了解指針在什麼位置，起什麼作用，這樣才會避免疊代器失效發生。

附贈思考

上文中給出了一個問題：

//讀者看到此處，肯定有所收獲，那麼思考下面這個模闆定義語句作用？？？

為甚需要三個(class T, class Ref, class Ptr)？？？

template<class T, class Ref, class Ptr>

struct _list_iterartor

{

typedef _list_node node;

typedef _list_iterartor<T, Ref, Ptr> self;

node* _pnode;//疊代器内部必有一個普通指針，指向list的節點

我摘取了部分，供讀者思考，分享。

參考文獻：

<<STL源碼剖析>>，侯捷

www.cplusplus.com list庫

文中圖檔來自www.cplusplus.com

STL之list介紹及實作（list接口、模拟實作list）1 什麼是list？2 list原型測試與實作3 list疊代器失效附贈思考

文章目錄

1 什麼是list？

1.1 模拟實作預備知識

2 list原型測試與實作

2.1 構造函數（拷貝構造，指派構造，析構）

2.2 疊代器

2.3 capacity

2.4 modifiers

2.4.1 assign

2.4.2 push_back/pop_back/push_front/pop_front

2.4.3 insert

2.4.4 erase

2.4.5 swap

2.4.6 resize

2.4.7 clear

2.5 list 疊代器補充

3 list疊代器失效

附贈思考

繼續閱讀

POJ 1284 Primitive Roots (歐拉函數&原根定理)

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

成員函數初始化清單

2021-08-13c++——類之操作符重載

swmm與lisflood-fp源碼如何一起編譯 CMake指令

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

線性表之順序表的實作

10年軟體測試工程師，隻剩下這點感悟了（初級測試工程師必看）

面試題解析：你接口測試是怎麼做的？

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述

Linux裝置模型（中）之上層容器