STL組成

• 容器
• 配接器
• 算法
• 迭代器
• 仿函數(shù)
• 空間配置器

主要講解容器和算法，不講解其他的

容器分類

• 序列式容器:vector list deque stack queue heap priority_quue slist (queue和stack是配接器)
• 關(guān)聯(lián)式容器:set map multiset multimap hash_set hash_map hash_multiset hash_multimap

vector

• 連續(xù)空間
• vector 動(dòng)態(tài)空間
• array 靜態(tài)空間
• 動(dòng)態(tài)空間是以原大小的兩倍進(jìn)行擴(kuò)充，重新分配時(shí)，迭代器會(huì)失效

主要操作有push_back pop_back erase clear insert size empty

初始化

#include <vector>

int main(){
    // size=0的vector
    vector<int> a;
    // 初始化size，但元素為默認(rèn)值
    vector<int> b(10);
    // 初始化size并設(shè)置默認(rèn)值
    vector<int> b(10,2);
}

list

• 非連續(xù)空間
• STL的list是一個(gè)環(huán)狀雙向鏈表
• 插入和刪除操作都不會(huì)造成原迭代器失效

主要操作有:push_front push_back erase pop_front pop_back clear remove unique splice merge reverse sort size empty

內(nèi)部定義了一個(gè)transfer函數(shù)，為splice sort merge等操作提供基礎(chǔ)。功能是將連續(xù)范圍內(nèi)的元素遷移到某個(gè)特定位置之前

deque

• 雙向開口的連續(xù)空間
• 兩端插入和刪除操作都是
• 分段連續(xù)空間組合而成，避免了重新配置、復(fù)制、釋放的輪回
• 對(duì)deque的排序只能復(fù)制到一個(gè)vector 然后根據(jù)sort算法，再復(fù)制回deque

原理

• 用一個(gè)小塊連續(xù)空間作為主控
• 每個(gè)元素都是指針，指向另一個(gè)大的連續(xù)線性空間，稱為緩沖區(qū)
• 緩沖區(qū)才是deque存儲(chǔ)空間的主題

deque中控器、緩沖區(qū)、迭代器的相互關(guān)系

主要操作有:push_front push_back pop_front pop_back clear erase insert size empty

stack

• 先進(jìn)后出的結(jié)構(gòu)，只有一個(gè)出口
• STL使用deque作為底層源碼進(jìn)行實(shí)現(xiàn)
• 沒有迭代器
• 也有使用它list作為底層源碼進(jìn)行實(shí)現(xiàn)

主要操作有:empty size back push_back pop_back

queue

• 先進(jìn)先出結(jié)構(gòu)，有兩個(gè)出口
• STL以deque作為底層源碼進(jìn)行實(shí)現(xiàn)
• 沒有迭代器
• 也有使用list作為底層源碼進(jìn)行實(shí)現(xiàn)

主要操作有:empty size front back push pop

heap

• 不歸屬于STL容器組件，但是是priority_queue的底層實(shí)現(xiàn)
• 二叉堆是一個(gè)完全二叉樹，除葉節(jié)點(diǎn)外，都是填滿的，且葉節(jié)點(diǎn)左右不得有空隙
• 可以使用array存儲(chǔ)所有節(jié)點(diǎn)
• 某個(gè)節(jié)點(diǎn)位于i處時(shí)，左子節(jié)點(diǎn)位于2i處，右子節(jié)點(diǎn)位于2i+1處，父節(jié)點(diǎn)在i/2處
• 分為最大堆和最小堆
• STL提供的是最大堆
• heap不提供遍歷功能，也不提供迭代器

原理

• push操作：先插入到vector尾部,然后進(jìn)行上溯：新節(jié)點(diǎn)與父節(jié)點(diǎn)比較，如果比父節(jié)點(diǎn)大，父子調(diào)換位置
• pop操作: 取走根節(jié)點(diǎn)后，把最下層最右邊節(jié)點(diǎn)進(jìn)行下溯:空間節(jié)點(diǎn)與較大子節(jié)點(diǎn)調(diào)換位置，直到葉節(jié)點(diǎn)為止

priority_queue

• 優(yōu)先隊(duì)列，根據(jù)權(quán)值進(jìn)行排序，默認(rèn)情況是一個(gè)最大堆
• 以heap為源碼作為底層實(shí)現(xiàn)
• 沒有迭代器

主要操作有:size empty top push

slist

