插入的key已经有了,就返回false,没有就true,
改造一下:也可以
自己走隐式类型转换,构造iteraator要用当前节点和 根节点指针
相等了就插入失败,返回相等的
这里也是插入成功,返回新插入的节点,新节点不能用current,因为父亲叔叔 红的要变色连续往上处理,所以
newnode记录一下,不然current连续变色处理,不一定是新节点,neewnode记录新节点就行
这些地方就都得跟着改
库里set这里iterator用的const iterator支持这个地方就会有坑,因为 底层是普通迭代器,就得支持腹痛迭代器到const 迭代器的转换。
然后搭operator【】:
注意两个pair,
可以继续加拷贝析构
哈希
两个容器C++11的
因为set底层是搜索树,所以是有序地,而undersort是无序的,
去掉unorder就是有序,
怎么去重 如果有了就插入不就去了
哈希更快,绝多数场景可以用unorder set 和unordermap
数据有序情况:
有序用 map set 其余情况可以用 unorderset unordermap
降序可以给greater仿函数,里面用一个仿函数,换参数位置就可以实现大于小于,
比如说计数排序,
数据比较分散就不行,适合数据范围比较集中的整形,
假设32个位,模后十个位,前22个位想不想同不重要,后十个值相同摸出来都是一样的,尽可能要避免2的次方。取13就很好
前面都是零后面16位都是1,可与 就取后16位了。但是后16位相同的值不就冲突了, 就把前16位取出来给给key'然后两个异或
这样写很好,很活
但是这里真正问题是后16位相同就都冲突了,前面的位没参与,尽可能让更多位参与运算就可以了,位不同参与运算的结果就更分散,
此时这个值就不是只有后16位参与运算了就打破了只用2的x次方。
总结:第一种
第二种:就取2的x次方也没问题,尽可能让所有位参与运算。两个不同值运算结果更有可能不一样,哈希函数是减小冲突,概率降低了很多很多。