Set和multiset容器

set/multiset的簡介

set是一個集合容器，其中所包含的元素是唯一的，集合中的元素按一定的順序排列。元素插入過程是按排序規(guī)則插入，所以不能指定插入位置。

set采用紅黑樹變體的數(shù)據(jù)結構實現(xiàn)，紅黑樹屬于平衡二叉樹。在插入操作和刪除操作上比vector快。

set不可以直接存取元素。（不可以使用at.(pos)與[]操作符）。

 multiset與set的區(qū)別：set支持唯一鍵值，每個元素值只能出現(xiàn)一次；而multiset中同一值可以出現(xiàn)多次。

 不可以直接修改set或multiset容器中的元素值，因為該類容器是自動排序的。如果希望修改一個元素值，必須先刪除原有的元素，再插入新的元素。

 #include <set>  

set/multiset對象的默認構造

set<int> setInt;            //一個存放int的set容器。

set<float> setFloat;     //一個存放float的set容器。

set<string> setString;     //一個存放string的set容器。

multiset<int> mulsetInt;            //一個存放int的multi set容器。

multi set<float> multisetFloat;     //一個存放float的multi set容器。

multi set<string> multisetString;     //一個存放string的multi set容器。

set的插入與迭代器

set.insert(elem);     //在容器中插入元素。

set.begin();  //返回容器中第一個數(shù)據(jù)的迭代器。

set.end();  //返回容器中最后一個數(shù)據(jù)之后的迭代器。

set.rbegin();  //返回容器中倒數(shù)第一個元素的迭代器。

set.rend();   //返回容器中倒數(shù)最后一個元素的后面的迭代器。

set<int> setInt;

setInt.insert(3); setInt.insert(1);setInt.insert(5);setInt.insert(2);

for(set<int>::iterator it=setInt.begin(); it!=setInt.end(); ++it)

{

      int iItem = *it;

      cout << iItem;    //或直接使用cout << *it

}

//這樣子便順序輸出  1 2 3 5。

set.rbegin()與set.rend()。略。

Set集合的元素排序

set<int,less<int> >  setIntA;  //該容器是按升序方式排列元素。

 set<int,greater<int>> setIntB;   //該容器是按降序方式排列元素。

set<int> 相當于 set<int,less<int>>。

ess<int>與greater<int>中的int可以改成其它類型，該類型主要要跟set容納的數(shù)據(jù)類型一致。

 疑問1：less<>與greater<>是什么？

疑問2：如果set<>不包含int類型，而是包含自定義類型，set容器如何排序？

要解決如上兩個問題，需要了解容器的函數(shù)對象，也叫偽函數(shù)，英文名叫functor。

下面將講解什么是functor，functor的用法。

使用stl提供的函數(shù)對象

set<int,greater<int>> setIntB;   

setIntB.insert(3);

setIntB.insert(1);

setIntB.insert(5);

setIntB.insert(2);

此時容器setIntB就包含了按順序的5,3,2,1元素

函數(shù)對象functor的用法

盡管函數(shù)指針被廣泛用于實現(xiàn)函數(shù)回調，但C++還提供了一個重要的實現(xiàn)回調函數(shù)的方法，那就是函數(shù)對象。

 functor，翻譯成函數(shù)對象，偽函數(shù)，算符，是重載了“()”操作符的普通類對象。從語法上講，它與普通函數(shù)行為類似。

greater<>與less<>就是函數(shù)對象。

下面舉出greater<int>的簡易實現(xiàn)原理。

下面舉出greater<int>的簡易實現(xiàn)原理。

struct greater

{

bool Operator() (const int& iLeft, const int& iRight)

{

       return (iLeft>iRight);    //如果是實現(xiàn)less<int>的話，這邊是寫return (iLeft<iRight);

}

}

容器就是調用函數(shù)對象的operator()方法去比較兩個值的大小。

題目：學生包含學號，姓名屬性，現(xiàn)要求任意插入幾個學生對象到set容器中，使得容器中的學生按學號的升序排序。

解：

//學生類

class CStudent

{

public:

CStudent(int iID, string strName)

{

m_iID = iID;

m_strName = strName;

}

     int m_iID; //學號

     string m_strName; //姓名

}

//為保持主題鮮明，本類不寫拷貝構造函數(shù)，不類也不需要寫拷貝構造函數(shù)。但大家仍要有考慮拷貝構造函數(shù)的習慣。

//函數(shù)對象

struct StuFunctor

{

bool operator()  (const CStudent &stu1, const CStudent &stu2)

{

return (stu1.m_iID<stu2.m_iID);

}

}

//main函數(shù)

void main()

{

set<CStudent, StuFunctor> setStu;

setStu.insert(CStudent(3,"小張"));

setStu.insert(CStudent(1,"小李"));

setStu.insert(CStudent(5,"小王"));

setStu.insert(CStudent(2,"小劉"));

//此時容器setStu包含了四個學生對象，分別是按姓名順序的“小李”，“小劉”，“小張”，“小王” 

}

