總結(jié)STL中set容器

2020-02-24 14:24:51

字體：大中小

供稿：網(wǎng)友

set可以存儲相同數(shù)據(jù)類型的數(shù)據(jù)，還可以從數(shù)據(jù)集中提取數(shù)據(jù)，其實每個set是唯一的，下面就讓武林技術(shù)頻道小編帶我們一起去看看總結(jié)STL中set容器吧。

1.關(guān)于set

C++ STL 之所以得到廣泛的贊譽，也被很多人使用，不只是提供了像vector, string, list等方便的容器，更重要的是STL封裝了許多復(fù)雜的數(shù)據(jù)結(jié)構(gòu)算法和大量常用數(shù)據(jù)結(jié)構(gòu)操作。vector封裝數(shù)組，list封裝了鏈表，map和set封裝了二叉樹等，在封裝這些數(shù)據(jù)結(jié)構(gòu)的時候，STL按照程序員的使用習(xí)慣，以成員函數(shù)方式提供的常用操作，如：插入、排序、刪除、查找等。讓用戶在STL使用過程中，并不會感到陌生。

關(guān)于set，必須說明的是set關(guān)聯(lián)式容器。set作為一個容器也是用來存儲同一數(shù)據(jù)類型的數(shù)據(jù)類型，并且能從一個數(shù)據(jù)集合中取出數(shù)據(jù)，在set中每個元素的值都唯一，而且系統(tǒng)能根據(jù)元素的值自動進行排序。應(yīng)該注意的是set中數(shù)元素的值不能直接被改變。C++ STL中標(biāo)準(zhǔn)關(guān)聯(lián)容器set, multiset, map, multimap內(nèi)部采用的就是一種非常高效的平衡檢索二叉樹：紅黑樹，也成為RB樹(Red-Black Tree)。RB樹的統(tǒng)計性能要好于一般平衡二叉樹，所以被STL選擇作為了關(guān)聯(lián)容器的內(nèi)部結(jié)構(gòu)。

?關(guān)于set有下面幾個問題：

（1）為何map和set的插入刪除效率比用其他序列容器高？

大部分人說，很簡單，因為對于關(guān)聯(lián)容器來說，不需要做內(nèi)存拷貝和內(nèi)存移動。說對了，確實如此。set容器內(nèi)所有元素都是以節(jié)點的方式來存儲，其節(jié)點結(jié)構(gòu)和鏈表差不多，指向父節(jié)點和子節(jié)點。結(jié)構(gòu)圖可能如下：

　　A
　? / /
　 B C
　/ / / /
? D E F G

因此插入的時候只需要稍做變換，把節(jié)點的指針指向新的節(jié)點就可以了。刪除的時候類似，稍做變換后把指向刪除節(jié)點的指針指向其他節(jié)點也OK了。這里的一切操作就是指針換來換去，和內(nèi)存移動沒有關(guān)系。

（2）為何每次insert之后，以前保存的iterator不會失效？

iterator這里就相當(dāng)于指向節(jié)點的指針，內(nèi)存沒有變，指向內(nèi)存的指針怎么會失效呢(當(dāng)然被刪除的那個元素本身已經(jīng)失效了)。相對于vector來說，每一次刪除和插入，指針都有可能失效，調(diào)用push_back在尾部插入也是如此。因為為了保證內(nèi)部數(shù)據(jù)的連續(xù)存放，iterator指向的那塊內(nèi)存在刪除和插入過程中可能已經(jīng)被其他內(nèi)存覆蓋或者內(nèi)存已經(jīng)被釋放了。即使時push_back的時候，容器內(nèi)部空間可能不夠，需要一塊新的更大的內(nèi)存，只有把以前的內(nèi)存釋放，申請新的更大的內(nèi)存，復(fù)制已有的數(shù)據(jù)元素到新的內(nèi)存，最后把需要插入的元素放到最后，那么以前的內(nèi)存指針自然就不可用了。特別時在和find等算法在一起使用的時候，牢記這個原則：不要使用過期的iterator。

（3）當(dāng)數(shù)據(jù)元素增多時，set的插入和搜索速度變化如何？

如果你知道log2的關(guān)系你應(yīng)該就徹底了解這個答案。在set中查找是使用二分查找，也就是說，如果有16個元素，最多需要比較4次就能找到結(jié)果，有32個元素，最多比較5次。那么有10000個呢？最多比較的次數(shù)為log10000，最多為14次，如果是20000個元素呢？最多不過15次。看見了吧，當(dāng)數(shù)據(jù)量增大一倍的時候，搜索次數(shù)只不過多了1次，多了1/14的搜索時間而已。你明白這個道理后，就可以安心往里面放入元素了。

2.set中常用的方法

--------------------------------------------------------------------------------

begin()???? 　　 ,返回set容器的第一個元素

end() 　　　　 ,返回set容器的最后一個元素

clear()?? 　　???? ,刪除set容器中的所有的元素

empty() 　　　,判斷set容器是否為空

max_size() 　 ,返回set容器可能包含的元素最大個數(shù)

size() 　　　　 ,返回當(dāng)前set容器中的元素個數(shù)

rbegin　　　　 ,返回的值和end()相同

rend()　　　　 ,返回的值和rbegin()相同

寫一個程序練一練這幾個簡單操作吧：

#include <iostream>
#include <set>

using namespace std;

