[C++]STL-set/multiset容器

set/multisite容器

set/multisite容器的特性是所有元素会根据元素的值自动进行排序。set/multisite容器是关联容器

set底层机制为RB-tree（红黑树，平衡二叉树的一种）。其查找效率非常高，set不允许有重复元素，multisite允许有重复元素

set容器会自动进行排序，所以只提供了insert方法添加数据

不可以通过set的迭代器改变元素的值

#include<iostream>
#include<set>   //set/multiset都是一个头文件，只需要引入set即可
using namespace std;
//set容器

void PrintSet(set<int> s) {
    for (set<int>::iterator it = s.begin(); it != s.end(); it++) {
        cout << (*it) << "  ";
    }
    cout << endl;
}

//set容器初始化
void SetTest1() {
    set<int> s1;
    s1.insert(56);  //自动进行排序，默认从小到大
    s1.insert(89);
    s1.insert(12);
    s1.insert(2);
    PrintSet(s1);




    //set容器赋值操作
    set<int> s2 = s1;
    set<int> s3 = { 10,56,44,23 };
    s3.swap(s2);  //交换容器内所有元素
    //size，empty，clear函数效果与其他容器一致

    //删除操作
    s1.erase(s1.begin());  //删除指定迭代器位置的元素
    s1.erase(89);  //删除指定值的元素
    PrintSet(s1);
    PrintSet(s2);
    PrintSet(s3);

    //改变默认排序


}

//set查找操作
void SetTest2() {
    //通过实值查找
    set<int> s1 = { 10,56,44,23 };
    set<int>::iterator it = s1.find(23);  
    /*
    find()函数若找到指定值的元素，
    则返回该元素的迭代器，
    若没有找到指定值元素
    则返回容器的end值
    */
    if (it != s1.end()) {
        cout << "容器中存在:" << (*it) << endl;
    }
    else {
        cout << "不存在！" << endl;
    }
    //lower_bound(keyElem)，返回第一个大于等于keyElem的key的迭代器
    //upper_bound(keyElem),返回第一个大于keyElem的key的迭代器
    it = s1.lower_bound(25);
    if (it != s1.end()) {
        cout << "容器中第一个大于等于25的数为：" << (*it) << endl;
    }
    else {
        cout << "容器中所有数都小于25" << endl;
    }
    //equal_range(),返回两个值，分别是lower_bound和upper_bound的返回值
    //返回的类型是对组pair
    pair<set<int>::iterator,set<int>::iterator> myret = s1.equal_range(23);
    //判断是否得到相应值
    if (myret.first != s1.end()) {
        cout << "容器中第一个大于等于25的数为：" << *(myret.first) << endl;
    }
    else {
        cout << "容器中所有数都大于25" << endl;
    }
    if (myret.second != s1.end()) {
        cout << "容器中第一个大于25的数为：" << *(myret.second) << endl;
    }
    else {
        cout << "容器中所有数都小于等于25" << endl;
    }

}



int main() {
    SetTest2();

    return 0;
}

对组

对组(pair)将一对值组合成一个值，这一对值可以具有不同的数据类型，两个值可以分别用pair的共有函数first和second访问

类模板

template<class T1 , class T2> struct pair

//pair对组练习
void PairTest() {
    //对组构造方法
    pair<string, int> pair1("Leslie",45);
    cout << pair1.first << "'s age is " << pair1.second << endl;

    pair<string, int> pair2 = make_pair("Bob", 26);
    cout << pair2.first << "'s age is " << pair2.second << endl;

    pair<string, int> pair3 = pair2;
}

//仿函数
class MyCompare {
public:
    bool operator()(int v1, int v2)const
    {
        return v1 > v2;
    }
};

//更改默认排序方式
void SetTest3() {
    set<int, MyCompare> s1;   //重新定义排序规则，使其从大到小排序
    s1.insert(56);
    s1.insert(89);
    s1.insert(12);
    s1.insert(2);
    for (set<int>::iterator it=s1.begin(); it != s1.end(); it++) {
        cout << *it << "  ";
    }
    cout << endl;

}

自定义类与set容器

#include<iostream>
#include<set>   //set/multiset都是一个头文件，只需要引入set即可
using namespace std;

class Person {
public:
    int mId;
    int mAge;
    Person(int id, int age) : mId(id), mAge(age) {}
    Person(){}
};

class PersonRank {
public:
    bool operator()(Person p1, Person p2) const  //注意，在VS中默认这里需要加const
    {
        return p1.mAge > p2.mAge;  //按照年龄从大到小
    }

};


void SetTest5() {  //对于自定义类的排序，由于系统不知道如何进行，所以需要我们自行制定排序方式
    set<Person, PersonRank> sp;
    Person p1(10, 15), p2(11, 19), p3(45, 88);
    sp.insert(p1);
    sp.insert(p2);
    sp.insert(p3);
    for (set<Person>::iterator it = sp.begin(); it != sp.end(); it++) {
        cout << "年龄：" << (*it).mAge << " ID：" << (*it).mId << endl;
    }

    //查找
    Person p4(20, 15);
    /*
    可以看到，set容器中并没有p4(20,15)
    但还是找到了与之“相同”的元素
    事实上，由于我们定义了排序的方法PersonRank
    所以find函数在寻找时，默认采用判断mAge值的方法决定两个元素是否相等
    所以，只要传入的年龄相同，find函数都找到与之相同的元素
    */
    set<Person>::iterator ret=sp.find(p4);
    if (ret == sp.end()) {
        cout << "没有找到" << endl;
    }
    else {
        cout << "年龄：" << (*ret).mAge << " ID：" << (*ret).mId << endl;
    }
}


int main() {
    SetTest5();
    return 0;
}