c++ STL中的set和multiset

1.结构

set和multiset会根据特定的排序原则将元素排序。两者不同之处在于，multisets允许元素重复，而set不允许重复。

set中的元素可以是任意类型的，但是由于需要排序，所以元素必须有一个序，即大小的比较关系,只要是assignable、copyable、comparable（根据某个排序准则）的型别T，都可以成为set或者multisets的元素。

2.底层实现

和所有的标准关联容器类似，sets和multisets通常以平衡二叉树完成。

自动排序的主要优点在于使二叉树搜寻元素具有良好的性能，在其搜索函数算法具有对数复杂度。但是自动排序也造成了一个限制，不能直接改变元素值，因为这样会打乱原有的顺序，要改变元素的值，必须先删除旧元素，再插入新元素。所以sets和multisets具有以下特点：
-不提供直接用来存取元素的任何操作元素。
-通过迭代器进行元素的存取。

3.成员函数

begin()--返回指向第一个元素的迭代器
clear()--清除所有元素
count()--返回某个值元素的个数
empty()--如果集合为空，返回true
end()--返回指向最后一个元素的迭代器
equal_range()--返回集合中与给定值相等的上下限的两个迭代器
erase()--删除集合中的元素
find()--返回一个指向被查找到元素的迭代器
get_allocator()--返回集合的分配器
insert()--在集合中插入元素
lower_bound()--返回指向大于（或等于）某值的第一个元素的迭代器
key_comp()--返回一个用于元素间值比较的函数
max_size()--返回集合能容纳的元素的最大限值
rbegin()--返回指向集合中最后一个元素的反向迭代器
rend()--返回指向集合中第一个元素的反向迭代器
size()--集合中元素的数目
swap()--交换两个集合变量
upper_bound()--返回大于某个值元素的迭代器
value_comp()--返回一个用于比较元素间的值的函数

什么时候需要用multiset？

当然是需要用set，但是又允许重复key存在的时候了。

什么时候用set？

需要随时往容器中插入元素，随时对元素进行快速查找，又需要按某种顺序对元素进行遍历的时候.

4.需要注意的地方

1.multiset::count(key)的返回值可能大于1。（因为插入了多个关键值）
2.multiset::size()的返回值是多重集合的势（cardinality），即multiset中元素的个数，而不是值的个数。比如，{1, 1, 2}的size是3，而不是2。
3.multiset::erase(key)会将对应的key全部删掉，所以对{1, 1, 2}调用erase(1)之后，它就变成了{2}。如果只想删除对应位置的key,erase的参数可以设置为迭代器，比如erase(lower_bound(n)),意味删除大于或等于值为n的第一个元素。
4.只要key存在于集合中，set::equal_range(key)的返回值pair<iterator1, iterator2>总是会有++iterator1 == iterator2。但是对multiset来说就不一定了。

巴特西