int main()
{
??? set<int> s;
??? s.insert(1);
??? s.insert(2);
??? s.insert(3);
??? s.insert(1);
??? cout<<"set 的 size 值為："<<s.size()<<endl;
??? cout<<"set 的 maxsize的值為："<<s.max_size()<<endl;
??? cout<<"set 中的第一個元素是："<<*s.begin()<<endl;
??? cout<<"set 中的最后一個元素是:"<<*s.end()<<endl;
??? s.clear();
??? if(s.empty())
??? {
??????? cout<<"set 為空！！！"<<endl;
??? }
??? cout<<"set 的 size 值為："<<s.size()<<endl;
??? cout<<"set 的 maxsize的值為："<<s.max_size()<<endl;
??? return 0;
}

運行結(jié)果：

小結(jié)：插入3之后雖然插入了一個1，但是我們發(fā)現(xiàn)set中最后一個值仍然是3哈，這就是set 。還要注意begin() 和 end()函數(shù)是不檢查set是否為空的，使用前最好使用empty()檢驗一下set是否為空.

--------------------------------------------------------------------------------

count() 用來查找set中某個某個鍵值出現(xiàn)的次數(shù)。這個函數(shù)在set并不是很實用，因為一個鍵值在set只可能出現(xiàn)0或1次，這樣就變成了判斷某一鍵值是否在set出現(xiàn)過了。

示例代碼：

#include <iostream>
#include <set>

using namespace std;

int main()
{
??? set<int> s;
??? s.insert(1);
??? s.insert(2);
??? s.insert(3);
??? s.insert(1);
??? cout<<"set 中 1 出現(xiàn)的次數(shù)是："<<s.count(1)<<endl;
??? cout<<"set 中 4 出現(xiàn)的次數(shù)是："<<s.count(4)<<endl;
??? return 0;
}

運行結(jié)果：

equal_range() ，返回一對定位器，分別表示第一個大于或等于給定關(guān)鍵值的元素和第一個大于給定關(guān)鍵值的元素，這個返回值是一個pair類型，如果這一對定位器中哪個返回失敗，就會等于end()的值。具體這個有什么用途我還沒遇到過~~~

示例代碼：

#include <iostream>
#include <set>

using namespace std;

int main()
{
??? set<int> s;
??? set<int>::iterator iter;
??? for(int i = 1 ; i <= 5; ++i)
??? {
??????? s.insert(i);
??? }
??? for(iter = s.begin() ; iter != s.end() ; ++iter)
??? {
??????? cout<<*iter<<" ";
??? }
??? cout<<endl;
??? pair<set<int>::const_iterator,set<int>::const_iterator> pr;
??? pr = s.equal_range(3);
??? cout<<"第一個大于等于 3 的數(shù)是："<<*pr.first<<endl;
??? cout<<"第一個大于 3的數(shù)是： "<<*pr.second<<endl;
??? return 0;
}

運行結(jié)果：

erase(iterator)? ,刪除定位器iterator指向的值

erase(first,second),刪除定位器first和second之間的值

erase(key_value),刪除鍵值key_value的值

看看程序吧：

#include <iostream>
#include <set>

using namespace std;

int main()
{
??? set<int> s;
??? set<int>::const_iterator iter;
??? set<int>::iterator first;
??? set<int>::iterator second;
??? for(int i = 1 ; i <= 10 ; ++i)
??? {
??????? s.insert(i);
??? }
??? //第一種刪除
??? s.erase(s.begin());
??? //第二種刪除
??? first = s.begin();
??? second = s.begin();
??? second++;
??? second++;
??? s.erase(first,second);
??? //第三種刪除
??? s.erase(8);
??? cout<<"刪除后 set 中元素是：";
??? for(iter = s.begin() ; iter != s.end() ; ++iter)
??? {
??????? cout<<*iter<<" ";
??? }
??? cout<<endl;
??? return 0;
}

運行結(jié)果：

小結(jié)：set中的刪除操作是不進行任何的錯誤檢查的，比如定位器的是否合法等等，所以用的時候自己一定要注意。

--------------------------------------------------------------------------------

find()? ，返回給定值值得定位器，如果沒找到則返回end()。

示例代碼：

#include <iostream>
#include <set>

using namespace std;

int main()
{
??? int a[] = {1,2,3};
??? set<int> s(a,a+3);
??? set<int>::iterator iter;
??? if((iter = s.find(2)) != s.end())
??? {
??????? cout<<*iter<<endl;
??? }
??? return 0;
}

insert(key_value); 將key_value插入到set中，返回值是pair<set<int>::iterator,bool>，bool標(biāo)志著插入是否成功，而iterator代表插入的位置，若key_value已經(jīng)在set中，則iterator表示的key_value在set中的位置。

inset(first,second);將定位器first到second之間的元素插入到set中，返回值是void.

示例代碼：

#include <iostream>
#include <set>

using namespace std;

int main()
{
??? int a[] = {1,2,3};
??? set<int> s;
??? set<int>::iterator iter;
??? s.insert(a,a+3);
??? for(iter = s.begin() ; iter != s.end() ; ++iter)
??? {
??????? cout<<*iter<<" ";
??? }
??? cout<<endl;
??? pair<set<int>::iterator,bool> pr;
??? pr = s.insert(5);
??? if(pr.second)
??? {
??????? cout<<*pr.first<<endl;
??? }
??? return 0;
}

運行結(jié)果：

lower_bound(key_value) ，返回第一個大于等于key_value的定位器

upper_bound(key_value)，返回最后一個大于等于key_value的定位器

示例代碼：

#include <iostream>
#include <set>

using namespace std;

int main()
{
??? set<int> s;
??? s.insert(1);
??? s.insert(3);
??? s.insert(4);
??? cout<<*s.lower_bound(2)<<endl;
??? cout<<*s.lower_bound(3)<<endl;
??? cout<<*s.upper_bound(3)<<endl;
??? return 0;
}

運行結(jié)果：