一、set集合容器
set實(shí)現(xiàn)了紅黑樹的平衡二叉檢索樹，插入元素時(shí)會(huì)自動(dòng)調(diào)整二叉樹，使得每個(gè)子樹根節(jié)點(diǎn)的鍵值大于左子樹所有節(jié)點(diǎn)的鍵值，小于右子樹所有節(jié)點(diǎn)的鍵值，且不會(huì)重復(fù)插入鍵值相同的元素。同時(shí)保證根節(jié)點(diǎn)左右子樹的高度相等。這樣二叉樹高度最小，檢索速度最快。
衡二叉檢索樹的檢索使用中序遍歷算法，效率高于vector、deque、list等容器，multiset、map、multimap的內(nèi)部結(jié)構(gòu)也是平衡二叉檢索樹。
set集合處理函數(shù)
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
int main()
{
//構(gòu)建set集合，指定元素類型，此時(shí)為空
set<int> s;
//插入元素
s.insert(8);
s.insert(1);
s.insert(12);
s.insert(8); //重復(fù)不會(huì)插入
//會(huì)按中序遍歷，即從小到大輸出鍵值
set<int>::iterator it;
for (it = s.begin(); it != s.end(); it ++)
cout << *it <<" ";
cout<<endl;
//元素的檢索，找到查找的鍵值返回該鍵值的迭代器位置，否則返回該集合最后一個(gè)元素的下一位置，即end()
it = s.find(12);
if (it != s.end())
cout << *it <<endl;
else
cout << "not find it" <<endl;
it = s.find(20);
if (it != s.end())
cout << *it <<endl;
else
cout << "not find it" <<endl;
//元素刪除，刪除對(duì)象可以是某迭代器位置上的元素、等于某鍵值的元素、一個(gè)區(qū)間上的元素和清空集合
s.erase(8);
//反向遍歷集合中元素
set<int>::reverse_iterator rit;
for (rit = s.rbegin(); rit != s.rend(); rit ++)
cout << *rit <<" ";
cout<<endl;
s.clear(); //清空
cout<<s.size()<<endl;
return 0;
}
自定義比較函數(shù)，默認(rèn)的比較函數(shù)按鍵值從小到大的順序插入元素，例如要換成從大到小的順序，有兩種自定義方法：
- 若元素不是結(jié)構(gòu)體，可編寫比較函數(shù)
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
//自定義比較函數(shù)，重載“（）”操作符
struct cmp
{
bool operator()(const int &a, const int &b)
{
if (a != b)
return a > b;
else
return a > b;
}
};
int main()
{
//構(gòu)建set集合，指定元素類型，此時(shí)為空
set<int, cmp> s;
//插入元素
s.insert(8);
s.insert(1);
s.insert(12);
s.insert(6);
set<int, cmp>::iterator cit;
for (cit = s.begin(); cit != s.end(); cit ++)
cout << *cit <<" ";
cout<<endl;
return 0;
}
=> 12 8 6 1
- 若元素是結(jié)構(gòu)體，可直接把比較函數(shù)寫在結(jié)構(gòu)體中
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
struct info
{
string name;
float score;
bool operator < (const info &a) const
{
return a.score < score;
}
};
int main()
{
set<info> s;
info fo;
fo.name = "jack";
fo.score = 80.5;
s.insert(fo);
fo.name = "tomi";
fo.score = 20.5;
s.insert(fo);
fo.name = "lucy";
fo.score = 60.5;
s.insert(fo);
set<info>::iterator it;
for (it = s.begin(); it != s.end(); it ++)
cout<<(*it).name<<":"<<(*it).score<<endl;
return 0;
}
=>
jack:80.5
lucy:60.5
tomi:20.5
二、multiset多重集合容器
與set不同的是multiset允許重復(fù)的元素鍵值插入。
multiset集合處理函數(shù)
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
int main()
{
multiset<string> ms;
//元素的插入
ms.insert("abc");
ms.insert("123");
ms.insert("aaa");
ms.insert("111");
ms.insert("123"); //重復(fù)元素
multiset<string>::iterator it;
for (it = ms.begin(); it != ms.end(); it ++)
cout<<*it<<endl;
//刪除元素，可以是某迭代器位置上的元素、等于某鍵值的元素、一個(gè)區(qū)間上的元素和清空集合
//刪除值為“123”的所有元素，返回刪除個(gè)數(shù)
int n = ms.erase("123");
cout << "total deleted:"<<n<<endl;
//輸出刪除后的剩余元素
for (it = ms.begin(); it != ms.end(); it ++)
cout<<*it<<endl;
//查找元素，找到則返回該鍵值的迭代器位置，否則返回該集合最后一個(gè)元素的下一位置，即end()
it = ms.find("aaa");
if (it != ms.end())
cout << *it <<endl;
else
cout << "not find it" <<endl;
it = ms.find("ccc");
if (it != ms.end())
cout << *it <<endl;
else
cout << "not find it" <<endl;
return 0;
}
