# C++ STL:SET & MULTISET

# 定义

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

# 操作

# 非变动性操作

操作效果
c.size()返回当前的元素数量
c.empty ()判断 set 是否为空,等同于 c.size () == 0,效率更高
c.max_size()返回能容纳的元素最大数量
c1 == c2判断 c1 是否等于 c2

# 查找

set 和 multiset 都是平衡树,O(logn)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()

操作效果
c1 = c2将 c2 的元素全部给 c1
c1.swap(c2)将 c1 和 c2 的元素互换
swap(c1, c2)同上,全局函数
c.begin()
c.end()
c.rbegin()
c.rend()

# 安插和删除元素

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

操作返回值效果
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 与 multiset 的异同

  • 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 来说就不一定了。
更新于