1、set是什么

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

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

估計不少同學(xué)看到容器這兩個字腦袋有點發(fā)蒙，會有一種我當(dāng)然知道容器是什么意思，但是我不知道你這里說容器是什么意思的感覺?，F(xiàn)實中的容器是用來存儲東西的器皿，在編程語言當(dāng)中，也是一樣，只不過存儲的不再是實際的物品而是抽象的變量。

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

看到新的術(shù)語，估計又有同學(xué)要發(fā)蒙了，先別著急發(fā)蒙。其實我們可以大膽猜測一下，從字面理解，所謂關(guān)聯(lián)式說白了也就是把兩個事物關(guān)聯(lián)起來。那么新的問題又來了，這個關(guān)聯(lián)是什么？我們怎么做的關(guān)聯(lián)，又為什么要做關(guān)聯(lián)？

這幾個問題估計連很多老鳥都能唬住。

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

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

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

那怎樣查找才快呢？

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

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

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

真正的問題在于數(shù)據(jù)結(jié)構(gòu)，雖然二分法很快，但我們并不能直接使用它。因為我們不能以線性的形式來存儲數(shù)據(jù)，如果我們這樣做，當(dāng)我們要插入元素的時候，就會涉及數(shù)組中元素的移動。這一移動，那么插入的復(fù)雜度又蛻化成了。

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

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

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

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

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

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

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

所以到這里，整個邏輯就閉合上了，我們也終于可以回答那個一開始的問題。set是個啥？

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

2、set有什么用

搞明白了set是個啥，接下來的問題就是它有什么用。

其實某種程度上來說這兩個問題是一個問題，理解了它的設(shè)計原理和設(shè)計思路，自然也就明白了它能干什么。

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

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

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

#include <set>

// 創(chuàng)建set
std::set<T> st;

// 插入元素
T t = T();
st.insert(t);

// 查找元素
if (st.count(t)) {
    
}

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

到此這篇關(guān)于C++ set到底是什么的文章就介紹到這了,更多相關(guān)C++ set內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

注：文章轉(zhuǎn)自微信公眾號：Coder梁（ID：Coder_LT）

最新評論