[[427784]]

大家好，我是梁唐。

今天我們繼續(xù)來(lái)聊C++的STL，今天來(lái)聊聊set。為了寫(xiě)這篇文章，老梁花了一早上的時(shí)間把網(wǎng)上大部分關(guān)于set的博文都看了一遍。

看完之后發(fā)現(xiàn)不出所料的千篇一律，上來(lái)就是說(shuō)怎么創(chuàng)建set，set里有哪些函數(shù)，標(biāo)準(zhǔn)的技術(shù)文檔。

這些東西對(duì)于老鳥(niǎo)來(lái)說(shuō)當(dāng)然沒(méi)問(wèn)題，瞬間掃一眼就能找到自己想要的，但是對(duì)于新手來(lái)說(shuō)估計(jì)看起來(lái)有些吃力。肯定一腦袋包，所以老梁另辟蹊徑，咱們先不羅列術(shù)語(yǔ)和api文檔，以記敘文的形式來(lái)說(shuō)說(shuō)它的前因后果、前世今生。

如果喜歡這種形式的文章，不妨給老梁點(diǎn)個(gè)贊，給老梁一點(diǎn)正反饋。

set是個(gè)啥?

如果大家學(xué)過(guò)幾門編程語(yǔ)言，會(huì)發(fā)現(xiàn)各大語(yǔ)言的特性雖然迥異，但是總有幾個(gè)東西反復(fù)出現(xiàn)刷存在感。它們?cè)诟鱾€(gè)語(yǔ)言當(dāng)中的名字雖然不太一樣，底層實(shí)現(xiàn)也不同，但是做的事情差不多。

在C++當(dāng)中，這幾個(gè)東西的名字叫做vector、set和map，它們有一個(gè)共同的名字叫做STL(標(biāo)準(zhǔn)模板庫(kù))容器。

估計(jì)不少同學(xué)看到容器這兩個(gè)字腦袋有點(diǎn)發(fā)蒙，會(huì)有一種我當(dāng)然知道容器是什么意思，但是我不知道你這里說(shuō)容器是什么意思的感覺(jué)。現(xiàn)實(shí)中的容器是用來(lái)存儲(chǔ)東西的器皿，在編程語(yǔ)言當(dāng)中，也是一樣，只不過(guò)存儲(chǔ)的不再是實(shí)際的物品而是抽象的變量。

那么問(wèn)題來(lái)了，同樣是容器，vector、set、map這些又有什么區(qū)別呢?前面的文章里說(shuō)過(guò)，vector類似于數(shù)組，可以以線性的形式存儲(chǔ)元素。而set、map和vector不同，它們不是線性的容器，而是關(guān)聯(lián)式的容器。

看到新的術(shù)語(yǔ)，估計(jì)又有同學(xué)要發(fā)蒙了，先別著急發(fā)蒙。其實(shí)我們可以大膽猜測(cè)一下，從字面理解，所謂關(guān)聯(lián)式說(shuō)白了也就是把兩個(gè)事物關(guān)聯(lián)起來(lái)。那么新的問(wèn)題又來(lái)了，這個(gè)關(guān)聯(lián)是什么?我們?cè)趺醋龅年P(guān)聯(lián)，又為什么要做關(guān)聯(lián)?

這幾個(gè)問(wèn)題估計(jì)連很多老鳥(niǎo)都能唬住。

要解釋清楚這個(gè)，就需要先來(lái)說(shuō)說(shuō)set的功能。我們從現(xiàn)象入手去逐漸理解本質(zhì)。

我們有了vector，可以順序地存儲(chǔ)數(shù)據(jù)，還可以隨心所欲地插入數(shù)據(jù)非常的方便，那么除了這些之外我們還需要什么呢?

