set和multiset
生活随笔
收集整理的這篇文章主要介紹了
set和multiset
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
文章目錄
- 1 set和multiset基本概念
- 2 set和multiset的常用用法
- 2.1 set/multiset對(duì)象的默認(rèn)構(gòu)造
- 2.2 Set/multiset 對(duì)象的帶參構(gòu)造函數(shù)
- 2.3 set對(duì)象的拷貝構(gòu)造與賦值
- 2.4 set的插入和pair的用法
- 2.5 set與迭代器
- 2.6 set/multiset的大小
- 2.7 set/multiset的刪除
- 2.8 set/multiset的查找
- 3 set和multiset中的排序方法
1 set和multiset基本概念
set/multiset容器概念：
- set和multiset是一個(gè)集合容器，其中set所包含的元素是唯一的，集合中的元素按一定的順序排列。set采用紅黑樹(shù)變體的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，紅黑樹(shù)屬于平衡二叉樹(shù)。在插入操作和刪除操作上比vector快。在n個(gè)數(shù)中查找目標(biāo)數(shù)的效率是 log2^n。
紅黑樹(shù)定義：是每個(gè)節(jié)點(diǎn)都帶有顏色屬性（顏色為紅色或黑色）的自平衡二叉查找樹(shù)，滿足下列性質(zhì)：
（圖中的45節(jié)點(diǎn)是有錯(cuò)誤的，應(yīng)該比55大）。
Set和multiset 特點(diǎn)：
- set中元素插入過(guò)程是按排序規(guī)則插入，所以不能指定插入位置。
- set不可以直接存取元素。（不可以使用at.(pos)與[]操作符）。
multiset與set的區(qū)別：
- set支持唯一鍵值，每個(gè)元素值只能出現(xiàn)一次；而multiset中同一值可以出現(xiàn)多次。
- 不可以直接修改set或multiset容器中的元素值，因?yàn)樵擃惾萜魇亲詣?dòng)排序的。如果希望修改一個(gè)元素值，必須先刪除原有的元素，再插入新的元素。
頭文件 #include <set> 。
set和multiset簡(jiǎn)單使用示例：
#include <set> #include <iostream> #include <functional> #include <algorithm> using namespace std;int main(void) {set<int> setInt;multiset<int> msetInt;multiset<int> msetInt1(msetInt.begin(), msetInt.end());for(int i=0; i<10; i++){msetInt.insert(100-i);}//set 不允許插入相同的元素，而multiset 是支持插入多個(gè)相同元素的.msetInt.insert(99);multiset<int>::iterator it = msetInt.begin();for( ; it!=msetInt.end(); it++){cout<<*it;cout<<" ";}cout<<endl;system("pause");return 0; }2 set和multiset的常用用法
2.1 set/multiset對(duì)象的默認(rèn)構(gòu)造
set<int> setInt; //一個(gè)存放int的set容器。 set<float> setFloat; //一個(gè)存放float的set容器。 set<string> setString; //一個(gè)存放string的set容器。 multiset<int> mulsetInt; //一個(gè)存放int的multi set容器。 multiset<float> multisetFloat; //一個(gè)存放float的multi set容器。 multiset<string> multisetString; //一個(gè)存放string的multi set容器。2.2 Set/multiset 對(duì)象的帶參構(gòu)造函數(shù)
set(beg,end); //將[beg, end)區(qū)間中的元素拷貝給本身。 set(const set &s); //拷貝構(gòu)造函數(shù)。 multiset(beg,end); //將[beg, end)區(qū)間中的元素拷貝給本身。 multiset(const multiset &s); //拷貝構(gòu)造函數(shù)。2.3 set對(duì)象的拷貝構(gòu)造與賦值
set(const set &st); //拷貝構(gòu)造函數(shù) set& operator=(const set &st); //重載等號(hào)操作符 set.swap(st); //交換兩個(gè)集合容器setIntA.insert(5); set<int> setIntA; setIntA.insert(1); setIntA.insert(2); setIntA.insert(3); setIntA.insert(4);set<int> setIntB(setIntA); //1 2 3 4 5set<int> setIntC; setIntC = setIntA; //1 2 3 4 5 setIntC.insert(6); //1 2 3 4 5 6 setIntC.swap(setIntA); //交換2.4 set的插入和pair的用法
pair表示一個(gè)對(duì)組，它將兩個(gè)值視為一個(gè)單元，把兩個(gè)值捆綁在一起。
pair<T1,T2>用來(lái)存放的兩個(gè)值的類型，可以不一樣，也可以一樣，如T1為int，T2為float。T1,T2也可以是自定義類。
- pair.first是pair里面的第一個(gè)值，是T1類型。
- pair.second是pair里面的第二個(gè)值，是T2類型。
2.5 set與迭代器
set.insert(elem); //在容器中插入元素。 set.begin(); //返回容器中第一個(gè)數(shù)據(jù)的迭代器。 set.end(); //返回容器中最后一個(gè)數(shù)據(jù)之后的迭代器。 set.rbegin(); //返回容器中倒數(shù)第一個(gè)元素的迭代器。 set.rend(); //返回容器中倒數(shù)最后一個(gè)元素的后面的迭代器。set<int> setInt; setInt.insert(3); setInt.insert(4); setInt.insert(1); setInt.insert(5); setInt.insert(2);//順序輸出 1 2 3 4 5 for(set<int>::iterator it=setInt.begin(); it!=setInt.end(); ++it) {int elem = *it;cout << elem; //或直接使用cout << *it }2.6 set/multiset的大小
set.size(); //返回容器中元素的數(shù)目 set.empty();//判斷容器是否為空 //注意事項(xiàng)： 它們沒(méi)有resize 方法set<int> setIntA; setIntA.insert(3); setIntA.insert(1); setIntA.insert(7); setIntA.insert(5); setIntA.insert(9);if (!setIntA.empty()) {int iSize = setIntA.size(); //5 }2.7 set/multiset的刪除
set.clear(); //清除所有元素 set.erase(pos); //刪除pos迭代器所指的元素，返回下一個(gè)元素的迭代器。 set.erase(beg,end); //刪除區(qū)間[beg,end)的所有元素，返回下一個(gè)元素的迭代器。 set.erase(elem); //刪除容器中值為elem的元素。//刪除區(qū)間內(nèi)的某個(gè)或某些元素 //setInt是用set<int>聲明的容器，假設(shè)它內(nèi)部現(xiàn)已包含按順序的1, 2, 3, 4, 5, 6元素。 set<int>::iterator itBegin=setInt.begin(); ++ itBegin; set<int>::iterator itEnd=setInt.begin(); ++ itEnd; ++ itEnd; ++ itEnd; setInt.erase(itBegin,itEnd); //此時(shí)容器setInt包含按順序的1, 4, 5, 6四個(gè)元素。//刪除容器中第一個(gè)元素 setInt.erase(setInt.begin()); //4, 5, 6//刪除容器中值為5的元素 setInt.erase(5); //4, 6//刪除setInt的所有元素 setInt.clear(); //容器為空2.8 set/multiset的查找
set.find(elem); //查找elem元素，返回指向elem元素的迭代器。 set.count(elem); //返回容器中值為elem的元素個(gè)數(shù)。對(duì)set來(lái)說(shuō)，要么是0，要么是1。對(duì)multiset來(lái)說(shuō)，值可能大于1。 set.lower_bound(elem); //返回第一個(gè)>=elem元素的迭代器。 set.upper_bound(elem); // 返回第一個(gè)>elem元素的迭代器。 set.equal_range(elem); //返回容器中與elem相等的上下限的兩個(gè)迭代器。上限是閉區(qū)間，下限是開(kāi)區(qū)間，如[beg,end)。以上函數(shù)返回兩個(gè)迭代器，而這兩個(gè)迭代器被封裝在pair中。set<int> setInt; setInt.insert(1); setInt.insert(2); setInt.insert(3); setInt.insert(4); setInt.insert(5);set<int>::iterator it1 = setInt.find(4); int elem1 = *it1; //elem1 == 4 int iCount = setInt.count(3); //iCount == 1set<int>::iterator it2 = setInt.lower_bound(3); set<int>::iterator it3 = setInt.upper_bound(3); int elem2 = *it2; //i2 == 3 int elem3 = *it3; //i3 == 4pair< set<int>::iterator, set<int>::iterator > pairIt = setInt.equal_range(5);3 set和multiset中的排序方法
當(dāng)我們往set或者multiset中插入的元素時(shí)，就會(huì)進(jìn)行對(duì)元素之間進(jìn)行比較，STL中是通過(guò)函數(shù)對(duì)象實(shí)現(xiàn)的，也被成為仿函數(shù)。使用函數(shù)對(duì)象而不是直接進(jìn)行函數(shù)重載，是為了我們可以自定義比較方式，我們只需要定義自己的函數(shù)對(duì)象，就定義了完成了我們對(duì)排序方式的自定義。
仿函數(shù)概念：
- 盡管函數(shù)指針被廣泛用于實(shí)現(xiàn)函數(shù)回調(diào)，但C++還提供了一個(gè)重要的實(shí)現(xiàn)回調(diào)函數(shù)的方法，那就是函數(shù)對(duì)象。
- functor，翻譯成函數(shù)對(duì)象，偽函數(shù)，它是是重載了“()”操作符的普通類對(duì)象。從語(yǔ)法上講，它與普通函數(shù)行為類似。
- functional頭文件中包含的 greater<>與less<>就是函數(shù)對(duì)象。
看一下set的模板聲明部分：
下面舉出greater 和 less的簡(jiǎn)易實(shí)現(xiàn)原理：
set/setmulti容器就是調(diào)用函數(shù)對(duì)象的operator()方法去比較兩個(gè)值的大小。
下面給出示例程序：
#include <set> #include <iostream> #include <functional> #include <algorithm>using namespace std;class student { public:student(int age) {this->age = age;}bool operator < (const student &right) const{return this->age > right.age;}int getAge() const { return age; }private:int age;string name;};class FunStudent{ public:bool operator () (const student &left, const student &right){cout<<"調(diào)用了 FunStudent ."<<endl;ret = left.getAge() < right.getAge();return ret;}public:int ret; };int main(void) {//less 函數(shù)對(duì)象實(shí)現(xiàn)比較，為排序提供依據(jù)//less 和greater 都是函數(shù)對(duì)象，有叫仿函數(shù)//set<int,less<int>> set1;set<int,greater<int>> set1;for(int i=5; i>0; i--){set1.insert(i);}//less<student>set<student, FunStudent> setStu; //等同于 set<student,less<student>>student lixiaohua(18);student wangdachui(19);//函數(shù)對(duì)象(仿函數(shù))可以像函數(shù)一樣直接調(diào)用FunStudent funStu;funStu(lixiaohua, wangdachui);cout<<"比較結(jié)果："<<funStu.ret<<endl;setStu.insert(lixiaohua);setStu.insert(wangdachui);for (set<student, FunStudent>::iterator it = setStu.begin(); it != setStu.end(); it++) {cout << it->getAge() ;cout << " ";}system("pause");return 0; }參考資料：
總結(jié)
以上是生活随笔為你收集整理的set和multiset的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 变参模板、完美转发和emplace
- 下一篇： 任务的创建