首頁資訊 STL源碼剖析學(xué)習記錄(二)

STL源碼剖析學(xué)習記錄(二)

來源：泰然健康網(wǎng) 時間：2025年07月25日 00:33

第五章關(guān)聯(lián)式容器

1、紅黑樹

operation: 左旋，右旋，變色， header實現(xiàn)技巧，平均查找時間復(fù)雜度nlog(n)

set/map/multiset/multimap

采用RB-tree紅黑樹實現(xiàn)；

刪除/插入新元素，不會導(dǎo)致迭代器失效；

set/map不允許重復(fù)，multiset/multimap允許重復(fù)

3）hash_table

operation: hash function, vector<slist<key>>, vector作為buckets的容器。rehash遵循質(zhì)數(shù)擴容

線性探測（存在primary clustering問題）、二次探測（存在secondary clustering問題）、開鏈法；

維護一個指針數(shù)組，每一個指針代表一個鏈表（具有相同的hash值）；

在插入數(shù)據(jù)時，會插入到同一個hash桶中的相同鍵值的數(shù)據(jù)的next 指向

當出現(xiàn)hashtable中元素個數(shù)達到閾值時（SGI是數(shù)組大小小于總元素個數(shù)時擴容），進行擴容（擴容大小為下一個質(zhì)數(shù)），并將原來的數(shù)據(jù)rehash到新的表中（原來同一個桶中的數(shù)據(jù)，現(xiàn)在可能會hash到不同桶中，因此需要一個一個hash，這可能會導(dǎo)致同一個桶的數(shù)據(jù)出現(xiàn)翻轉(zhuǎn)現(xiàn)象）；

注意針對double, float等未提供的用戶需要自定義hash function

4）hash_set/hash_map/hash_multiset/hash_multimap

采用hash_table實現(xiàn)；

hash_set/hash_map不允許重復(fù)，hash_multiset/hash_multimap允許重復(fù)；

map/multimap/unordered_map/ unordered_ multimap

第六章算法

這章主要講了一些stl對容器值的一些操作，比如sum, replace, fill等，主要分為inplace改變?nèi)萜髦岛瞳@取容器值兩類

記錄下copy()的操作:

利用type traits和模板偏特化實現(xiàn) 對可以進行memmove的char*, wchar_t*類別進行最快的操作，對random_access_tag的類別進行對應(yīng)copy_d操作，對其他類別進行對應(yīng)的操作，已達到最優(yōu)效率