STL之set

set簡介

set是一個集合容器，其中所包含的元素是唯一的，集合中的元素按一定的順序排列。元素插入過程是按排序規則插入，所以不能指定插入位置。
set采用紅黑樹變體的數據結構實現，紅黑樹屬于平衡二叉樹。在插入操作和刪除操作上比vector快。
set不可以直接存取元素。（不可以使用at.(pos)與[]操作符）。
multiset與set的區別：set支持唯一鍵值，每個元素值只能出現一次；而multiset中同一值可以出現多次。
不可以直接修改set或multiset容器中的元素值，因為該類容器是自動排序的。如果希望修改一個元素值，必須先刪除原有的元素，再插入新的元素。

#include <set>

默認構造

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();  //返回容器中第一個數據的迭代器。
set.end();  //返回容器中最后一個數據之后的迭代器。
set.rbegin();  //返回容器中倒數第一個元素的迭代器。
set.rend();   //返回容器中倒數最后一個元素的后面的迭代器。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>>。
less<int>與greater<int>中的int可以改成其它類型，該類型主要要跟set容納的數據類型一致。
疑問1：less<>與greater<>是什么？
疑問2：如果set<>不包含int類型，而是包含自定義類型，set容器如何排序？
要解決如上兩個問題，需要了解容器的函數對象，也叫仿函數，英文名叫functor。
下面將講解什么是functor，functor的用法。使用stl提供的函數對象
set<int,greater<int>> setIntB;   
setIntB.insert(3);
setIntB.insert(1);
setIntB.insert(5);
setIntB.insert(2);
此時容器setIntB就包含了按順序的5,3,2,1元素

函數對象functor的用法

盡管函數指針被廣泛用于實現函數回調，但C++還提供了一個重要的實現回調函數的方法，那就是函數對象。
functor，翻譯成函數對象，偽函數，算符，是重載了“()”操作符的普通類對象。從語法上講，它與普通函數行為類似。
greater<>與less<>就是函數對象。
下面舉出greater<int>的簡易實現原理。下面舉出greater<int>的簡易實現原理。
struct greater
{
bool operator() (const int& iLeft, const int& iRight)
{return (iLeft>iRight);    //如果是實現less<int>的話，這邊是寫return (iLeft<iRight);
}
}
容器就是調用函數對象的operator()方法去比較兩個值的大小。題目：學生包含學號，姓名屬性，現要求任意插入幾個學生對象到set容器中，使得容器中的學生按學號的升序排序。解：
//學生類
class CStudent
{public:CStudent(int iID, string strName){m_iID = iID;m_strName = strName;}int m_iID;       //學號string m_strName;   //姓名
}
//為保持主題鮮明，本類不寫拷貝構造函數，不類也不需要寫拷貝構造函數。但大家仍要有考慮拷貝構造函數的習慣。//函數對象
struct StuFunctor
{bool operator()  (const CStudent &stu1, const CStudent &stu2){return (stu1.m_iID<stu2.m_iID);}
}//main函數
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);             //拷貝構造函數
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 9set<int> setIntC;setIntC = setIntA;      //1 3 5 7 9setIntC.insert(6);setIntC.swap(setIntA);      //交換

set的大小

set.size();    //返回容器中元素的數目
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的刪除

set.clear();       //清除所有元素
set.erase(pos);   //刪除pos迭代器所指的元素，返回下一個元素的迭代器。
set.erase(beg,end);       //刪除區間[beg,end)的所有元素 ，返回下一個元素的迭代器。
set.erase(elem);     //刪除容器中值為elem的元素。刪除區間內的元素
setInt是用set<int>聲明的容器，現已包含按順序的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的查找

set.find(elem);   //查找elem元素，返回指向elem元素的迭代器。
set.count(elem);   //返回容器中值為elem的元素個數。對set來說，要么是0，要么是1。對multiset來說，值可能大于1。
set.lower_bound(elem);  //返回第一個>=elem元素的迭代器。
set.upper_bound(elem);     //  返回第一個>elem元素的迭代器。
set.equal_range(elem);         //返回容器中與elem相等的上下限的兩個迭代器。上限是閉區間，下限是開區間，如[beg,end)。以上函數返回兩個迭代器，而這兩個迭代器被封裝在pair中。
以下講解pair的含義與使用方法。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 == 5int iCount = setInt.count(5);    //iCount == 1set<int>::iterator itB = setInt.lower_bound(5);set<int>::iterator itC = setInt.upper_bound(5);int iB = *itB;    //iB == 5int iC = *itC; //iC == 7pair< 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

實例

#include <iostream>
#include <set>
#include <string>
using namespace std;void printA(set<int, less<int>> &s)
{set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";it++;}cout << endl;
}void printA(set<int, greater<int>> &s)
{set<int, greater<int>>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";it++;}cout << endl;
}// set集合里的數據是不允許修改的
void func1()
{set<int> s;s.insert(10);s.insert(2);s.insert(8);s.insert(6);cout << s.size() << endl;// set容器中的所有數據是唯一的，如果插入相同的數據，會失敗s.insert(8);s.insert(8);s.insert(8);s.insert(8);cout << s.size() << endl;// set容器中的數據都是排好序的, 默認是從小到大排序的printA(s);s.erase(s.begin());   // 通過迭代器刪除s.erase(8);           // 通過值刪除printA(s);
}void func2()
{// 默認從小到大排序// set<int> s;    //  ====>   set<int, less<int>> sset<int, greater<int>> s;s.insert(10);s.insert(2);s.insert(8);s.insert(6);printA(s);
}class Student
{
public:Student(int id, string name){this->id = id;this->name = name;}void print() const{printf ("id = %d, name = %s\n", id, name.c_str());}
public:int id;string name;
};class MySort
{
public:// 重載（）運算符，用來比較 student 的大小bool operator()(const Student &s1, const Student &s2){//return s1.id < s2.id;   // 從小到大return s1.id > s2.id;   // 從大到小}
};void func3()
{Student s1(11, "wang1");Student s2(12, "wang2");Student s3(13, "wang3");Student s4(14, "wang4");Student s5(15, "wang5");MySort ms;ms(s1, s3);   // ms 是一個類的對象，但是使用起來很相函數  =====>  仿函數 （函數對象）// 編譯器不知道怎么對自定義類型進行排序// set <int, less<int>>set<Student, MySort> s;s.insert(s1);s.insert(s4);s.insert(s2);    // s1, s2 s3s.insert(s5);s.insert(s3);set<Student, MySort>::iterator it;for (it = s.begin(); it != s.end(); it++)    { it->print();    // 集合里面的數據是不能被修改的 }}int main()
{//func1();//func2();func3();return 0;
}