關(guān)于STL中set容器的一些總結(jié)
1.關(guān)于set
C++ STL 之所以得到廣泛的贊譽(yù)，也被很多人使用，不只是提供了像vector, string, list等方便的容器，更重要的是STL封裝了許多復(fù)雜的數(shù)據(jù)結(jié)構(gòu)算法和大量常用數(shù)據(jù)結(jié)構(gòu)操作。vector封裝數(shù)組，list封裝了鏈表，map和set封裝了二叉樹(shù)等，在封裝這些數(shù)據(jù)結(jié)構(gòu)的時(shí)候，STL按照程序員的使用習(xí)慣，以成員函數(shù)方式提供的常用操作，如：插入、排序、刪除、查找等。讓用戶在STL使用過(guò)程中，并不會(huì)感到陌生。
關(guān)于set，必須說(shuō)明的是set關(guān)聯(lián)式容器。set作為一個(gè)容器也是用來(lái)存儲(chǔ)同一數(shù)據(jù)類(lèi)型的數(shù)據(jù)類(lèi)型，并且能從一個(gè)數(shù)據(jù)集合中取出數(shù)據(jù)，在set中每個(gè)元素的值都唯一，而且系統(tǒng)能根據(jù)元素的值自動(dòng)進(jìn)行排序。應(yīng)該注意的是set中數(shù)元素的值不能直接被改變。C++ STL中標(biāo)準(zhǔn)關(guān)聯(lián)容器set, multiset, map, multimap內(nèi)部采用的就是一種非常高效的平衡檢索二叉樹(shù)：紅黑樹(shù)，也成為RB樹(shù)(Red-Black Tree)。RB樹(shù)的統(tǒng)計(jì)性能要好于一般平衡二叉樹(shù)，所以被STL選擇作為了關(guān)聯(lián)容器的內(nèi)部結(jié)構(gòu)。
關(guān)于set有下面幾個(gè)問(wèn)題：
（1）為何map和set的插入刪除效率比用其他序列容器高？
大部分人說(shuō)，很簡(jiǎn)單，因?yàn)閷?duì)于關(guān)聯(lián)容器來(lái)說(shuō)，不需要做內(nèi)存拷貝和內(nèi)存移動(dòng)。說(shuō)對(duì)了，確實(shí)如此。set容器內(nèi)所有元素都是以節(jié)點(diǎn)的方式來(lái)存儲(chǔ)，其節(jié)點(diǎn)結(jié)構(gòu)和鏈表差不多，指向父節(jié)點(diǎn)和子節(jié)點(diǎn)。結(jié)構(gòu)圖可能如下：
A
/ \
B C
/ \ / \
D E F G
因此插入的時(shí)候只需要稍做變換，把節(jié)點(diǎn)的指針指向新的節(jié)點(diǎn)就可以了。刪除的時(shí)候類(lèi)似，稍做變換后把指向刪除節(jié)點(diǎn)的指針指向其他節(jié)點(diǎn)也OK了。這里的一切操作就是指針換來(lái)?yè)Q去，和內(nèi)存移動(dòng)沒(méi)有關(guān)系。
（2）為何每次insert之后，以前保存的iterator不會(huì)失效？
iterator這里就相當(dāng)于指向節(jié)點(diǎn)的指針，內(nèi)存沒(méi)有變，指向內(nèi)存的指針怎么會(huì)失效呢(當(dāng)然被刪除的那個(gè)元素本身已經(jīng)失效了)。相對(duì)于vector來(lái)說(shuō)，每一次刪除和插入，指針都有可能失效，調(diào)用push_back在尾部插入也是如此。因?yàn)闉榱吮ＷC內(nèi)部數(shù)據(jù)的連續(xù)存放，iterator指向的那塊內(nèi)存在刪除和插入過(guò)程中可能已經(jīng)被其他內(nèi)存覆蓋或者內(nèi)存已經(jīng)被釋放了。即使時(shí)push_back的時(shí)候，容器內(nèi)部空間可能不夠，需要一塊新的更大的內(nèi)存，只有把以前的內(nèi)存釋放，申請(qǐng)新的更大的內(nèi)存，復(fù)制已有的數(shù)據(jù)元素到新的內(nèi)存，最后把需要插入的元素放到最后，那么以前的內(nèi)存指針自然就不可用了。特別時(shí)在和find等算法在一起使用的時(shí)候，牢記這個(gè)原則：不要使用過(guò)期的iterator。
（3）當(dāng)數(shù)據(jù)元素增多時(shí)，set的插入和搜索速度變化如何？
如果你知道log2的關(guān)系你應(yīng)該就徹底了解這個(gè)答案。在set中查找是使用二分查找，也就是說(shuō)，如果有16個(gè)元素，最多需要比較4次就能找到結(jié)果，有32個(gè)元素，最多比較5次。那么有10000個(gè)呢？最多比較的次數(shù)為log10000，最多為14次，如果是20000個(gè)元素呢？最多不過(guò)15次?？匆?jiàn)了吧，當(dāng)數(shù)據(jù)量增大一倍的時(shí)候，搜索次數(shù)只不過(guò)多了1次，多了1/14的搜索時(shí)間而已。你明白這個(gè)道理后，就可以安心往里面放入元素了。
2.set中常用的方法
--------------------------------------------------------------------------------
begin() ,返回set容器的第一個(gè)元素
end() ,返回set容器的最后一個(gè)元素
clear() ,刪除set容器中的所有的元素
empty() ,判斷set容器是否為空
max_size() ,返回set容器可能包含的元素最大個(gè)數(shù)
size() ,返回當(dāng)前set容器中的元素個(gè)數(shù)
rbegin ,返回的值和end()相同
rend() ,返回的值和rbegin()相同
寫(xiě)一個(gè)程序練一練這幾個(gè)簡(jiǎn)單操作吧： using namespace std; int main()
#include <iostream>
#include <set>
{
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 中的第一個(gè)元素是 ："<<*s.begin()<<endl;
cout<<"set 中的最后一個(gè)元素是:"<<*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;
}
運(yùn)行結(jié)果：
小結(jié)：插入3之后雖然插入了一個(gè)1，但是我們發(fā)現(xiàn)set中最后一個(gè)值仍然是3哈，這就是set 。還要注意begin() 和 end()函數(shù)是不檢查set是否為空的，使用前最好使用empty()檢驗(yàn)一下set是否為空.
--------------------------------------------------------------------------------
count() 用來(lái)查找set中某個(gè)某個(gè)鍵值出現(xiàn)的次數(shù)。這個(gè)函數(shù)在set并不是很實(shí)用，因?yàn)橐粋€(gè)鍵值在set只可能出現(xiàn)0或1次，這樣就變成了判斷某一鍵值是否在set出現(xiàn)過(guò)了。
示例代碼： using namespace std; int main()
#include <iostream>
#include <set>
{
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;
}
運(yùn)行結(jié)果：
equal_range() ，返回一對(duì)定位器，分別表示第一個(gè)大于或等于給定關(guān)鍵值的元素和 第一個(gè)大于給定關(guān)鍵值的元素，這個(gè)返回值是一個(gè)pair類(lèi)型，如果這一對(duì)定位器中哪個(gè)返回失敗，就會(huì)等于end()的值。具體這個(gè)有什么用途我還沒(méi)遇到過(guò)~~~
示例代碼： using namespace std; int main()
#include <iostream>
#include <set>
{
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<<"第一個(gè)大于等于 3 的數(shù)是 ："<<*pr.first<<endl;
cout<<"第一個(gè)大于 3的數(shù)是 ： "<<*pr.second<<endl;
return 0;
}
運(yùn)行結(jié)果：
erase(iterator) ,刪除定位器iterator指向的值
erase(first,second),刪除定位器first和second之間的值
erase(key_value),刪除鍵值key_value的值
看看程序吧： using namespace std; int main()
#include <iostream>
#include <set>
{
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;
}
運(yùn)行結(jié)果：
小結(jié)：set中的刪除操作是不進(jìn)行任何的錯(cuò)誤檢查的，比如定位器的是否合法等等，所以用的時(shí)候自己一定要注意。
--------------------------------------------------------------------------------
find() ，返回給定值值得定位器，如果沒(méi)找到則返回end()。
示例代碼： using namespace std; int main()
#include <iostream>
#include <set>
{
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.
示例代碼： using namespace std; int main()
#include <iostream>
#include <set>
{
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;
}
運(yùn)行結(jié)果：
lower_bound(key_value) ，返回第一個(gè)大于等于key_value的定位器
upper_bound(key_value)，返回最后一個(gè)大于等于key_value的定位器
示例代碼： using namespace std; int main()
#include <iostream>
#include <set>
{
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;
}
運(yùn)行結(jié)果：
相關(guān)文章
C語(yǔ)言通過(guò)三步翻轉(zhuǎn)法實(shí)現(xiàn)單詞倒置詳解
這篇文章主要為大家分享了用三步翻轉(zhuǎn)法將一句話的單詞進(jìn)行倒置的方法，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以了解一下2022-05-05
這篇文章主要介紹了冒泡算法的改進(jìn)具體實(shí)現(xiàn)，有需要的朋友可以參考一下2013-12-12
C++ LibCurl實(shí)現(xiàn)Web指紋識(shí)別功能
Web指紋識(shí)別是一種通過(guò)分析Web應(yīng)用程序的特征和元數(shù)據(jù),以確定應(yīng)用程序所使用的技術(shù)棧和配置的技術(shù),本文將通過(guò)C++中LibCurl庫(kù)實(shí)現(xiàn)簡(jiǎn)單是指紋識(shí)別功能,感興趣的可以了解下2023-11-11
C語(yǔ)言實(shí)現(xiàn)支持動(dòng)態(tài)拓展和銷(xiāo)毀的線程池
這篇文章主要為大家介紹了C語(yǔ)言實(shí)現(xiàn)支持動(dòng)態(tài)拓展和銷(xiāo)毀的線程池，感興趣的小伙伴們可以參考一下2016-01-01
下面小編就為大家?guī)?lái)一篇淺談C++的淺拷貝出現(xiàn)的錯(cuò)誤。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-01-01
詳解如何在C/C++中測(cè)量一個(gè)函數(shù)或功能的運(yùn)行時(shí)間
本文算是一個(gè)比較完整的關(guān)于在 C/C++ 中測(cè)量一個(gè)函數(shù)或者功能的總結(jié),最后會(huì)演示三種方法的對(duì)比,文章通過(guò)代碼示例給大家介紹的非常詳細(xì),需要的朋友可以參考下2023-12-12
VC實(shí)現(xiàn)將網(wǎng)址解析出所有ip地址的實(shí)例代碼
這篇文章主要介紹了VC實(shí)現(xiàn)將網(wǎng)址解析出所有ip地址的實(shí)例代碼,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-04-04
這篇文章主要為大家詳細(xì)介紹了C++類(lèi)實(shí)現(xiàn)通訊錄功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-06-06
下面小編就為大家?guī)?lái)一篇C/C++ 進(jìn)程通訊(命名管道)的實(shí)例。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-08-08
C語(yǔ)言深入講解之從函數(shù)棧幀角度理解return關(guān)鍵字
在C語(yǔ)言中,一般情況下函數(shù)的返回值是通過(guò)函數(shù)中的return語(yǔ)句來(lái)實(shí)現(xiàn)的,每調(diào)用一次return語(yǔ)句只能從函數(shù)中返回一個(gè)值,這篇文章主要給大家介紹了關(guān)于C語(yǔ)言從函數(shù)棧幀角度理解return關(guān)鍵字的相關(guān)資料,需要的朋友可以參考下2021-09-09