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(\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来说就不一定了。