當(dāng)擁有的數(shù)據(jù)多了之后，就會(huì)產(chǎn)生一個(gè)很自然的需求，就是查找數(shù)據(jù)。數(shù)據(jù)搜集存儲(chǔ)起來(lái)之后總是要拿來(lái)用的，既然要拿出來(lái)用，自然就需要查找。在查找這個(gè)需求面前，vector很不夠看，因?yàn)樗?dāng)中的數(shù)據(jù)都是線性排列的，排成一排，需要一個(gè)一個(gè)查找。數(shù)據(jù)少還行，如果數(shù)據(jù)多了，顯然忙不過(guò)來(lái)。

那怎樣查找才快呢?

得讓數(shù)據(jù)有順序，有了順序查找就快了。比如同樣是一行數(shù)，如果它們都是有序的，我們就可以通過(guò)二分法來(lái)查找了，那么復(fù)雜度就陡然地從提升到了。看起來(lái)好像只是數(shù)學(xué)公式上的一點(diǎn)微小變化，實(shí)際上這兩者之間的差距大的離譜，尤其是在海量數(shù)據(jù)的情況下。

18,446,744,073,709,551,615這個(gè)數(shù)據(jù)夠大嗎?表示成科學(xué)記數(shù)法是，比地球上的沙子都多。這么龐大的數(shù)據(jù)要是一個(gè)一個(gè)遍歷過(guò)來(lái)真得天荒地老，即使計(jì)算機(jī)運(yùn)行速度超快也不行。如果用二分法呢，只需要查找64次。64和一個(gè)比地球上沙子數(shù)量都大的數(shù)相比，這中間的差距可想而知。

所以我們想要快速查找，就必須要讓數(shù)據(jù)有順序，有了順序就可以用二分法快速查找。如果我們要存的數(shù)是數(shù)字，當(dāng)然很好辦，天然有序。如果不是數(shù)字其實(shí)也很簡(jiǎn)單，我們可以給它賦上一個(gè)id，給它們一個(gè)編號(hào)，用這個(gè)編號(hào)來(lái)排序，或者是根據(jù)我們的需要自己實(shí)現(xiàn)排序的邏輯，這都不是問(wèn)題。

真正的問(wèn)題在于數(shù)據(jù)結(jié)構(gòu)，雖然二分法很快，但我們并不能直接使用它。因?yàn)槲覀儾荒芤跃€性的形式來(lái)存儲(chǔ)數(shù)據(jù)，如果我們這樣做，當(dāng)我們要插入元素的時(shí)候，就會(huì)涉及數(shù)組中元素的移動(dòng)。這一移動(dòng)，那么插入的復(fù)雜度又蛻化成了。

所以我們需要使用二分查找的方法，但又不能使用數(shù)組，這就需要我們使用一個(gè)新的數(shù)據(jù)結(jié)構(gòu)。估計(jì)學(xué)過(guò)算法或者是看過(guò)老梁之前文章的同學(xué)應(yīng)該已經(jīng)猜到了，這樣的數(shù)據(jù)結(jié)構(gòu)就是樹(shù)，準(zhǔn)確得說(shuō)是二叉搜索樹(shù)。

老梁從網(wǎng)上找來(lái)一張圖，二叉搜索樹(shù)長(zhǎng)這樣：

它看起來(lái)很普通，但有一個(gè)很牛的性質(zhì)，就是對(duì)于任意一個(gè)節(jié)點(diǎn)，它都滿足它左子樹(shù)的所有元素都比它小，右子樹(shù)的所有元素都比它大。當(dāng)我們想要查找某一個(gè)元素的時(shí)候就很強(qiáng)大了，我們只需要利用這個(gè)性質(zhì)從根節(jié)點(diǎn)開(kāi)始往左往右遍歷，就能找到目標(biāo)了。

在理想情況下，我們每次進(jìn)行分支選擇的時(shí)候，都等價(jià)于舍棄掉了一半的元素，也就是將搜索空間縮小了一半。所以它其實(shí)也是一個(gè)二分查找算法，復(fù)雜度同樣是。

