開發成長之路（7）-- C++從入門到開發（C++知名庫：STL入門·容器（二））

deque

vector是單向開口的連續線性空間，deque則是一種雙向開口的連續線性空間，
所謂雙向開口，也就是說可以在頭尾兩端進行插入和洗掉操作，

vector當然也可以做頭部操作，但是其頭部操作效率奇差！！！
無法被接受，
（這點以前居然都沒有發現！！！）

deque沒有所謂容量的觀念，因為它是動態的以分段連續空間組合而成，隨時可以增加一段新的空間并鏈接起來，因此，deque沒有必要提供所謂的空間保留功能，

但是呢，為什么我們更多的選用vector而非deque呢？因為它的指標實在是太麻煩了，我們后面就知道了，

除非必要，我們應盡可能的選擇使用vector而非deque，對deque進行的排序操作，為了最高效率，可以將deque完整的復制到一個vector身上，將vector排序后，再復制回deque，

不要被事務的表面現象鎖迷惑，你看它是分段連續線性空間，就以為它是vector和list的結合體，取長補短？其實不然，
為了維持整體連續的假象，資料結構的設計及迭代器前進后退等操作都頗為繁瑣，

deque的中控器

deque采用一塊所謂的map映射，來看吧：

template <class T,class Alloc = alloc,size_t BufSiz = 0>
class deque{
public:
	typedef T value_type;
	typedef value_type* pointer;
	···
protected:
	//元素的指標的指標
	typedef pointer* map_pointer;

protected:
	map_pointer map;	
	//指向map，map是塊連續空間，其內的每個元素都是一個指標，指向一塊緩沖區
	
	size_type map_size;
	//map內可容納多少指標
}

看得我尷尬癥都犯了，

此外，deque還維護start、finish兩個迭代器，分別指向第一緩沖區的第一個元素和最后緩沖區的最后一個元素（的下一個位置），
此外，它當然也必須記住目前map的大小，一旦map的空間不足，必須要重新配置一個更大的map，

stack – 堆疊

什么是堆疊？怎么說呢，我覺得我真應該先寫資料結構專欄，失策失策！！！
堆疊是一種先進后出的資料結構，它只有一個介面，
只能從一端加入元素，從那一端移除元素，所以并不被允許有其他方法來存取元素，
換言之，stack不允許有遍歷行為，

將元素推入stack的方式稱為push，將元素退出stack的操作稱為pop，

以某種既有容器作為底部結構，將其介面改變，使之符合“先進后出”的特性，形成一個stack，是很容易做到的，

deque是雙向開口資料結構，若以deque為底部結構并封閉其頭端開口，
便輕而易舉形成了一個stack、
（不知道為什么，我覺得好糟糕哦，vector是不能做嗎？）

還是等我過兩篇寫資料結構的時候再說吧，

除deque之外，list也是雙向開口的資料結構，以list為底的stack被稱作鏈堆疊，

嘿我就挺納悶兒，為什么就非要雙向開口的資料結構？？？

queue – 佇列

佇列，是一種先進先出結構，只能從一端加入元素，從另一端移除元素，所以并不被允許有其他方法來存取元素，
換言之，queue不允許有遍歷行為，

那這個跟上面的stack其實沒多大區別，只不過一個是后進先出，一個是先進先出的罷了，那為什么也要雙向開口的資料結構呢？

heap是什么

heap并不屬于STL容器組件，它是個“幕后白手”，扮演priority queue的助手，

顧名思義，那個queue允許用戶以任何次序插入資料，但是在插入的時候會根據優先級進行排序，以保證取出的時候是按照優先級排序的，

如果以List作為這個優先級佇列的底層機制，那么排序將會很麻煩，如果以二叉搜索樹的話，未免大材小用了，
而難度夾在中間的binary heap便是不二人選了，

所謂binary heap,就是一種完全二叉樹，整棵樹除了底層節點外，都是填滿的，從左至右又不得又間隙，

蒼白無力的文字啊，來看張圖實在：

簡單明了吧，可以用想象下面有一個陣列來存盤所有節點，以樹根節點作為陣列的[0]位置，可以發現，任何一個節點 [i] 的左子節點必位于 [2i] 處，其右子節點必位于 [2i+1] 處，
而任何一個節點 [k]，其父節點必位于 [k/2] 處，

通過這簡單的規則，咱就種了一棵樹，完全二叉樹，
而這顆二叉樹需要能動態的增加節點，所以采用vector作為這棵樹的底層土壤是個理想的選擇，

根據元素排列方式，heap可以分為max-heap和min-heap，STL供應的是max-heap,最大值在頭結點，

heap演算法

push_heap演算法（尾端插入元素）
本來是自己畫了圖，但是理解了書中的圖之后，發現他的圖更有一番風味，

原先我也疑惑于為何同一級中左邊的節點會比右邊節點大，后來我想明白了，
在插入程序中，這個順序被打亂是難以避免的，況且這個排序于取出資料并無影響，所以沒必要在欄位外作業對樹的底層做那么精細的排序，

如果還是不理解，先看下去，慢慢的就會茅塞頓開，

在尾部插入時，總是將節點插入到最底層的最右節點，不管你要插入的資料右多大，見上圖第一個步驟，
插入之后執行上溯操作，將新節點拿來與父節點進行比較，如果“青出于藍勝于藍”，那么將父子節點互換位置，見上圖第二個步驟，
之后持續執行上一個步驟，直到不再互換位置，見上圖三、四個步驟，
至于下面被打亂的順序，不用擔心，亂中有序，

