[[428330]]

大家好，我是梁唐。

今天咱們繼續(xù)來(lái)聊聊C++中的set。

上次的文章遺留了一個(gè)問(wèn)題沒(méi)有回答，有些小伙伴有些疑問(wèn)。就是為什么說(shuō)set是關(guān)聯(lián)式的容器，這個(gè)關(guān)聯(lián)體現(xiàn)在哪里。

其實(shí)很簡(jiǎn)單，我們說(shuō)過(guò)set的內(nèi)部使用了紅黑樹(shù)對(duì)所有的元素進(jìn)行了排序。在樹(shù)結(jié)構(gòu)當(dāng)中，我們通常使用的都是<key, value>的形式。其中的key用來(lái)排序，value則是我們實(shí)際存儲(chǔ)的值。只不過(guò)set有些特殊，它的value和key是一樣的，相當(dāng)于是<key, key>的形式，所以它依然是關(guān)聯(lián)式的容器。

今天這篇文章主要來(lái)聊聊set的api以及一些特殊的用法。

創(chuàng)建set

首先是set容器的類模板定義。

template < class T,     // 鍵 key 和值 value 的類型 
           class Compare = less<T>,  // 指定 set 容器內(nèi)部的排序規(guī)則 
           class Alloc = allocator<T>  // 指定分配器對(duì)象的類型 
           > class set; 

其中第一個(gè)參數(shù)表示set當(dāng)中元素的類型，第二個(gè)參數(shù)則是set容器內(nèi)部的排序規(guī)則，第三個(gè)參數(shù)可以忽略，一般用不到。

set有3種構(gòu)造函數(shù)，可以應(yīng)用在不同的場(chǎng)景當(dāng)中，我們簡(jiǎn)單來(lái)列舉一下。

第一種

set<string> st; 

最常規(guī)的一種，沒(méi)有任何參數(shù)，直接創(chuàng)建。

第二種

set<string> st{"good", "bad", "medium"}; 

直接通過(guò)花括號(hào)枚舉我們要傳入set的值。

第三種

set<string> st{"good", "bad", "medium"}; 
set<string> st2(st); 

拷貝創(chuàng)建，從另外一個(gè)set當(dāng)中拷貝元素。

除了這三種形式的構(gòu)造函數(shù)之外，還可以利用set類模板的第二個(gè)參數(shù)，傳入元素排序規(guī)則來(lái)影響set中元素的排序，這勉強(qiáng)也算是一種構(gòu)造方法：

set<string, greater<string>> st{"good", "bad", "medium"}; 

我們不傳入greater的排序結(jié)果是"bad", "good", "medium"，當(dāng)我們傳入了這個(gè)參數(shù)之后，結(jié)果會(huì)變成："medium", "good", "bad"。

這是因?yàn)槲覀儌魅氲呐判蛞?guī)則重新定義了元素的大小關(guān)系。

使用set

創(chuàng)建完了set就需要使用，使用無(wú)非增刪改查。

我們先來(lái)說(shuō)說(shuō)增，往set里添加元素的函數(shù)有好幾個(gè)，我們一個(gè)一個(gè)來(lái)說(shuō)。

insert

insert函數(shù)非常簡(jiǎn)單，就直接調(diào)用，往set里插入即可。

st.insert("hhh"); 

但insert還可以批量插入多個(gè)元素：

st.insert({"hhh", "wow"}); 

emplace

emplace函數(shù)的功能和insert一樣，可以往set當(dāng)中插入元素。它和insert最大的區(qū)別在于emplace傳入的參數(shù)并不是要插入的元素，而是構(gòu)造元素需要的參數(shù)。

我這么說(shuō)估計(jì)有點(diǎn)難理解，其實(shí)很簡(jiǎn)單，我們來(lái)對(duì)比一下就知道了。

假設(shè)我們有一個(gè)set它的類型是結(jié)構(gòu)體P，當(dāng)中我們重載了它的比較算子，這個(gè)先忽略。

struct P { 
 int x, y; 
    P(int x, int y) : x(x), y(y){}; 
    bool operator<(const P b) const  {   
         return this->x < b.x;   
    }  
}; 
 
set<P> st; 

如果我們要使用insert應(yīng)該怎么操作呢？

