包头网站建设价格,电子商务网站建设及维护,5免费网站建站,完全免费建站系统我讨厌世俗#xff0c;也耐得住孤独。 文章目录一、键值对二、树形结构的关联式容器1.set1.1 set的介绍1.2 set的使用1.3 multiset的使用2.map2.1 map的介绍2.2 map的使用2.3 multimap的使用三、两道OJ题1.前K个高频单词#xff08;lessT小于号是小的在左面升序…我讨厌世俗也耐得住孤独。 文章目录一、键值对二、树形结构的关联式容器1.set1.1 set的介绍1.2 set的使用1.3 multiset的使用2.map2.1 map的介绍2.2 map的使用2.3 multimap的使用三、两道OJ题1.前K个高频单词lessT小于号是小的在左面升序greaterT大于号是大的在左面降序2.两个数组的交集排序去重简单的比对算法一、键值对
1. 之前所学的vectorlistdeque等容器都是序列式容器因为他们的底层数据结构都是线性的并且数据结构中存储的都是元素数据本身也就是单一的变量。 而下面所学的set、map、multimap、multiset等容器都是关联式容器他们内部存储的不再是单一的元素数据存储的而是key,value的键值对由于每个键值对之间都有关联所以其结构天生就具有优势在数据检索时效率要比序列式容器高的多。
2. 那什么是键值对呢键值对实际也是一个类类里面对key和value数据进行了封装key表示关键码value表示与之对应的值下面是SGI对于pair键值对结构体的定义
3. struct pair{}有两个构造函数一个是无参的利用T1和T2类型的默认构造函数初始化出来的键值对一个是T1和T2作为参数的构造函数。 另外pair还重载了两个运算符用于键值对的等于和小于比较小于比较时优先比较first如果first恰好满足xy则返回true。如果first之间相等则比较失败返回false。如果first是xy那就继续比较second。 为了方便构造键值对pair又另写了成员函数make_pair()这个函数其实也是调用了构造函数但在构造键值对的时候省下我们自己去传T1和T2的类型了就。
template class T1, class T2
struct pair {typedef T1 first_type;typedef T2 second_type;T1 first;T2 second;pair() : first(T1()), second(T2()) {}pair(const T1 a, const T2 b) : first(a), second(b) {}template class T1, class T2
inline bool operator(const pairT1, T2 x, const pairT1, T2 y) { return x.first y.first x.second y.second;
}template class T1, class T2
inline bool operator(const pairT1, T2 x, const pairT1, T2 y) { return x.first y.first || (!(y.first x.first) x.second y.second);
}template class T1, class T2
inline pairT1, T2 make_pair(const T1 x, const T2 y) {return pairT1, T2(x, y);
}二、树形结构的关联式容器
根据应用场景的不同STL总共实现了两种不同结构的管理式容器一种是树型结构一种是哈希结构树型结构的关联式容器主要分为map、set、multimap、multiset。 这四种容器的共同点是都是用平衡搜索树(红黑树)作为底层结构。
1.set
1.1 set的介绍
1. 在set中key和value是同时被标识的所以key就是value正由于key就是value所以set容器中的元素不允许被修改每个元素都被const修饰只能增insert删erase查find。
2. set在比较时默认使用缺省的仿函数less T 所以一旦比较成功时较小元素就被插入到左边较大元素就被插入到右边那么在中序遍历时结果自然就是升序结果。如果改为greater T 则逻辑就会反过来中序遍历结果就是降序。 3. set与map不同的是map存放的是真正的键值对key,value而set中只放value但在底层实际存放的是key,key的键值对。 4. set不允许元素被修改因为这会破坏搜索树的结构。
5. set中不允许元素有重复所以set和二叉搜索树比较像一旦元素重复再进行插入时情况就较为复杂需要用到树的旋转等知识不过multiset可以支持插入的元素重复。 在使用set迭代器进行遍历时set的迭代器走的是中序遍历的顺序每一个迭代器都指向对应位置的键值对当然set容器的元素我们也可以叫做键值对只不过key和value相等罢了。
6. 由于set中不允许有元素重复所以将一段数据插入到set时set所展现的功能是排序去重。
1.2 set的使用
1. set的insert有三个重载形式较为常用的就是直接插入一个值和利用其他容器的迭代器区间构建出set容器。
2. erase用于删除set中的某个元素如果删除成功则返回1否则返回0size_type是unsigned int typedef出来的。 3. find用于查找set中某个元素val找到就返回键值对对应的迭代器否则就返回end迭代器。 算法库中也有find但哪个find的效率明显要低于set类的find因为一个是类似于二分查找一个是暴力通过迭代器进行查找一个是logN一个是N void test_set1()
{setint,greaterint s;s.insert(3);s.insert(1);s.insert(4);s.insert(7);s.insert(2);s.insert(1);//set底层是二叉搜索树当插入相同的值时会返回false所以set是排序去重setint,greaterint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;for (auto e : s){cout e ;}cout endl;//auto pos s.find(3);auto pos find(s.begin(), s.end(), 3);//算法库的find其实就是利用迭代器进行查找找不到就返回end()迭代器//上面这两行代码的查找结果相同但34行的效率肯定更高一些因为35行是暴力查找34行借助搜索树的特性查找高度次//如果是平衡的搜索树则效率是O(logN)。暴力查找的效率是O(N)即一个一个迭代器的遍历进行查找。if (pos ! s.end()){s.erase(pos);}for (auto e : s){cout e ;}cout endl;cout s.erase(10) endl;//返回0表示没有删除cout s.erase(1) endl;//返回1表示删除//上面代码等价于finderase删除元素也是要先找再删找到就删没找到就直接返回。
}1.3 multiset的使用
1. multiset与set的唯一区别就是允许元素重复其余并没有什么区别所以用multiset进行排序时仅仅只能排序没有去重的效果。 在set中count可能没有什么用因为每个键值对都只能出现一次不允许元素重复但count在multiset中就有用了可以统计某个key在set中共出现了几次。 #include set
void TestSet()
{int array[] { 2, 1, 3, 9, 6, 0, 5, 8, 4, 7 };// 注意multiset在底层实际存储的是int, int的键值对multisetint s(array, array sizeof(array)/sizeof(array[0]));for (auto e : s)cout e ;cout endl;return 0;
}2. 在set和multiset中都有lower_bound和upper_bound接口bound是约束束缚的意思可以用于set中某一上限和下限区间元素的删除有一说一这俩接口确实不常用。 2.map
2.1 map的介绍
1. map存储的是key和value组成的键值对元素结构体在比较时按照key来进行比较下面源码我们可以看到key依旧是不允许被修改的但其对应的value是可以被修改的。 2. map中比较时比较的是key类型但我们可以通过key找到value这里多说一句无论是map还是set他们的迭代器走的都是中序的顺序。 2.2 map的使用
1. map和set都有三个构造函数其中无参构造函数最为常用平常在使用map或set时直接定义其对象即可无须传参大多数情况下都是这样。 2. map和set在插入后都会返回一个键值对 键值对的first是迭代器其指向的是新插入键值对若新插入键值对的key已经存在则返回已经存在的key对应的键值对的迭代器这是first的变化规则。 键值对的second是bool值如果插入的key已经存在则bool为false否则bool为true。 3. map的迭代器访问这里有讲究由于其迭代器指向的是由key和value组成的键值对那* it该获得哪个key和value的哪个值呢set的迭代器指向的就只有key所以* it直接返回key值即可。 对于map来说*it拿到的是pair的对象所以我们还需要再加一个.操作符才能访问pair对象里面的first和second值但这样写起来有点麻烦所以map的迭代器也重载了→操作符→重载的函数会返回迭代器指向对象的地址所以还应该再加个→访问first或second才对但是编译器在这里做了优化省略了一个箭头。这部分其实在list迭代器那里就说过了这里正好做一下复习
4. 在map这里如果我们用语法糖遍历map时最好采用const引用因为map中存的是键值对pair不用引用就会发生赋值会调用pair的赋值重载函数代价比较大为了提升效率建议采用const引用。语法糖遍历拿到的值其实就是*it在map这里就是pair对象键值对
int main()
{mapstring, string dict;dict.insert(pairstring, string(苹果, apple));dict.insert(pairstring, string(鸭梨, pear));dict.insert(pairstring, string(西瓜, watermelon));dict.insert(make_pair(草莓, strawberry));//make_pair是一个函数模板内部调用pair的构造函数但隐式实例化可以减少代码dict[迭代器] iterator;// 插入修改dict[insert];// key不在就是插入value用string的默认构造dict.insert(pairstring, string(鸭梨, xxxx));//这个插入不进去搜索树的鸭梨已经存在了dict[insert] 插入;// insert已经存在这里表示修改insert的value值cout dict[insert] endl;//key已经存在这里相当于查找[]会返回关键码对应的value值查找时必须确定key已经存在于mapmapstring, string::iterator it dict.begin();while (it ! dict.end()){//如果结点定义成key和value两个变量*it都不知道返回谁的值。所以返回pair对象这样就可以访问两个值了//cout (*it).first : (*it).second endl;cout it-first : it-second endl;//底层是pair封装了value和key并实现运算符重载it;}for (const auto kv : dict)//kv就相当于*it取到的是map中存储的结构体对象pair//现在的kv已经不像以前一样仅仅是个内置类型而是一个结构体对象结构体的对象进行赋值调用函数代价太大所以我们用引用{cout kv.first : kv.second endl;}
}5. 如果用map来统计水果出现的次数我们采用的思路可以是如果key不在那就将键值对插入map键值对的int初始值设置为1。如果key在那就把key对应的value值1最后语法糖遍历一下map就可以拿到中序遍历的结果也就是统计出了水果出现的次数。
6. 另外还有一种非常骚的操作就是利用map的[ ]来统计次数在前面了解了insert的返回值之后再来理解map的[ ]调用成本就会低很多了实际上[ ]带来的作用包括插入查找修改的功能直接一个[ ]运算符重载包揽map的三个重要功能。
7. 拥有这么多功能其实还是因为调用了insertinsert在插入时的键值对的key由我们来传参而value用其对应类型的匿名构造来代替所以如果key不存在那insert就表示插入如果key已经存在则[ ]既可以修改又可以查找。 8. 所以用[ ]可以直接统计出次数将对应的arr每个元素插入到map里面如果key存在则[ ]内部的insert会返回已经存在的key对应的迭代器通过此迭代器可以拿到value的引用又因为int类型匿名构造是0则value初始化是0就是1所以countMap.[e]就可以直接统计出水果出现的次数。
int main()
{//定义一个map统计水果出现的次数string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉 ,草莓,草莓, 香蕉, 西瓜, };mapstring, int countMap;//for (auto e : arr)//{// //mapstring, int::iterator it countMap.find(e);// auto it countMap.find(e);// if (it countMap.end())// countMap.insert(make_pair(e, 1));// else// it-second;//}for (auto e : arr){countMap[e];// ( *( (this-insert(make_pair(k, mapped_type()))).first ) ).second //迭代器指向的是pair类实例化的对象我们称这个对象为键值对}for (const auto kv : countMap){cout kv.first : kv.second endl;}return 0;
}9. 注意在元素访问时有一个与operator[]类似的操作at()(该函数不常用)函数都是通过 key找到与key对应的value然后返回其引用不同的是当key不存在时operator[]用默认 value与key构造键值对然后插入返回该默认valueat()函数直接抛异常。
2.3 multimap的使用
1. multimap是没有[ ]的因为multimap支持key值进行重复那[ ]返回哪个key的引用呢太乱了吧所以multimap没有重载[ ]运算符。其余接口的使用和map一样这里不作介绍。
三、两道OJ题
1.前K个高频单词less小于号是小的在左面升序greater大于号是大的在左面降序
前K个高频单词
1. 我们可以用排序的思路来解决这道题定义string和int的键值对然后将所有单词存到map里面这样map里面就有单词和单词出现的次数的键值对了并且string还是按照字典顺序排好了。然后我们将键值对利用sort来进行排序但由于map的迭代器是双向迭代器而sort要求支持随机访问因为他底层是快排那就需要随机迭代器所以我们将map中的键值对语法糖式的尾插到vector里面vector的迭代器是随机迭代器可以适用于快排。
2. 比较vector中的键值对时快排是不稳定的当两个单词的出现次数一样时那在快排比较的时候是有可能打乱两个单词在vector里面出现的顺序的所以我们可以采取stable_sort进行排序代码里面写出了错误示范其实问题不仅仅出现在sort上面而是出现在pair的比较规则上面去了所以要想解决问题还是得从排序的比较规则上面入手我们重写仿函数自己定义比较的规则就好了让这个比较规则契合题目逻辑。
快排的确是不稳定的这确实没毛病。
3. sort排序想要正确他的仿函数逻辑要分两种情况一种是只有左边键值对的次数大于右边时才可以交换另一种是关键因为快排不是不稳定么那我们就调整逻辑让他稳定当次数相等时必须保证second的相对顺序不变不能随意交换。那就增加条件为左边的string小于右边的string才返回true。 这个地方你可以这么理解因为算法库中默认的less排升序less里面是小于号那就是小的在左面greater排降序greater里面是大于号大的在左面这样理解的话当次数相同时我们想让字符串小的在左面那就应该用小于号进行比较所以仿函数里面second比较那里用小于号
4. 这里并没有改变sort的稳定性只是调整了比较的逻辑如果不控制first相等时的string顺序那快排就会随意打乱次数相等的单词但这并不是我们想看到的所以我们现在强行控制逻辑不让快排打乱单词的顺序必须按照字典顺序保证string小的单词在左面。
class Solution {
public:struct compare{bool operator()(const pairint, string left, const pairint, string right){return left.first right.first || (left.firstright.first left.second right.second);//second用小于号比较}};vectorstring topKFrequent(vectorstring words, int k) {vectorstring ret;mapstring, int mp;for(const auto str : words){mp[str];}vectorpairint, string v;//用vector来排序map是双向迭代器不支持随机访问for(const auto kv : mp){v.push_back(make_pair(kv.second, kv.first));}//第一个是错误写法示例greater排降序但pair默认的比较规则不符合题目要求stable_sort(v.begin(), v.end(), greaterpairint ,string);sort(v.begin(), v.end(), compare());for(int i0; ik; i){ret.push_back(v[i].second);}return ret;}
};5. 下面采用稳定排序的方式进行排序稳定排序不用考虑first相等时单词有可能被打乱顺序的情况因为稳定排序不会打乱相等值的相对顺序。
6. 所以仿函数逻辑就是只有左边的键值对的first大于右边的firstvector中键值对的first是单词出现次数时我们才会返回true进行交换其他相等或小于的情况都不允许交换这样就可以保证大的在左面就能完成降序的工作了。
class Solution {
public:struct compare{bool operator()(pairint, string left, pairint, string right){return left.first right.first;}};vectorstring topKFrequent(vectorstring words, int k) {vectorstring ret;mapstring, int mp;for(const auto str : words){mp[str];}vectorpairint, string v;//用vector来排序map是双向迭代器不支持随机访问for(const auto kv : mp){v.push_back(make_pair(kv.second, kv.first));}stable_sort(v.begin(), v.end(), compare());for(int i0; ik; i){ret.push_back(v[i].second);}return ret;}
};2.两个数组的交集排序去重简单的比对算法
两个数组的交集
1. 这道题目就比较简单了我们可以利用set先进行排序去重然后比较两个set里面的值如果两个值相等时说明这个值是两个数组的交集两个迭代器同时往后走去后面继续比较如果不相等那就让较小元素对应的迭代器往后因为在小元素的后面才会有可能和另一个set当前的值相等。
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {vectorint ret;setint s1(nums1.begin(), nums1.end());setint s2(nums2.begin(), nums2.end());auto it1 s1.begin();auto it2 s2.begin();while(it1 ! s1.end() it2 ! s2.end()){if(*it1 *it2){it1;}else if(*it1 *it2){it2;}else{ret.push_back(*it1);it1;it2;}}return ret;}
};
