STL学习笔记（9）常用容器 set/multiset
STL学习笔记（9）常用容器 set/multiset
set/multiset 容器基本概念
Set 的特性是：所有元素都会根据元素的键值自动被排序。Set 的元素不像 map 那样可以同时拥有实值和键值，set 的元素即是键值又是实值。Set 不允许两个元素有相同的键值。 我们可以通过 set 的迭代器改变 set 元素的值吗？不行，因为 set 元素值就是其键值，关系到 set 元素的排序规则。 如果任意改变 set 元素值，会严重破坏 set 组织。换句话说，set 的 iterator 是一种 const_iterator. set 拥有和 list 某些相同的性质，当对容器中的元素进行插入操作或者删除操作的时候，操作之前所有的迭代器， 在操作完成之后依然有效，被删除的那个元素的迭代器必然是一个例外。
multiset 特性及用法和 set 完全相同，唯一的差别在于它允许键值重复。set 和 multiset 的底层实现是红黑树，红黑 树为平衡二叉树的一种。
树的简单知识：
二叉树就是任何节点最多只允许有两个字节点。分别是左子结点和右子节点。
二叉搜索树，是指二叉树中的节点按照一定的规则进行排序，使得对二叉树中元素访问更加高效。二叉搜索树的 放置规则是：任何节点的元素值一定大于其左子树中的每一个节点的元素值，并且小于其右子树的值。因此从根 节点一直向左走，一直到无路可走，即得到最小值，一直向右走，直至无路可走，可得到最大值。那么在儿茶搜 索树中找到最大元素和最小元素是非常简单的事情。下图为二叉搜索树：
上面我们介绍了二叉搜索树，那么当一个二叉搜索树的左子树和右子树不平衡的时候，那么搜索依据上图表示， 搜索 9 所花费的时间要比搜索 17 所花费的时间要多，由于我们的输入或者经过我们插入或者删除操作，二叉树失 去平衡，造成搜索效率降低。 所以我们有了一个平衡二叉树的概念，所谓的平衡不是指的完全平衡。
set 常用操作
1. set 构造函数
set<T> st;//set 默认构造函数：
mulitset<T> mst; //multiset 默认构造函数:
set(const set &st);//拷贝构造函数 2. set 赋值操作
set& operator=(const set &st);//重载等号操作符
swap(st);//交换两个集合容器 3. set 大小操作
size();//返回容器中元素的数目
empty();//判断容器是否为空 4. set 插入和删除操作
insert(elem);//在容器中插入元素。
clear();//清除所有元素
erase(pos);//删除 pos 迭代器所指的元素，返回下一个元素的迭代器。
erase(beg, end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
erase(elem);//删除容器中值为 elem 的元素。 5. set 查找操作
find(key);//查找键 key 是否存在,若存在，返回该键的元素的迭代器；若不存在，返回 set.end();
count(key);//查找键 key 的元素个数
lower_bound(keyElem);//返回第一个 key>=keyElem 元素的迭代器。
upper_bound(keyElem);//返回第一个 key>keyElem 元素的迭代器。
equal_range(keyElem);//返回容器中 key 与 keyElem 相等的上下限的两个迭代器。例子
//插入操作返回值
void test01()
{
set<int> s;
pair<set<int>::iterator, bool> ret = s.insert(10);
if (ret.second)
{
cout << "插入成功:" << *ret.first << endl;
}
else
{
cout << "插入失败:" << *ret.first << endl;
}
ret = s.insert(10);
if (ret.second)
{
cout << "插入成功:" << *ret.first << endl;
}
else
{
cout << "插入失败:" << *ret.first << endl;
}
}
struct MyCompare02
{
bool operator()(int v1, int v2) { return v1 > v2; }
};
//set 从大到小
void test02()
{
srand((unsigned int)time(NULL)); //我们发现 set 容器的第二个模板参数可以设置排序规则，默认规则是 less<_Kty>
set<int, MyCompare02> s;
for (int i = 0; i < 10; i++)
{
s.insert(rand() % 100);
}
for (set<int, MyCompare02>::iterator it = s.begin(); it != s.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
//set 容器中存放对象
class Person
{
public:
Person(string name, int age)
{
this->mName = name;
this->mAge = age;
}
public:
string mName;
int mAge;
};
struct MyCompare03
{
bool operator()(const Person &p1, const Person &p2)
{
return p1.mAge > p2.mAge;
}
};
void test03()
{
set<Person, MyCompare03> s;
Person p1("aaa", 20);
Person p2("bbb", 30);
Person p3("ccc", 40);
Person p4("ddd", 50);
s.insert(p1);
s.insert(p2);
s.insert(p3);
s.insert(p4);
for (set<Person, MyCompare03>::iterator it = s.begin(); it != s.end(); it++)
{
cout << "Name:" << it->mName << " Age:" << it->mAge << endl;
}
}