网站东莞优化建设,建设信用交通网站 省,泉州有哪些做网站的,制作班徽的小程序1.set和map存在的意义
#xff08;1#xff09;set和map的底层都是二叉搜索树#xff0c;可以达到快速排序#xff08;当我们按照迭代器的顺序来遍历set和map#xff0c;其实是按照中序来遍历的#xff0c;是排过序的#xff09;、去重、搜索的目的。
#xff08;21set和map的底层都是二叉搜索树可以达到快速排序当我们按照迭代器的顺序来遍历set和map其实是按照中序来遍历的是排过序的、去重、搜索的目的。
2优先级队列priority_queue也有类似的功能但是它的底层是数组在插入删除频繁的情况下效率降低且它的数据结构是堆在排序上效率还行但在搜索上就无能为力了。
3在C数据结构重要知识点1我就讲过二叉搜索树的特性在退化的情况下搜索效率低下所以要引入AVL树、红黑树这样的平衡树来解决问题。set和map就引入了红黑树使得这两个容器的搜索效率很高。
4set和map有什么区别呢其实就是分别对应key和key-value模型。set是针对key单个数据的二叉搜索树而map是针对key-value那样的键值对的二叉搜索树。
5两种容器
序列式容器vector、list对存储数据的顺序的要求不高注意这句话的意思是在序列式容器中换两个数据虽然可能会影响到它的功能比如本来是降序排列的vector现在被打乱了但不影响容器结构本身vector还叫vector关联式容器map、set对数据顺序有强关联性结构靠数据支撑如果你随便换两个数据的位置那么整个容器就崩了而且无法修复。
2.set
set的底层引入了红黑树大致和key模型的二叉搜索树一样是借助二叉树的特性来存放数据达到排序和搜索的功能的。但是在接口上和我们上篇文章分享的又不一样
1模板参数、仿函数的应用 第一个模板参数要存放数据的类型可以是int这样的内置类型也可以是自定义类型
第三个模板参数基本不用管
第二个模板参数默认是lessT在用迭代器遍历时是从小到大注意我们前面讲的优先级队列priority_queue默认也是lessT但对应的是大堆。我们也可以自己写一个仿函数作为set的第二个模板参数自定义规则不过自定义仿函数的坑有点多下面分享一下需要注意的点加深对仿函数的理解。
先看以下代码
#include iostream
#include string
#include set
using namespace std;templateclass T
struct Compare
{bool operator()(const T t1, const T t2) const{return t1 t2;}
};template
struct Comparestring
{bool operator()(const string s1, const string s2) const{return (s1.size() s2.size()) || (s1.size() s2.size() s1 s2);}
};int main()
{setint, Compareint s1;s1.insert(1);s1.insert(2);s1.insert(3);setstring, Comparestring s2;s2.insert(zzzzzzz);s2.insert(aaaaaaa);s2.insert(bb);for (const auto e : s1){cout e ;}cout endl;for (const auto e : s2){cout e ;}return 0;
}
输出结果是 为什么对于s1是从大排到小呢为什么s2是这样排的呢它们是怎样控制的呢
在默认的情况下是less对应的是从小排到大即小的元素在大的元素前面因此我们可以这样分析 再分析我们的 在写仿函数的时候特别注意举一反三我上面两张图都提到的“返回true是谁在前”并不适用于所有情况map和set都遵循返回true时到底是t1在前还是t2在前要自己判断。借助默认排序方式和仿函数类型可以判断如果set默认仿函数是greater而默认访问是从小到大那么自己写仿函数时就应该遵循“返回true时是t2第二个函数参数在前”来写代码了。
我们并不知道STL里面到底是怎样排序的所以从细节推理出排序结果很重要看似很简单但一定不能含糊。
还有个细节在自己写仿函数时要把重载函数定义为const对象否则是编译不通过的。 2构造函数 总体分为三类空构造、拷贝构造、迭代器构造
最后的内存池相关的参数不管它倒数第二个comp只能是显式实例化容器时使用的仿函数不过一般也不写因为编译器会自己生成对应的仿函数 3insert、pair insert最常用的就是第一个第二第三个基本不用。但是返回值pairiterator, bool是什么呢 pair是一个模板类叫键值对它有两个成员变量一个叫first另一个叫secondfirst和second构成一一对应的关系first相当于keysecond相当于value在map中也用到了它。
要创建一个pair对象也很简单 pair和我们之前学的容器不同pair只是一个存储数据的类型它的底层非常简单它存在的意义就是将key和value联系起来根本不存在增删查改。
作为一个专门用于存储数据的类型它也有自己的判断大小的方式也很好理解。当first和second都相同时pair相同first大的pair就大first都相同时second大的pair就大。 了解完pair之后我们可以去研究set的insert了 val就是我们想插入set的数据那么返回的键值对有什么价值呢 这也是set和map可以实现去重的原因之一除此以外像find之类的函数也可以通过insert变相实现了 4erase、count、multiset 常用的是第二种直接删除某个值返回值是删除的值的个数。这个时候我们就有疑问了直接用bool不好吗删除了就是true删不掉就是false这是为了multiset准备的。
multiset是一个没有去重效果的set可以用于除去重以外其他功能的实现 值得注意的是multiset的大部分接口和set没什么两样但是在set中有的接口设计会考虑去重比如insert的返回值而在multiset中这就没有必要了所以存在一些不同之处 在find中multiset返回的就是第一个出现的val的迭代器 同样的像count函数也存在erase类似处理的情况 count返回的是val在set中出现次数就是为了统一set和multiset的接口用法
5lower_bound、upper_bound
这两个函数还是比较容易混的我们先看看下面的代码 int main()
{setint s;s.insert(1);s.insert(2);s.insert(3);s.insert(4);s.insert(5);s.erase(s.lower_bound(2), s.upper_bound(4));for (const auto e : s){cout e ;}return 0;
}输出结果是 lower_bound和upper_bound返回的是对应值的迭代器吗如果真是这样那4就不应该被删掉且和find就没区别了。
事实上对于lower_bound而言它返回的是按迭代器遍历顺序大于等于val的值的迭代器在上面的代码中2存在于是就把2对应的迭代器返回了回去如果2不存在就会向上找。 而upper_bound返回的是按迭代器遍历顺序大于val的值的迭代器在上面的代码中4虽然存在但它会找比4大的值返回的是5的迭代器因此erase按左闭右开的规则会删掉4。 两种迭代器都是向比自己大的值去找但lower_bound要找等于自己的upper_bound不找。在erase中却很好理解s.erase(s.lower_bound(2), s.upper_bound(4));就是删掉2到4之间的所有值闭区间。在所有迭代器的组合使用中都是左闭右开lower_bound对应左upper_bound对应右这样你就明白为什么这样设计了。
如果找不到符合规则的迭代器那就会返回end。
6find
前面我已经介绍了find这里为什么还要介绍呢前面的find是set容器里自带的而这里我想讨论算法库的find和容器里的find的区别 在算法库中find前两个参数是迭代器区间第三个是要查找的值 而在set中不需要前两个参数了。
似乎两者没什么区别但在底层上区别就很大了。算法库的find只能根据迭代器不断来找。在set和map中迭代器的顺序就是中序的顺序。但对于set自带的find而言就不是按照中序来找数据了而是按照平衡二叉搜索树的特点左小右大来找了在高度次内就能找到。算法库的时间复杂度是O(N)而自带的find时间复杂度是O(logN)
