1、 set/multiset容器基本概念
所有元素都會(huì)根據(jù)元素的鍵值自動(dòng)被排序。
set/multiset屬于關(guān)聯(lián)式容器，底層結(jié)構(gòu)是用二叉樹(shù)實(shí)現(xiàn)。
2、set容器特點(diǎn)
set的元素不像map那樣可以同時(shí)擁有實(shí)值和鍵值，set的元素即是鍵值又是實(shí)值。
set不允許兩個(gè)元素有相同的鍵值。
不能通過(guò)set的迭代器改變set元素的值。因?yàn)閟et元素值就是其鍵值，關(guān)系到set元素的排序規(guī)則。如果任意改變set元素值，會(huì)嚴(yán)重破壞set組織。
set容器的迭代器為可讀迭代器。
3、set/multiset容器區(qū)別
multiset特性及用法和set完全相同，唯一的差別在于它允許鍵值重復(fù)。set和multiset的底層實(shí)現(xiàn)是紅黑樹(shù)，紅黑樹(shù)為平衡二叉樹(shù)的一種。 樹(shù)的簡(jiǎn)單知識(shí)： 二叉樹(shù)就是任何節(jié)點(diǎn)最多只允許有兩個(gè)字節(jié)點(diǎn)。 分別是左子結(jié)點(diǎn)和右子節(jié)點(diǎn)。
二叉樹(shù)示意圖
二叉搜索樹(shù)，是指二叉樹(shù)中的節(jié)點(diǎn)按照一定的規(guī)則進(jìn)行排序，使得對(duì)二叉樹(shù)中元素訪問(wèn)更加高效。二叉 搜索樹(shù)的放置規(guī)則是：任何節(jié)點(diǎn)的元素值一定大于其左子樹(shù)中的每一個(gè)節(jié)點(diǎn)的元素值，并且小于其右子樹(shù)的值。因此從根節(jié)點(diǎn)一直向左走，一直到無(wú)路可走，即得到最小值，一直向右走，直至無(wú)路可走，可得到最大值。那么在兒茶搜索樹(shù)中找到最大元素和最小元素是非常簡(jiǎn)單的事情。下圖為二叉搜索樹(shù)：
上面我們介紹了二叉搜索樹(shù)，那么當(dāng)一個(gè)二叉搜索樹(shù)的左子樹(shù)和右子樹(shù)不平衡的時(shí)候，那么搜索依據(jù)上圖表示，搜索9所花費(fèi)的時(shí)間要比搜索17所花費(fèi)的時(shí)間要多，由于我們的輸入或者經(jīng)過(guò)我們插入或者刪除操作，二叉樹(shù)失去平衡，造成搜索效率降低。 所以我們有了一個(gè)平衡二叉樹(shù)的概念，所謂的平衡不是指的完全平衡。
4、set/multiset容器常用API
4.1set/multiset構(gòu)造函數(shù)
set<T> st;//set默認(rèn)構(gòu)造函數(shù)：
mulitset<T> mst; //multiset默認(rèn)構(gòu)造函數(shù): set(const set &st);//拷貝構(gòu)造函數(shù)
4.2set賦值操作
set& operator=(const set &st);//重載等號(hào)操作符 swap(st);//交換兩個(gè)集合容器
4.3set大小操作
size();//返回容器中元素的數(shù)目 empty();//判斷容器是否為空
4.4set插入和刪除操作
insert(elem);//在容器中插入元素。 clear();//清除所有元素 erase(pos);//刪除pos迭代器所指的元素，返回下一個(gè)元素的迭代器。 erase(beg, end);//刪除區(qū)間[beg,end)的所有元素 ，返回下一個(gè)元素的迭代器。 erase(elem);//刪除容器中值為elem的元素。
4.5set查找操作
find(key);//查找鍵key是否存在,若存在，返回該鍵的元素的迭代器；若不存在，返回set.end(); count(key);//查找鍵key的元素個(gè)數(shù) lower_bound(keyElem);//返回第一個(gè)key>=keyElem元素的迭代器。 upper_bound(keyElem);//返回第一個(gè)key>keyElem元素的迭代器。 equal_range(keyElem);//返回容器中key與keyElem相等的上下限的兩個(gè)迭代器
使用案例：
#include <iostream>#include <set>using namespace std;void printSetInt(set<int> &s){
set<int>::iterator it=s.begin();
for(;it!=s.end();it++)
{
cout<<*it<<" ";
}
cout<<endl;}
void test(){
set<int> s;
//set容器 會(huì)根據(jù)鍵值 自動(dòng)排序
s.insert(20);
s.insert(50);
s.insert(40);
s.insert(30);
s.insert(10);
printSetInt(s);
set<int>::iterator p = s.begin();
//*p = 100;//set容器的迭代器為只讀迭代器 不允許修改內(nèi)容
set<int>::const_iterator ret;
//如果find沒(méi)有找到相關(guān)數(shù)據(jù) 返回結(jié)束迭代器end
ret = s.find(30);
if(ret == s.end())
{
cout<<"未找到相關(guān)數(shù)據(jù)"<<endl;
}
else
{
cout<<"找到數(shù)據(jù)為:"<<*ret<<endl;
}
//set容器的鍵值 唯一的。
//count統(tǒng)計(jì)元素在set容器的個(gè)數(shù)：結(jié)果只能是1 或 0
cout<<s.count(100)<<endl;//0
set<int> s1;
s1.insert(10);//ok
s1.insert(20);//ok
s1.insert(10);//err
s1.insert(10);//err
s1.insert(30);//ok
printSetInt(s1);//10 20 30}
int main(int argc, char *argv[]){
test();
return 0;}
5、常見(jiàn)應(yīng)用
5.1set容器的排序規(guī)則(仿函數(shù) 更改 set的排序規(guī)則)
#include <iostream>#include <set>using namespace std;
//仿函數(shù)class MyCompare{public:
bool operator()(int v1, int v2)
{
return v1>v2;
}};
void printSetInt01(set<int, MyCompare> &s){
set<int, MyCompare>::iterator it=s.begin();
for(;it != s.end(); it++)
{
cout<<*it<<" ";
}
cout<<endl;}void test01(){
//排序規(guī)則：必須是類(lèi)型 但同時(shí)又可以執(zhí)行函數(shù)
//set<int,排序規(guī)則> s;
set<int, MyCompare> s;
s.insert(5);
s.insert(2);
s.insert(3);
s.insert(4);
s.insert(1);
printSetInt01(s);}int main(int argc, char *argv[]){
test01();
return 0;}
5.2set容器 存放自定義數(shù)據(jù) 必須指定 排序規(guī)則。
#include <iostream>#include <set>using namespace std;
class Person{public:
string name;
int num;
int age;public:
Person(string name, int num, int age)
{
//this‐>
this->name = name;
this->num =num;
this->age = age;
}};class MyComparePerson{public:
bool operator()(Person ob1, Person ob2)
{
return ob1.num < ob2.num;
}};void printSetPerson(set<Person, MyComparePerson> &s){
set<Person, MyComparePerson>::iterator it=s.begin();
for(;it != s.end(); it++)
{
cout<<it->name<<", "<<it->num<<", "<<it->age<<endl;
}
cout<<endl;}
void test(){
set<Person, MyComparePerson> s;
s.insert(Person("lucy", 101, 19));
s.insert(Person("bob", 107, 19));
s.insert(Person("tom", 105, 19));
s.insert(Person("hehe", 104, 19));
printSetPerson(s);}int main(int argc, char *argv[]){
test();
return 0;}
5.3multiset容器使用(允許重復(fù))
#include <iostream>#include <set>using namespace std;
void printSetInt(multiset<int> &s){
multiset<int>::iterator it=s.begin();
for(;it != s.end(); it++)
{
cout<<*it<<" ";
}
cout<<endl;}void test(){
multiset<int> s;
s.insert(10);
s.insert(10);
s.insert(10);
printSetInt(s);}int main(int argc, char *argv[]){
test();
return 0;}
6、對(duì)組(補(bǔ)充)
對(duì)組(pair)將一對(duì)值組合成一個(gè)值，這一對(duì)值可以具有不同的數(shù)據(jù)類(lèi)型，兩個(gè)值可以分別用pair的兩個(gè)公 有屬性fifirst和second訪問(wèn)。 類(lèi)模板：templatestruct pair. 如何創(chuàng)建對(duì)組？
//第一種方法創(chuàng)建一個(gè)對(duì)組
pair<string, int> pair1(string("name"), 20);
cout << pair1.first << endl; //訪問(wèn)pair第一個(gè)值
cout << pair1.second << endl;//訪問(wèn)pair第二個(gè)值 //第二種
pair<string, int> pair2 = make_pair("name", 30);
cout << pair2.first << endl;
cout << pair2.second << endl; //pair=賦值
pair<string, int> pair3 = pair2;
cout << pair3.first << endl; cout << pair3.second << endl;
更多關(guān)于只能物聯(lián)網(wǎng)培訓(xùn)的問(wèn)題，歡迎咨詢(xún)千鋒教育在線名師，如果想要了解我們的師資、課程、項(xiàng)目實(shí)操的話可以點(diǎn)擊咨詢(xún)課程顧問(wèn)，獲取試聽(tīng)資格來(lái)試聽(tīng)我們的課程，在線零距離接觸千鋒教育大咖名師，讓你輕松從入門(mén)到精通。
京公網(wǎng)安備 11010802030320號(hào)