set對象的拷貝構造與賦值

set(const set &st);      //拷貝構造函數(shù)

set& operator=(const set &st); //重載等號操作符

set.swap(st); //交換兩個集合容器

set<int> setIntA;

setIntA.insert(3);

setIntA.insert(1);

setIntA.insert(7);

setIntA.insert(5);

setIntA.insert(9);

set<int> setIntB(setIntA);  //1 3 5 7 9

set<int> setIntC;

setIntC = setIntA; //1 3 5 7 9

setIntC.insert(6);

setIntC.swap(setIntA);   //交換

set的大小

2 set.size(); //返回容器中元素的數(shù)目

2 set.empty();//判斷容器是否為空

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

}

set的刪除

2 set.clear(); //清除所有元素

2 set.erase(pos); //刪除pos迭代器所指的元素，返回下一個元素的迭代器。

2 set.erase(beg,end);     //刪除區(qū)間[beg,end)的所有元素，返回下一個元素的迭代器。

2 set.erase(elem);     //刪除容器中值為elem的元素。

刪除區(qū)間內的元素

setInt是用set<int>聲明的容器，現(xiàn)已包含按順序的1,3,5,6,9,11元素。

set<int>::iterator itBegin=setInt.begin();

++ itBegin;

set<int>::iterator itEnd=setInt.begin();

++ itEnd;

++ itEnd;

++ itEnd;

setInt.erase(itBegin,itEnd);

//此時容器setInt包含按順序的1,6,9,11四個元素。

刪除容器中第一個元素

setInt.erase(setInt.begin()); //6,9,11

刪除容器中值為9的元素

set.erase(9);    

刪除setInt的所有元素

setInt.clear(); //容器為空

set的查找

2 set.find(elem);   //查找elem元素，返回指向elem元素的迭代器。

2 set.count(elem);   //返回容器中值為elem的元素個數(shù)。對set來說，要么是0，要么是1。對multiset來說，值可能大于1。

2 set.lower_bound(elem);  //返回第一個>=elem元素的迭代器。

2 set.upper_bound(elem);    //  返回第一個>elem元素的迭代器。

2 set.equal_range(elem); //返回容器中與elem相等的上下限的兩個迭代器。上限是閉區(qū)間，下限是開區(qū)間，如[beg,end)。

2  

2 以上函數(shù)返回兩個迭代器，而這兩個迭代器被封裝在pair中。

2 以下講解pair的含義與使用方法。

2 

set<int> setInt;

setInt.insert(3);

setInt.insert(1);

setInt.insert(7);

setInt.insert(5);

setInt.insert(9);

set<int>::iterator itA = setInt.find(5);

int iA = *itA; //iA == 5

int iCount = setInt.count(5); //iCount == 1

set<int>::iterator itB = setInt.lower_bound(5);

set<int>::iterator itC = setInt.upper_bound(5);

int iB = *itB; //iB == 5

int iC = *itC; //iC == 7

pair< set<int>::iterator, set<int>::iterator > pairIt = setInt.equal_range(5);  //pair是什么？

pair的使用

pair譯為對組，可以將兩個值視為一個單元。

pair<T1,T2>存放的兩個值的類型，可以不一樣，如T1為int，T2為float。T1,T2也可以是自定義類型。

pair.first是pair里面的第一個值，是T1類型。

pair.second是pair里面的第二個值，是T2類型。

set<int> setInt;

...  //往setInt容器插入元素1,3,5,7,9

pair< set<int>::iterator , set<int>::iterator > pairIt = setInt.equal_range(5);

set<int>::iterator itBeg = pairIt.first;

set<int>::iterator itEnd = pairIt.second;

//此時 *itBeg==5  而  *itEnd == 7

小結

2 一、容器set/multiset的使用方法；

紅黑樹的變體，查找效率高，插入不能指定位置，插入時自動排序。

2 二、functor的使用方法；

    類似于函數(shù)的功能，可用來自定義一些規(guī)則，如元素比較規(guī)則。

2 三、pair的使用方法。

對組，一個整體的單元，存放兩個類型(T1,T2，T1可與T2一樣)的兩個元素。

案例:

int x;

    scanf("%ld",&x);

    multiset<int> h;//建立一個multiset類型，變量名是h，h序列里面存的是int類型,初始h為空

    while(x!=0){

        h.insert(x);//將x插入h中

        scanf("%ld",&x);

    }    

pair< multiset<int>::iterator , multiset<int>::iterator > pairIt = h.equal_range(22);

multiset<int>::iterator itBeg = pairIt.first;

multiset<int>::iterator itEnd = pairIt.second;

int nBeg = *itBeg;

int nEnd = *itEnd;

    while(!h.empty()){//序列非空h.empty()==true時表示h已經空了

multiset<int>::iterator c = h.begin();//c指向h序列中第一個元素的地址，第一個元素是最小的元素

        PRintf("%ld ",*c);//將地址c存的數(shù)據(jù)輸出

        h.erase(c);//從h序列中將c指向的元素刪除

    }