Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

c++选手的福利第二弹——自带平衡树set&&multiset

事出有因

今天上午的模拟题
我用了multiset
然后在复杂度分析的时候和assass_cannotin谈论复杂度
发现这个东西复杂度好玄学
毕竟set为c++选手提供了无限的便利
所以我来讲一讲这个东西

1.set&&multiset的正体??

这个我懒得自己写 而且我的定义也不准
其他的途径我也没有找到定义
其实它就是一个容器
ok这就是正体(就这么草率
反正又不考你定义对吧

2.stl的内部是怎么实现这个东西的呢

这个要详细讲了 涉及到原理了嘛
和vector、list不同,set、map都是关联式容器。set内部是基于红黑树实现的。插入和删除操作效率较高,因为只需要修改相关指针而不用进行数据的移动。
在进行数据删除操作后,迭代器会不会失效呢?删除set的数据时,实际的操作是删除红黑树中的一个节点,然后相关指针做相关调整。指向其他元素的迭代器还是指向原位置,并没有改变,所以删除一个节点后其他迭代器不会失效。list和map也是同样的道理。然而删除vector中的某个元素,vector中其他迭代器会失效,因为vector是基于数组的,删除一个元素后,后面的元素会往前移动,所以指向后面元素的迭代器会失效。
再稍微说一下迭代器的实现。迭代器是一个对象,vector的迭代器是封装了数组下标;list、map、set的迭代器是封装了元素节点的指针。
还有一点,从数学层面,set的一个集合,好比一个袋子里面装了好多个小球。但是红黑树是一种特殊的二叉搜索树,set中的元素根据其值的大小在红黑树中有特定的位置,是不可移动的。所以,1是search操作效率会很高O(log n),2是set中元素的值不可改变。
说的通俗点就是这是一棵红黑树
自带常数以及操作的平衡树

3.自带操作

既然提到了自带操作
那么set&&multiset都支持什么操作呢
begin()    返回set容器的第一个元素的地址
end()      返回set容器的最后一个元素地址
clear()    删除set容器中的所有的元素
empty()     判断set容器是否为空
max_size()   返回set容器可能包含的元素最大个数
size()      返回当前set容器中的元素个数
erase(it) 删除迭代器指针it处元素
insert(a) 插入某个元素
这里说一下迭代器的事情
迭代器是一个类似于指针的东西
用法跟指针类似
总的来说迭代器一般用于返回地址
以及用来遍历
这个后面再说

4.set&&multiset有区别么

这个一定是有的 不然分开干嘛
set我们叫做集合
这个set跟数学上面的集合挺像的
就是不允许出现重复的元素
multiset填补了这个空白
其余的貌似没有什么区别了
multiset大概常数略大?忽略吧

5.操作详细

5.1 构造、拷贝、析构

set c
产生一个空的set/multiset,不含任何元素
set c(op)
以op为排序准则,产生一个空的set/multiset
set c1(c2)
产生某个set/multiset的副本,所有元素都被拷贝
set c(beg,end)
以区间[beg,end)内的所有元素产生一个set/multiset
set c(beg,end, op)
以op为排序准则,区间[beg,end)内的元素产生一个set/multiset
c.~set()
销毁所有元素,释放内存
set
产生一个set,以(operator <)为排序准则
set<Elem,0p>
产生一个set,以op为排序准则

5.2 非变动性操作

c.size()
返回当前的元素数量
c.empty ()
判断大小是否为零,等同于0 == size(),效率更高
c.max_size()
返回能容纳的元素最大数量
c1 == c2
判断c1是否等于c2
c1 != c2
判断c1是否不等于c2(等同于!(c1==c2))
c1 < c2
判断c1是否小于c2
c1 > c2
判断c1是否大于c2
c1 <= c2
判断c1是否小于等于c2(等同于!(c2<c1))
c1 >= c2
判断c1是否大于等于c2 (等同于!(c1<c2))

5.3 特殊的搜寻函数

  sets和multisets在元素快速搜寻方面做了优化设计,提供了特殊的搜寻函数,所以应优先使用这些搜寻函数,可获得对数复杂度,而非STL的线性复杂度。比如在1000个元素搜寻,对数复杂度平均十次,而线性复杂度平均需要500次。
count (elem)
返回元素值为elem的个数
find(elem)
返回元素值为elem的第一个元素,如果没有返回end()
lower _bound(elem)
返回元素值为elem的第一个可安插位置,也就是元素值 >= elem的第一个元素位置
upper _bound (elem)
返回元素值为elem的最后一个可安插位置,也就是元素值 > elem 的第一个元素位置
equal_range (elem)
返回elem可安插的第一个位置和最后一个位置,也就是元素值==elem的区间

5.4 赋值

c1 = c2
将c2的元素全部给c1
c1.swap(c2)
将c1和c2 的元素互换
swap(c1,c2)
同上,全局函数

5.5 迭代器相关函数

  sets和multisets的迭代器是双向迭代器,对迭代器操作而言,所有的元素都被视为常数,可以确保你不会人为改变元素值,从而打乱既定顺序,所以无法调用变动性算法,如remove()。
c.begin()
返回一个随机存取迭代器,指向第一个元素
c.end()
返回一个随机存取迭代器,指向最后一个元素的下一个位置
c.rbegin()
返回一个逆向迭代器,指向逆向迭代的第一个元素
c.rend()
返回一个逆向迭代器,指向逆向迭代的最后一个元素的下一个位置

5.6 安插和删除元素

  必须保证参数有效,迭代器必须指向有效位置,序列起点不能位于终点之后,不能从空容器删除元素。
c.insert(elem)
插入一个elem副本,返回新元素位置,无论插入成功与否。
c.insert(pos, elem)
安插一个elem元素副本,返回新元素位置,pos为收索起点,提升插入速度。
c.insert(beg,end)
将区间[beg,end)所有的元素安插到c,无返回值。
c.erase(elem)
删除与elem相等的所有元素,返回被移除的元素个数。
c.erase(pos)
移除迭代器pos所指位置元素,无返回值。
c.erase(beg,end)
移除区间[beg,end)所有元素,无返回值。
c.clear()
移除所有元素,将容器清空

操作还是非常全的

6.复杂度

插入: O(logN)
查看:O(logN)
删除:O(logN)
其余的就很玄学了
不过大概都是log级别的

One Comment

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