一、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;
}
