STL源碼剖析 筆記之四 序列式容器

第四章 序列式容器 所謂序列式容器，其中的元素都可序，但未必有序。 C++語言本身提供了一個序列式容器array。 序列式容器:    array        C++内建                vector

                    heap    以算法呈現(xxx_heap)

                        priority-queue

                list

                slist        非标準

                deque

                    stack    配接器

                    queue    配接器

以下隻介紹各種容器的理論技術，具體的代碼請檢視SGI STL源碼。 1.vector    包含于<vertor>，實作于<stl_vector.h> ①vector概述 vector的資料安排和操作方式跟array相似，唯一差别在于空間運用的靈活性。 array是靜态空間，一旦配置了就不能改變,如需改變，需使用者自己實作細節。 vector是動态空間，随着元素的加入，它的内部機制會自行擴充空間以容納新元素。

vector的實作技術，關鍵在于其對大小的控制以及重新配置時的資料移動效率。 "配置新空間/資料移動/釋放舊空間"，時間成本很高，應該加入未雨綢缪的考慮。 ②vecotr定義摘要 <stl_vector.h> ③vecotr疊代器 vector維護的是一個連續線性空間，是以不論其元素類型為何，普通指針都可以作為vector的疊代器而滿足所有條件。 vector支援随機存取，是以vector提供的是random access iterators。 ④vector資料結構 vector所采用的資料結構非常簡單:線性連續空間。它以兩個疊代器start和finish分别指向配置得來的連續空間中目前已被使用的範圍，并以疊代器end_of_storage指向整塊連續空間(含備用空間)的尾端。 為了降低空間配置時的速度成本，vector實際配置的大小可能比用戶端需求更大，以備将來可能的擴充。這便是容量的概念。一旦容量等于大小，便是滿載，再增加新元素，整個vector就要另覓新所。 運用start、finish、end_of_storage三個疊代器，可以輕易的提供首尾辨別、大小、容量、空容器判斷、下标運算符、最前/後端元素等。 vector預設使用alloc作為空間配置器，并據此另外定義了data_allocator，以便以元素大小為配置機關。 ⑤vector構造與記憶體管理 constructor push_back 會根據第一個模闆參數來決定調用構造還是fill_n。 push_back的時候會判斷是否還有備用空間，沒有則重新申請空間(2倍)。 ⑥vector元素操作 pop_back    拿掉尾部元素并調整大小 erase        清除區段内元素或清除單個元素 clear    = erase(begin(),end());     清除所有元素 insert    插入n個節點到position節點之前 2.list       包含于<list>，實作于<stl_list.h> ①list概述 list的好處是每次插入或删除一個元素，就配置或釋放一個元素空間。list對空間的利用絕對精準，一點也不浪費。 而且對于任何位置的元素插入或删除，list永遠是常數時間。 list和vector,什麼時機下最适合使用哪種容器，必須是元素的數量，構造複雜度，元素存取行為的特性而定。 ②list結點 list本身與list結點是不同的結構，要分開設計。list是雙向連結清單。 ③list疊代器 list的結點不保證在記憶體中連續，是以不能用普通指針作為疊代器。 list疊代器必須有能力指向list的結點，并有能力進行正确的遞增++、遞減--、取值*、成員存取->等操作。 list是個雙向連結清單，疊代器必須具備前移後移能力，是以list提供的是Bidirectional Iterators。 ④list資料結構 SGI list是一個環狀雙向連結清單，是以它隻需一個指針，便可以完整的表現整個連結清單。 讓list中的node指針，指向刻意置于尾端的一個空白結點，node便符合STL前開後閉的要求，成為last疊代器。 ⑤list構造與記憶體管理 constructor push_back    内部調用insert insert        有n個重載 list預設使用alloc作為空間配置器，并據此另外定義了list_node_allocator，以便以元素大小為配置機關。 ⑥list元素操作 push_front/ push_back/ erase/ pop_front/ pop_back/ clear/ remove/ unique/ splice(接合)/ merge/ reverse/ sort list内部提供一個所謂遷移操作(transfer)，将某連續範圍内的元素遷移到某個特定位置之前。 3.deque       包含于<deque>，實作于<stl_ deque .h> ①deque概述 vector是單向開口的連續線性空間，deque是一種雙向開口的連續線性空間。 deque允許常數時間内進行元素的插入和移除操作；deque沒有容器的概念，它是動态的以分段連續空間組合而成。不會出現向vector那樣因空間不足而配置複制釋放的動作。 對deque的排序，為了最高效率，講deque完整複制到一個vector，排序後，複制回deque。 ②deque中控器 deque是由一段段的定量連續空間構成，一旦有必要在deque的前端或尾端增加新空間，便配置一段定量連續空間，串接在整個deque頭端或尾端。 deque的最大任務，便是在這些分段的定量連續空間上，維護其整體連續的假象，并提供随機存取接口。 避開了重新配置複制釋放的輪回，代價是複雜的疊代器結構。 deque采用一塊所謂map作為主要。這裡的map是一小塊連續空間，其中每個結點都是指針，指向另一塊稱為緩沖區的連續線性空間。緩沖區才是deque的儲存空間主體。預設值0表示将使用512Bytes緩沖區。 ③deque疊代器 deque是分段連續空間，維持其整體連續假象的任務，落在了疊代器的operator++和 operator--身上。 __deque_iterator未繼承自std::iterator。 __deque_iterator中的四個指針分别表示:   T* cur;    目前緩沖區指針   T* first;    該緩沖區的頭端   T* last;    該緩沖區的尾端   map_pointer node;    該緩沖區在map中的位置。 各種指針運算，加、減、前進、後退，都需注意:一旦行進到緩沖區邊緣，可能需要調用set_node()跳轉緩沖區。 ④deque資料結構 deque除了維護一個指向map的指針外，也維護start、finish兩個疊代器，分别指向第一緩沖區的第一進制素和最後緩沖區的最後一個元素。同時也記住目前map的大小。 ⑤deque構造與記憶體管理 ctor push_back        push_back_aux push_front       push_front_aux deque自行定義了兩個專屬的空間配置器data_allocator和map_allocator。 map的重新整治reallocate，當map滿載之後發生(因為map是不能動态增長的), 由reserve_map_at_back()和 reserve_map_at_front()判斷， reallocate_map執行。 ⑥deque 元素操作 pop_back\pop_front\clear(清除整個deque,保有一個緩沖區)\erase\insert 4.stack     包含于<stack>，實作于<stl_ stack .h> ①stack概述 stack是一種FILO的資料結構。隻有一個出口。允許增加、移除、取得頂部元素。不允許有周遊行為。 ②stack定義完整清單 <stl_ stack .h> SGI STL預設情況下用deque作為底層容器。更改某物接口，形成另一種風貌。容器配接器。 ③stack沒有疊代器 stack所有元素都必須符合先進後出條件，隻有頂端的元素才有機會被外界取用，不提供走訪功能。 ④以list作為stack的底層容器 list也是一種雙向開口的資料結構，若以list為底部結構并封閉其頭端開口也可以輕易實作stack. 5.queue     包含于<queue>，實作于<stl_ queue .h> ①queue概述 queue 是一種FIFO的資料結構。有兩個出口。允許增加、移除、取得頂部元素、從底部加入元素。不允許有周遊行為。 ②queue 定義完整清單 <stl_ queue .h> ③queue沒有疊代器 ④以list作為queue的底層容器 6.heap   隐式表述，實作于< stl_heap.h> ①heap概述 heap并不屬于STL容器元件，它扮演priority queue的助手。 priority queue允許使用者以任何次序将任何元素推入容器，但取出時一定是以優先權最高的元素開始取。 采用二叉堆(binary heap)作為底層機制。 binary heap是一種complete binary tree完全二叉樹。 實作:完全二叉樹的特點是整棵樹内沒有任何結點漏洞，這樣我們用線性存儲方式vector來儲存所有結點。 将第0個元素保留，那麼當完全二叉樹的某個結點位于i處時候，其左子結點位于2i處，右子結點位于2i+1處，父結點位于i/2處。 這樣就可以用vector輕易實作完全二叉樹，這種以線性空間表示樹的方式，稱為隐式表述法。 其實這種方式可以反過來看，線性存儲空間裡面，是把樹以層序周遊的方式存儲到vector中。 當然SGI STL的heap沒采用這種技巧，其計算左右孩子和父結點的方式另有不同。回頭我們研究源碼。 heap分為max-heap和min-heap,差別是排序方式，從大到小和從小到大。 max-heap的要求，第一是完全二叉樹，第二父結點總是大于等于子節點。 min-heap的要求，第一是完全二叉樹，第二父結點總是小于等于子節點。 ②heap算法 push_heap 首先要将新加入的元素放到最下一層作為葉節點，并填補從左到右的第一個空格，也就是vector的end處。 然後為了滿足父結點總是大于等于子節點這一條件，與于父結點比較，如果大于父結點，就交換，直到滿足條件。 pop_heap 因為pop的總是最大值(max-heap)，而最大值肯定是根節點。 是以做法是把根節點與最後一個結點交換，然後再調整新的根節點的位置。 pop_heap不會移除結點，隻是調整到vector的最末。 sort_heap 采用pop_heap，每次pop_heap後最大值肯定在vector的最後。 是以一直調用pop_heap直到隻剩下一個元素。當然之後此vector就不是一個有效heap了。 make_heap 将現有資料轉化為一個heap。依照之前提到的完全二叉樹的隐式表述。 ③heap沒有疊代器 heap的所有元素都必須遵循特别的(完全二叉樹)排列規則，是以heap不提供周遊功能，也不提供疊代器。 7.priority_queue    包含于<queue>,實作于<stl_queue.h> ① priority_queue概述 priority_queue是一個擁有權值概念的queue,它允許加入新元素，移除舊元素，審視元素值。 由于這是一個queue，是以隻允許在低端加入元素，從頂端取出元素。 預設情況下 priority_queue是用一個max-heap完成，max-heap是一個以vector表現的complete binary tree。 ② priority_queue定義完整清單 priority_queue完全以底部容器為根據，再加上heap處理規則，是以實作非常簡單。 預設情況下以vector作為底部容器。 ③ priority_queue沒有疊代器 priority_queue的所有元素，進出都有一定的規則，隻有頂端的元素才有機會被外界取用。 priority_queue 不提供周遊功能，也不提供疊代器。 8.slist    單向連結清單, 包含于<slist>,實作于<stl_slist.h> ①slist概述 slist并不在标準規格之内。 slist與list的主要差别在于，slist的疊代器屬于單向的Forward iterator，list的疊代器屬于雙向的Bidirectional Iterator。共同特色在于，插入移除接合操作不會造成原有的疊代器失效。 STL的習慣是插入操作會将元素插入于指定位置之前，但是slist不能反向定位。于是提供了insert_after()和erase_after()，基于同樣的效率考慮，slist不提供push_back(),隻提供push_front()。 ②slist結點 slist的結點設計比list要複雜，運用了繼承關系: struct __slist_node_base {   __slist_node_base* next; }; template <class T> struct __slist_node : public __slist_node_base {   T data; }; ③slist疊代器 同樣采用繼承關系: struct __slist_iterator_base {...};//重載了== 和!=操作符 template <class T, class Ref, class Ptr> struct __slist_iterator : public __slist_iterator_base {...};//重載了前置++和後置++操作符。 ④slist資料結構 template <class T, class Alloc = alloc> class slist {   ... private:   list_node_base head;//頭結點   ... }; 結點的插入push_front(): 構造結點，create_node(); 把結點添加到slist中，__slist_make_link(); 結點的移除pop_front(): 移除結點 head->next = head->next->next; 銷毀結點,destroy_node() ⑤slist元素操作 begin() end()//傳回是iterator(0),為了實作前閉後開[first,last)的規則。 push_front() pop_front() insert() insert_after() ...