[[427784]]

大家好，我是梁唐。

今天我們繼續來聊C++的STL，今天來聊聊set。為了寫這篇文章，老梁花了一早上的時間把網上大部分關于set的博文都看了一遍。

看完之后發現不出所料的千篇一律，上來就是說怎么創建set，set里有哪些函數，標準的技術文檔。

這些東西對于老鳥來說當然沒問題，瞬間掃一眼就能找到自己想要的，但是對于新手來說估計看起來有些吃力。肯定一腦袋包，所以老梁另辟蹊徑，咱們先不羅列術語和api文檔，以記敘文的形式來說說它的前因后果、前世今生。

如果喜歡這種形式的文章，不妨給老梁點個贊，給老梁一點正反饋。

set是個啥?

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

在C++當中，這幾個東西的名字叫做vector、set和map，它們有一個共同的名字叫做STL(標準模板庫)容器。

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

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

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

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

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

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

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

那怎樣查找才快呢?

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

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

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

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

所以我們需要使用二分查找的方法，但又不能使用數組，這就需要我們使用一個新的數據結構。估計學過算法或者是看過老梁之前文章的同學應該已經猜到了，這樣的數據結構就是樹，準確得說是二叉搜索樹。

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

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

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

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

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

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

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

set是一個用紅黑樹實現的關聯式容器，它可以有序地存儲數據，提供快速的查找、添加刪除的功能。

set有什么用?

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

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

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

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

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

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

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

本文轉載自微信公眾號「Coder梁」，可以通過以下二維碼關注。轉載本文請聯系Coder梁公眾號。