正是由于這波操作，使得同一級會出現左邊的節點比右邊的大的情況，

下面來看一下演算法的實作細節：

//該函式接受兩個迭代器，用來表現一個heap底部容器的頭尾，并且新元素已經插入到底部容器的最尾端，

template <class RandomAccessIterator>
inline void push_heap(RandomAccessIterator first,RandomAccessIterator last)
{
	__push_heap_aux(first,last,distance_type(first),value_type(first));/*這倆type在上一篇提到了，不知道也就算了吧，畢竟上一篇也不短*/
}

template <class RandomAccessIterator,class Distance,class T>
inline void __push_heap_aux(RandomAccessIterator first,RandomAccessIterator last,Distance*,T*)
{
	__push_heap(first,Distance((last-first)-1),Distance(0),T(*(last - 1)));	//(last-first)-1，容器最尾端
}

template <class RandomAccessIterator,class Distance,class T>
void __push_heap(RandomAccessIterator first,Distance holeIndex,Distance topIndex,T value)
{
	Distance parent = (holeIndex - 1)/2;	//找出父節點
	while(holeIndex > topIndex && *(first+parent)<value)	//尚未到達頂端，且父節點小于新值，這個回圈將父值不斷下調
	{
		*(first + holeIndex) = *(first + parent);	//令新值為父
		holeIndex = parent;	//調節洞號，向上提升至父節點
		parent = (holeIndex -1)/2;	//新洞的父節點
	}
	*(first + holeIndex) = value;	//令洞值為新值，完成插入操作
}

看下來，果然會茅舍頓開吧，

pop_heap演算法（頭部插入元素）
看完上面的插入，可能會有人覺得這樣打亂順序的話取出會有問題，其實會有嗎？不知道，看下去，

還是用書上的圖啊，
取出元素時，首先將1根節點拿下來，留下一個洞洞，見上圖第一步到第二步，
還要將當前樹的最后一個節點拿下來，并將根節點放到尾節點在容器中的位置，見上圖步驟二，
接下來將尾節點和原根節點的兩個子節點比較大小，將大的那個推上根節點，見上圖步驟三，同樣留下一個洞洞，
回圈這個“向下流放”的程序，直到原尾結點插入樹中或者到了最底層，見上圖步驟四，

看懂了這個圖之后我們來看演算法的實作細節：

template <class RandomAccessIterator>
inline void pop_heap(RandomAccessIterator first,RandomAccessIterator last)
{
	__pop_heap_aux(first,last,value_type(first));
}

template <class RandomAccessIterator,class T>
inline void __pop_heap_aux(RandomAccessIterator first,RandomAccessIterator last,Distance*,T*)
{
	__pop_heap(first,last-1,last-1,T(*(last - 1)),diatance_type(first));
}

template <class RandomAccessIterator,class Distance,class T>
void __push_heap(RandomAccessIterator first,RandomAccessIterator last,RandomAccessIterator result,T value,Distance*)
{
	*result = *first;	//設定尾值為首值，客端稍后可以pop_back()將值取出
	__adjust_heap(first,Distance(0),Distance(last - first),value);
}

template <class RandomAccessIterator,class Distance,class T>
void __adjust_heap(RandomAccessIterator first,Distance holeIndex,Distance len,T value)
{
	Distance topIndex = holeIndex;
	Distance secondChild = 2 * 	holeIndex+2;	//右節點
	while(secondChild < len)
	{
		if(*(first + secondChild) < *(first +(secondChild -1)))
			secondChild --;
		*(first + holeIndex) = *(first + secondChild);
		holeIndex = secondChild;

		secondChild = 2*(secondChild+1);	//找出新洞節點的有子節點
	}
	if(secondChild == len)	//沒有右子節點了
	{
		*(first + holeIndex) = *(first + secondChild -1);	//令左子值為鍵值
		holeIndex = secondChild - 1;	//再把洞的位置下移
	}
	__push_heap(first,holeIndex,topIndex,value);
}

sort_heap演算法（思想簡介）
不斷對heap進行pop操作，便可達到排序效果，
這個圖可以根據上面兩張圖自行腦補，演算法也可以自行腦補，

heap迭代器
嘿嘿，那當然是沒有迭代器了，所有元素都必須遵循特別的排列規則，又不提供遍歷功能，要什么迭代器，

make_heap （制造heap）
這個演算法就是用來將現有的一段資料轉化成一個heap，

思想不多說，直接看代碼：

template<class RandomAccessIterator>
template <class RandomAccessIterator>
inline void make_heap(RandomAccessIterator first,RandomAccessIterator last)
{
	__make_heap(first,last,distance_type(first),value_type(first));
}

//不允許指定比較方法
template <class RandomAccessIterator,class Distance,class T>
void __make_heap(RandomAccessIterator first,RandomAccessIterator last,Distance*,T*)
{
	if(last - first <2)	return;
	Distance len = last - first;
	Distance parent = (len - 1)/2;	//找出臨時父節點
	while(true)	//尚未到達頂端，且父節點小于新值，這個回圈將父值不斷下調
	{
		__adjust_heap(first,parent,len,T(*(first+parent)));
		if(parent == 0)	return;	
		parent--;
	}
}