• 雙向列表
• 不在標(biāo)準(zhǔn)規(guī)格之內(nèi)，有些STL不提供
• 與list相比沒有回溯節(jié)點(diǎn)的操作
• 提供了insert_after和erase_after兩個(gè)操作

紅黑樹

• 是容器，但是不開放使用，是map set的底層實(shí)現(xiàn)
• 時(shí)間復(fù)雜度是
• 是個(gè)二叉搜索樹，同時(shí)滿足下列規(guī)則
• 1.每個(gè)節(jié)點(diǎn)不是紅色就是黑色
• 2.根節(jié)點(diǎn)是黑色
• 3.如果節(jié)點(diǎn)為紅色，子節(jié)點(diǎn)必須是黑色
• 4.任一節(jié)點(diǎn)至NULL的任何路徑，所含之黑節(jié)點(diǎn)數(shù)必須相同

根據(jù)規(guī)則4，新增節(jié)點(diǎn)必須是紅色，根據(jù)規(guī)則3，新增節(jié)點(diǎn)的父節(jié)點(diǎn)必須是黑色，如果不滿足，必須調(diào)整紅黑樹

主要提供:insert_unique insert_equal和find三個(gè)方法。insert_unique不允許重復(fù)，insert_equal每次插入都會(huì)成功，find遵循二叉搜索樹的性質(zhì)(左 < 根 < 右)

set

• 所有元素的鍵值都會(huì)自動(dòng)被排序
• 不允許有兩個(gè)相同的鍵值
• 不允許修改set的鍵值
• 新增或刪除時(shí)，迭代器不會(huì)失效
• 以紅黑樹作為底層實(shí)現(xiàn)
• 擁有交、并、差集合運(yùn)算

主要提供的操作有:insert erase size clear find empty

map

• 元素會(huì)根據(jù)鍵值進(jìn)行自動(dòng)排序
• 所有元素都是pair
• 不允許有兩個(gè)相同的鍵
• 不可以修改鍵，可以修改值
• 新增和刪除操作，迭代器不會(huì)失效

主要提供的操作有：insert erase size empty clear find 下標(biāo)操作

multiset

• 和set完全相同，唯一差別在于允許鍵值重復(fù)

multimap

• 和map完全相同，唯一差別在于允許鍵值重復(fù)

hashtable

• 常數(shù)平均時(shí)間的復(fù)雜度
• 需要用散列函數(shù)將一個(gè)元素映射為一個(gè)大小可接受的索引
• 如果映射索引有沖突，需要通過一些列辦法解決沖突，如線性探測(cè)，二次探測(cè)，開鏈等做法
• hashtable采用開鏈方法解決沖突

線性探測(cè)

有沖突，直接循環(huán)往下一一尋找，直到一個(gè)可用的空間為止；刪除時(shí)采用惰性刪除，實(shí)際刪除需要重新整理時(shí)再進(jìn)行

問題：平均插入成本的成長幅度，遠(yuǎn)高于負(fù)載系數(shù)的成長幅度（主集團(tuán)現(xiàn)象）

二次探測(cè)

主要用來解決主集團(tuán)問題；如果有沖突，嘗試

如果表格大小為質(zhì)數(shù)，且永遠(yuǎn)保持負(fù)載系數(shù)在0.5以下(超過0.5重新整理)，每次插入不超過2次探測(cè)

問題：計(jì)算出來的位置相同，則插入的位置也相同，會(huì)造成浪費(fèi)（次集團(tuán)現(xiàn)象）

解決辦法有：復(fù)式散列等

開鏈

每個(gè)表格元素維護(hù)一個(gè)list，沖突時(shí)，在list上插入、搜尋等操作

hash_set

• 以hashtable為底層實(shí)現(xiàn)機(jī)制
• 沒有自動(dòng)排序的功能
• 使用和性質(zhì)與set完全一樣

hash_multiset

• 與multiset完全一樣，沒有排序功能

hash_map

• 以hashtable為底層實(shí)現(xiàn)機(jī)制
• 沒有自動(dòng)排序功能
• 使用性質(zhì)和map完全一樣

hash_multimap

• 與multimap完全一樣，沒有排序功能

算法

包含的一些主要算法有: binary_search copy find find_if find_first_of max max_element lower_bound min min_element reverse rotate search search_n set_difference set_intersection set_union sort stable_sort swap upper_bound make_heap pop_heap push_heap sort_heap

算法的操作一般都是迭代器

參考文獻(xiàn)

STL源碼剖析