一、set集合容器

set实现了红黑树的平衡二叉检索树，插入元素时会自动调整二叉树，使得每个子树根节点的键值大于左子树所有节点的键值，小于右子树所有节点的键值，且不会重复插入键值相同的元素。同时保证根节点左右子树的高度相等。这样二叉树高度最小，检索速度最快。

衡二叉检索树的检索使用中序遍历算法，效率高于vector、deque、list等容器，multiset、map、multimap的内部结构也是平衡二叉检索树。

set集合处理函数

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

int main()
{
    //构建set集合，指定元素类型，此时为空
    set<int> s;

    //插入元素
    s.insert(8);
    s.insert(1);
    s.insert(12);
    s.insert(8);        //重复不会插入

     //会按中序遍历，即从小到大输出键值
    set<int>::iterator it;
    for (it = s.begin(); it != s.end(); it ++)
        cout << *it <<" ";
    cout<<endl;

    //元素的检索，找到查找的键值返回该键值的迭代器位置，否则返回该集合最后一个元素的下一位置，即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;

    //元素删除，删除对象可以是某迭代器位置上的元素、等于某键值的元素、一个区间上的元素和清空集合
    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;
}

自定义比较函数，默认的比较函数按键值从小到大的顺序插入元素，例如要换成从大到小的顺序，有两种自定义方法：

若元素不是结构体，可编写比较函数

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

//自定义比较函数，重载“（）”操作符
struct cmp
{
    bool operator()(const int &a, const int &b)
    {
        if (a != b)
            return a > b;
        else
            return a > b;
    }
};

int main()
{
    //构建set集合，指定元素类型，此时为空
    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

若元素是结构体，可直接把比较函数写在结构体中

#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允许重复的元素键值插入。

multiset集合处理函数

#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");        //重复元素
    multiset<string>::iterator it;
    for (it = ms.begin(); it != ms.end(); it ++)
        cout<<*it<<endl;

    //删除元素，可以是某迭代器位置上的元素、等于某键值的元素、一个区间上的元素和清空集合
    //删除值为“123”的所有元素，返回删除个数
    int n = ms.erase("123");
    cout << "total deleted:"<<n<<endl;

    //输出删除后的剩余元素
    for (it = ms.begin(); it != ms.end(); it ++)
        cout<<*it<<endl;

    //查找元素，找到则返回该键值的迭代器位置，否则返回该集合最后一个元素的下一位置，即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;
}