1、 set/multiset容器基本概念

　　所有元素都會根據(jù)元素的鍵值自動被排序。

　　set/multiset屬于關(guān)聯(lián)式容器，底層結(jié)構(gòu)是用二叉樹實現(xiàn)。

　　2、set容器特點

　　set的元素不像map那樣可以同時擁有實值和鍵值，set的元素即是鍵值又是實值。

　　set不允許兩個元素有相同的鍵值。

　　不能通過set的迭代器改變set元素的值。因為set元素值就是其鍵值，關(guān)系到set元素的排序規(guī)則。如果任意改變set元素值，會嚴重破壞set組織。

　　set容器的迭代器為可讀迭代器。

　　3、set/multiset容器區(qū)別

　　multiset特性及用法和set完全相同，唯一的差別在于它允許鍵值重復(fù)。set和multiset的底層實現(xiàn)是紅黑樹，紅黑樹為平衡二叉樹的一種。 樹的簡單知識： 二叉樹就是任何節(jié)點最多只允許有兩個字節(jié)點。 分別是左子結(jié)點和右子節(jié)點。

　　二叉樹示意圖

　　二叉搜索樹，是指二叉樹中的節(jié)點按照一定的規(guī)則進行排序，使得對二叉樹中元素訪問更加高效。二叉 搜索樹的放置規(guī)則是：任何節(jié)點的元素值一定大于其左子樹中的每一個節(jié)點的元素值，并且小于其右子樹的值。因此從根節(jié)點一直向左走，一直到無路可走，即得到最小值，一直向右走，直至無路可走，可得到最大值。那么在兒茶搜索樹中找到最大元素和最小元素是非常簡單的事情。下圖為二叉搜索樹：

　　上面我們介紹了二叉搜索樹，那么當一個二叉搜索樹的左子樹和右子樹不平衡的時候，那么搜索依據(jù)上圖表示，搜索9所花費的時間要比搜索17所花費的時間要多，由于我們的輸入或者經(jīng)過我們插入或者刪除操作，二叉樹失去平衡，造成搜索效率降低。 所以我們有了一個平衡二叉樹的概念，所謂的平衡不是指的完全平衡。

　　4、set/multiset容器常用API

　　4.1set/multiset構(gòu)造函數(shù)

set<T> st;//set默認構(gòu)造函數(shù)：

mulitset<T> mst; //multiset默認構(gòu)造函數(shù): set(const set &st);//拷貝構(gòu)造函數(shù)

　　4.2set賦值操作

set& operator=(const set &st);//重載等號操作符 swap(st);//交換兩個集合容器

　　4.3set大小操作

size();//返回容器中元素的數(shù)目 empty();//判斷容器是否為空

　　4.4set插入和刪除操作

insert(elem);//在容器中插入元素。 clear();//清除所有元素 erase(pos);//刪除pos迭代器所指的元素，返回下一個元素的迭代器。 erase(beg, end);//刪除區(qū)間[beg,end)的所有元素 ，返回下一個元素的迭代器。 erase(elem);//刪除容器中值為elem的元素。

　　4.5set查找操作

find(key);//查找鍵key是否存在,若存在，返回該鍵的元素的迭代器；若不存在，返回set.end(); count(key);//查找鍵key的元素個數(shù) lower_bound(keyElem);//返回第一個key>=keyElem元素的迭代器。 upper_bound(keyElem);//返回第一個key>keyElem元素的迭代器。 equal_range(keyElem);//返回容器中key與keyElem相等的上下限的兩個迭代器

　　使用案例：

#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容器 會根據(jù)鍵值 自動排序

    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沒有找到相關(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)計元素在set容器的個數(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、常見應(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ī)則：必須是類型 但同時又可以執(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、對組(補充)

　　對組(pair)將一對值組合成一個值，這一對值可以具有不同的數(shù)據(jù)類型，兩個值可以分別用pair的兩個公 有屬性fifirst和second訪問。 類模板：templatestruct pair. 如何創(chuàng)建對組？

//第一種方法創(chuàng)建一個對組

pair<string, int> pair1(string("name"), 20); 

cout << pair1.first << endl; //訪問pair第一個值

cout << pair1.second << endl;//訪問pair第二個值 //第二種

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)的問題，歡迎咨詢千鋒教育在線名師，如果想要了解我們的師資、課程、項目實操的話可以點擊咨詢課程顧問，獲取試聽資格來試聽我們的課程，在線零距離接觸千鋒教育大咖名師，讓你輕松從入門到精通。