一.set/multiset总结二.map/multiset总结三.set/map应用

一.set/multiset总结

set是按照一定次序存储元素的容器在set中元素的value也标识它(value就是key类型为T)并且每个value必须是唯一的。

set中的元素不能在容器中修改(元素总是const)但是可以从容器中插入或删除它们。

在内部set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。

set容器通过key访问单个元素的速度通常比unordered_set容器慢但它们允许根据顺序对子集进行直接迭代迭代完后有序。

set在底层是用二叉搜索树(红黑树)实现的。

底层封装着一个pair类型的对象。

这个对象里面存着两个成员变量即key和value。

【函数注意1】

2.set的查找函数find:找到了会返回当前结点的迭代器找不到就会返回最后一个位置的迭代器end()。

3.set还有count函数这个是用来计算出现的个数的但对于set而言来说没有用因为set是去重后的最后的结果要么是0要么是1所以count函数还可以用来具有查找功能。

4.count函数主要用于mutilsetmutilset可以允许重复的数据。

5.set与multiset的区别就在于set里面的数据是唯一的不能出现重复的是去重的而multiset是允许出现重复的不去重的。

【结构注意2】

与map/multimap不同map/multimap中存储的是真正的键值对key,

valueset中只放value但在底层实际存放的是由value,value构成的键值对.

set中查找某个元素时间复杂度为

1.在map中键值key通常用于排序和惟一地标识元素而值value中存储与此键值key关联的内容。

键值key和值value的类型可能不同并且在map的内部key与value通过成员类型value_type绑定在一起为其取别名称为pair:

typedef

};2.底层封装一个pair类型的成员变量。

存储着也是pair类型的对象当要插入一个数据时这个对象是pair类型的才可以被插入所以可以使用匿名对象的形式插入

string(run,

启动));也可以使用一个make_pair(T,T)函数来返回pair.T类型的对象

dict.insert({

});这里会将这个数组类型转化成pair类型怎么转化的调用pair的构造函数C11支持双参构造函数调用时会发生隐式类型转化。

3.使用迭代器访问的不是真正的数据而是pair类型的对象所以要真正的访问数据还需要进一步访问。

而且第一个数据是不能被修改的只能访问第二个数据可以被修改可以被访问。

mapstring,

dict.end()){//it是迭代器就相当于指针//正常是*it就是解引用到要访问的对象了但这里的对象是pair不可以直接打印cout

(*it).first

endl;//可以直接通过指针访问到里面的数据it;}4.对于map来说也是具有排序和去重功能而且当插入相同的值。

并不会插入进去不会覆盖原来的数据。

在内部map中的元素总是按照键值key进行比较排序的。

key是无法被修改的而value的值可以被修改。

map中通过键值访问单个元素的速度通常比unordered_map容器慢但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时可以得到一个有序的序列)。

map通常被实现为二叉搜索树(更准确的说平衡二叉搜索树(红黑树))。

map支持下标访问符即在[]中放入key就可以找到与key对应的value。

只不过与正常的下标访问不同而是传key值给你返回的是value值的引用。

[

①当key在树里面返回的是pair在树里面key对于结点的iteratorfalse。

②当key不在树里面返回的是pair刚插入树里面对应结点的iteratortrue。

所以[]里面其实具有两个功能一是将数据插入进去二是返回对应key的value值的引用。

operator[](const

ret.iterator-second;}mapstring,

stringkv;kv.insert(make_pair(apple,

苹果));kv.insert(make_pair(yellow,

黄色));kv.insert(make_pair(insert,

插入));//[

]具有读取value的功能//跟正常的[]类似只不过map的[]读的是value值cout

kv[apple]

endl;kv[sort];//插入一个空valuekv[sort]

排序;//修改kv[man]

支持[]操作符operator[]中实际进行插入查找。

而multimap是不支持[],因为multimap一个key值可能对应多个value值所以不知道返回哪一个了。

三.set/map应用

};//map的find查找特点当找到要要的key值后会返回对应key-value的迭代器//如果没找到就会返回最后一个位置的后一个迭代器即end()mapstring,

int

count.end())//说明树里没有那就插入进去并给1{count.insert(make_pair(e,

1));}else//说明找到了那就将对应的数字{ret-second;}}for

(auto

arr){count[e];//实现的原理//第一步先插入第二步返回value值//如果不存在就插入并且value值就是匿名对象对应类型的缺省值然后就变成1//

如果存在插入也没事不会覆盖返回value

1.两个序列中可能存在多个相同的数但最终结点只会有一个所以需要先去重这就需要使用set。

使用完set后序列就变得有序了。

2.两个有序序列如何找交集呢

交集两个序列同时从头开始遍历较小的一方就相同的就是交集然后再同时。

class

{//首先要考虑两个序列都去重那就都放进set里。

setint

s1(nums1.begin(),nums1.end());setint

s2(nums2.begin(),nums2.end());//去重排序vectorint

v;auto

it2s2.begin();while(it1!s1.end()it2!s2.end()){if(*it1*it2){it1;}else

{v.push_back(*it1);it1;it2;}}return

v;}

要求获取前k个出现最多的单词不过这里还有个要求当出现的次数相同时就要按照字典序排序。

4.我们想map统计完后单词的顺序是排序好的每个单词的个数可能相同也可能不同。

但如果当单词个数不相同时对出现的个数排序就可以完成任务因为没有出现相同的频率但如果单词个数出现相同时排序完后如果它们的相对顺序没有被改变那么也可以完成任务因为相对顺序就是按照字典序排的所以这个排序得要求是稳定的。

5.还有如何进行比较排序呢我们需要使用仿函数来修改比较规则。

根据次数进行比较并且进行降序排序。

class

public://要求先按照频率由高到低排序也就是出现的次数如何统计出现的次数呢用map统计次数struct

Greater//仿函数重构比较方式利用出现的次数进行比较并且降序排大的在前面小的在后面{bool

operator()(const

kv1.secondkv2.second;}};vectorstring

words,

e:words){countmap[e];}//已经统计完次数了接下来就要按照出现的频率来排序,不过map其实已经按照字典序的排序方法将数据排好//只要要按照频率排序后稳定性不变相对顺序不变就可以了但sort稳定性不行//注意sort无法对map排序所以我们可以将map里的数据放进vector里vectorpairstring,int

v(countmap.begin(),countmap.end());stable_sort(v.begin(),v.end(),Greater());//stable_sort排序比较稳定vectorstring

vs;for(int

i0;ik;i){vs.push_back(v[i].first);//选取前k个单词}return

vs;}

};还有一种方法可以直接使用sort不用管稳定不稳定那就是直接更改sort的比较排序规则除了按照次数进行降序排序外再添加上当次数相同时就按照字典序对单词进行比较。

class

public://要求先按照频率由高到低排序也就是出现的次数如何统计出现的次数呢用map统计次数struct

operator()(const

kv1.secondkv2.second||(kv1.secondkv2.secondkv1.firstkv2.first);//大于就是降序前面大后面小}};vectorstring

words,

e:words){countmap[e];}//已经统计完次数了接下来就要按照出现的频率来排序,不过map其实已经按照字典序的排序方法将数据排好vectorpairstring,int

v;v(countmap.begin(),countmap.end());sort(v.begin(),v.end(),Greater());//也可以利用仿函数的比较规则来使用sort排序首先要按照频率比较当频率相同时按照字典序比较vectorstring

vs;for(int

i0;ik;i){vs.push_back(v[i].first);}return

vs;}