C++ STL：SET & MULTISET - 算法

# 定义

方式	效果
`set <数据类型名> 集合名;`	先定义一个容器，容器内无任何元素
`set <数据类型名> 集合名(另一个集合名);`	定义一个集合并用另一个集合初始化（只能是数据类型相同的集合，不能是数组）
`set <数据类型名> 集合名(另一个集合名.begin(), 另一个集合名.end());`	定义一个集合并用另一个集合初始化（只能是数据类型相同的集合，不能是数组）
`set <数据类型名> 集合名[集合数量];`	定义集合数组
`set <Elem>`	产生一个 set，以 (operator <) 为排序准则
`set <Elem, cmp>`	产生一个 set，以 cmp 为排序准则

set 和 multiset 都是平衡树， $O(\log n)$ 级别查找。

操作	效果
count(elem)	返回元素值为 elem 的个数
find(elem)	返回元素值为 elem 的第一个元素，如果没有返回 end ()
lower_bound(elem)	返回元素值为 elem 的第一个可安插位置，也就是元素值 >= elem 的第一个元素位置
upper_bound(elem)	返回元素值为 elem 的最后一个可安插位置，也就是元素值 > elem 的第一个元素位置
equal_range(elem)	返回 elem 可安插的第一个位置和最后一个位置，也就是元素值 == elem 的区间

sets 和 multisets 的迭代器是双向迭代器，对迭代器操作而言，所有的元素都被视为常数，可以确保你不会人为改变元素值，从而打乱既定顺序，所以无法调用变动性算法，如 remove() 。

必须保证参数有效，迭代器必须指向有效位置，序列起点不能位于终点之后，不能从空容器删除元素。

操作	返回值	效果
c.insert(elem)	`pair <iterator, bool>`	插入一个 elem 副本
c.insert(pos, elem)	`iterator`	安插一个 elem 元素副本，返回元素的迭代器。pos 为搜索起点，提升插入速度。
c.insert(beg,end)	`void`	将区间 [beg,end) 所有的元素安插到 c。
c.erase(elem)	无符号整数	删除与 elem 相等的所有元素，返回被移除的元素个数。
c.erase(pos)	`void`	移除迭代器 pos 所指位置元素。
c.erase(beg,end)	`void`	移除区间 [beg,end) 所有元素，返回 `void` 。
c.clear()	`void`	移除所有元素，将容器清空

set::insert(key) 的返回值是一个 pair<iterator, bool> ，其中 pair 中的 bool 成员表明了 key 被插入之前，set 中是否已存在相同的 key。如果 set 中已经存在相同 key 的元素，那么插入操作是会失败的，新的元素不会被插进去。而 multiset::insert(key) 的返回值只是一个 iterator，插入操作总是会成功的。
multiset::count(key) 的返回值可能大于 1。
multiset::size() 的返回值是 multiset 中元素的个数，而不是值的个数。比如，{1, 1, 2} 的 size 是 3，而不是 2。
multiset::erase(key) 会将对应的 key 全部删掉，所以对 {1, 1, 2} 调用 erase(1) 之后，它就变成了 {2}。
只要 key 存在于集合中， set::equal_range(key) 的返回值 pair<iterator1, iterator2> 总是会有 ++iterator1 == iterator2 。但是对 multiset 来说就不一定了。