順序容器 — heap · STL源碼分析

heap不屬于STL容器，它扮演者priority queue的助手。heap是一種完全二叉樹，可由數組來實現，但heap需要動態改變大小，所以最終選擇了vector作為底層容器。STL默認提供最大堆。題外話：分析heap的源碼就能清楚的理解堆這種數據結構的例程，而STL庫代碼的質量又很高，所以看堆的代碼，STL源碼是一個很好的選擇。為了滿足完全二叉樹的性質，新插入的元素一定最后一個葉子節點，也就是容器尾端，再然后再進行上濾操作，讓新元素找到正確的位置。以push_heap為例： ~~~ template <class RandomAccessIterator> // 新元素已插入容器尾部 inline void push_heap(RandomAccessIterator first, RandomAccessIterator last) { __push_heap_aux(first, last, distance_type(first), value_type(first)); } ~~~ 這個函數已經假設新插入元素已經位于vector的尾端，所以last指向新元素之后的一個位置。distance_type和value_type都是通過特性萃取機（iterator_traits）提取迭代器的相應類型：difference_type和value_type。提取過程如下： ~~~ template <class Iterator> inline typename iterator_traits<Iterator>::difference_type* distance_type(const Iterator&) { // 決定迭代器difference_type return static_cast<typename iterator_traits<Iterator>::difference_type*>(0); } template <class Iterator> inline typename iterator_traits<Iterator>::value_type* value_type(const Iterator&) { // 決定迭代器value_type return static_cast<typename iterator_traits<Iterator>::value_type*>(0); } ~~~ 注意，這里使用了static_cast把0進行了轉換，由于我們是需要迭代器所內嵌的類型，而不關心具體值，所以用0來代替是OK的。 push_heap內部調用函數__push_heap_aux，代碼如下： ~~~ 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))); // 新插入元素值 } ~~~ 最后兩個參數只有類型名，沒有參數名，印證了前面的說法。這個函數內部又調用了一個__push_heap函數，這個函數做了實際的上濾操作。在看__push_heap的源碼之前，先分析一下它的四個參數： - first：迭代器，指向容器開頭。 - Distance((last - first) - 1)：last - first - 1是新插入元素的下標值，這里用了一個C風格的類型轉換，符合泛型思想。 - Distance(0)：根元素的下標值，同樣進行了類型轉換。 - T(*(last - 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) { // value為新插入元素值 *(first + holeIndex) = *(first + parent); holeIndex = parent; // 上移 parent = (holeIndex - 1) / 2; // 上移 } *(first + holeIndex) = value; } ~~~ SGI STL的heap，元素是從vector的下標0開始排的，知道了這一點，看這段代碼就很輕松了。參考：《STL源碼剖析》 P172.