有了這樣的樹(shù)結(jié)構(gòu)，插入元素的問(wèn)題就解決了，因?yàn)闃?shù)上的元素都是離散的，我們插入節(jié)點(diǎn)并不會(huì)影響其他節(jié)點(diǎn)。但這又會(huì)產(chǎn)生另外一個(gè)問(wèn)題，就是插入元素會(huì)破壞樹(shù)上元素的分布。比如我們一直插入一個(gè)比樹(shù)上所有元素都要小的數(shù)，那么這個(gè)數(shù)會(huì)一直被添加在搜索樹(shù)的最左側(cè)，長(zhǎng)此以往就會(huì)導(dǎo)致這棵樹(shù)的左側(cè)元素特別多，這樣就會(huì)影響元素查找的性能。

好在這個(gè)問(wèn)題并不是無(wú)解的，我們可以設(shè)計(jì)一些算法讓樹(shù)在元素添加或者刪除的時(shí)候能夠自我修復(fù)平衡性，一直保持樹(shù)上元素的平衡。

從這個(gè)出發(fā)點(diǎn)設(shè)計(jì)出來(lái)的算法有很多，所以自平衡二叉搜索樹(shù)有很多種。比如常見(jiàn)的AVL、紅黑樹(shù)、SBT等等。在這許多算法當(dāng)中，公認(rèn)紅黑樹(shù)的統(tǒng)計(jì)性能最好，所以往往set、map這些關(guān)聯(lián)式容器的底層都是用紅黑樹(shù)寫(xiě)的。

所以到這里，整個(gè)邏輯就閉合上了，我們也終于可以回答那個(gè)一開(kāi)始的問(wèn)題。set是個(gè)啥?

set是一個(gè)用紅黑樹(shù)實(shí)現(xiàn)的關(guān)聯(lián)式容器，它可以有序地存儲(chǔ)數(shù)據(jù)，提供快速的查找、添加刪除的功能。

set有什么用?

搞明白了set是個(gè)啥，接下來(lái)的問(wèn)題就是它有什么用。

其實(shí)某種程度上來(lái)說(shuō)這兩個(gè)問(wèn)題是一個(gè)問(wèn)題，理解了它的設(shè)計(jì)原理和設(shè)計(jì)思路，自然也就明白了它能干什么。

最大的功能就是數(shù)據(jù)的查找，由于set底層是通過(guò)紅黑樹(shù)實(shí)現(xiàn)的，紅黑樹(shù)的本質(zhì)是二叉搜索樹(shù)。既然是二叉搜索樹(shù)就需要保證key唯一，所以set中的元素也必須是唯一的。那么我們就可以利用這個(gè)性質(zhì)來(lái)構(gòu)建一個(gè)容器，保證容器內(nèi)的元素是唯一的，并提供查詢功能。

舉個(gè)簡(jiǎn)單的例子，比如說(shuō)開(kāi)發(fā)了一個(gè)新功能要上線測(cè)試。為了防止除測(cè)試人員之外的其他用戶遇到bug影響用戶體驗(yàn)，所以一般常規(guī)措施都是維護(hù)一個(gè)白名單。也就是在名單中的人才能看到這個(gè)特性，其他用戶還是走老的邏輯。這樣的一個(gè)白名單用set就非常合適。

set的常規(guī)使用代碼也非常簡(jiǎn)單，也就只有幾行：

#include <set> 
 
// 創(chuàng)建set 
std::set<T> st; 
 
// 插入元素 
T t = T(); 
st.insert(t); 
 
// 查找元素 
if (st.count(t)) { 
     
} 

當(dāng)然這個(gè)只是最常規(guī)最常規(guī)的用法，除了這些之外，set還有很多進(jìn)階用法，以及不少注意事項(xiàng)。由于篇幅原因，我們下一篇文章再和大家詳細(xì)聊聊。

本文轉(zhuǎn)載自微信公眾號(hào)「Coder梁」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系Coder梁公眾號(hào)。