P p{0, 3}; 
st.insert(p); 

如果使用emplace函數(shù)呢，則是這樣：

st.emplace(1, 23); 

因?yàn)閑mplace的內(nèi)部會(huì)替我們?nèi)フ{(diào)用結(jié)構(gòu)體P的構(gòu)造函數(shù)，使用1和23這兩個(gè)參數(shù)構(gòu)造出一個(gè)P的實(shí)例來(lái)存入set當(dāng)中。

使用emplace可以節(jié)省掉創(chuàng)建實(shí)例的一步，所以通常工程當(dāng)中往往大量使用emplace。

emplace函數(shù)返回的結(jié)果是一個(gè)pair，pair的第一個(gè)元素是set的迭代器，表示插入的元素的位置，第二個(gè)值是一個(gè)bool，表示是否插入成功。

emplace_hint

emplace函數(shù)的改進(jìn)版，接受額外的參數(shù)表示插入set的位置。它的返回結(jié)果也有了一些變化，返回的是一個(gè)迭代器。

如果插入成功則返回新添加的元素，否則則指向set容器中和添加元素相同的元素。

使用emplace_hint會(huì)影響set中的有序性，一般不建議使用。

erase

說(shuō)完了插入再說(shuō)說(shuō)刪除，在set當(dāng)中刪除的方法只有一個(gè)就是erase，但是它卻有好幾種用法。

我們直接來(lái)看它的函數(shù)簽名：

size_type erase (const value_type& val); 
iterator erase (const_iterator position); 
iterator erase (const_iterator first, const_iterator last); 

第一種方法我們傳入了一個(gè)val值，也就是我們要?jiǎng)h除的元素。

第二種方法我們傳入的是一個(gè)迭代器，它會(huì)刪除迭代器指向的元素。第三種方法類似，只不過(guò)我們傳入的是兩個(gè)迭代器，表示一個(gè)范圍，它會(huì)刪除這個(gè)范圍內(nèi)所有的元素。

第一種方法的返回值是一個(gè)整數(shù)，表示刪除的元素個(gè)數(shù)。后面兩種返回的都是一個(gè)迭代器，指向刪除元素后面一個(gè)位置。

clear

清空set。

find

set中的查詢函數(shù)，傳入我們要查詢的value，返回一個(gè)迭代器。

set<string>::iterator it = st.find("good"); 

如果成功找到則返回指向該元素的迭代器，否則指向end。

count

同樣是查詢函數(shù)，只不過(guò)它返回的不再是迭代器，而是一個(gè)整數(shù)，表示查詢到元素的個(gè)數(shù)。

int cnt = st.count("good"); 
 
lower_bound 和 upper_bound 

lower_bound和upper_bound嚴(yán)格也算是查詢函數(shù)，只不過(guò)它們查詢的范圍。lower_bound查詢的是set當(dāng)中第一個(gè)大于等于val的位置，而upper_bound查詢的是set中第一個(gè)嚴(yán)格大于val的位置。

set<string>::iterator it_low = st.lower_bound("i"); 
set<string>::iterator it_up = st.upper_bound("i"); 

同樣這兩個(gè)函數(shù)返回的是一個(gè)迭代器。

equal_range

這個(gè)函數(shù)返回的是一個(gè)pair，它的第一個(gè)元素是lower_bound的結(jié)果，第二個(gè)元素是upper_bound的結(jié)果。

pair<set<string>::iterator, set<string>::iterator> ret = st.equal_range("i"); 

總結(jié)

到這里，關(guān)于set常用的方法基本上就都介紹完了，除此之外還有一些其他細(xì)枝末節(jié)的方法就不贅述了。比如像是size()，max_size()等等，大家有用到去查詢即可。

但是有一個(gè)疑問(wèn)不知道大家有沒(méi)有發(fā)現(xiàn)，就是我們沒(méi)有介紹到修改的函數(shù)。是set不支持修改嗎？

關(guān)于這個(gè)問(wèn)題的答案并不是老梁故意賣關(guān)子，而是它非常復(fù)雜，一句兩句很難說(shuō)清楚，老梁將在下一篇文章當(dāng)中好好探討一下這個(gè)問(wèn)題。如果大家有修改元素的需求，可以用erase + insert代替。

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