[C++进阶]map和set的相关题目
1. 下面关于map和set说法错误的是（）
A.map中存储的是键值对，set中只储存了key
B.map和set查询的时间复杂度都是O(log_2N)
C.map和set都重载了[]运算符
D.map和set底层都是使用红黑树实现的
解析:
A：正确，map和set的概念
B：正确，因map和set的底层结构都是红黑树，而红黑树是近似的平衡二叉搜索树，故查询时间 复杂度为O(log_2N)
C：错误，map中重载了[]运算符，因为其需要通过key获取value，set中没有
D：正确
因此：选择C
2.下面关于map的说法正确的是（）
A.map的查询效率是O(log_2N)，因为其底层使用的是二叉搜索树
B.map的key和value的类型可以相同
C.map中的有序只能是升序，不能是降序
D.map中的key可以直接修改
解析:
A：错误，map的查询效率是O(log_2N)是正确的，但map的底层结构不是二叉搜索树，而是红黑树
B：正确，key和value的类型由用户自己设置，可以相同也可以不同，取决于应用场景需要
C：错误，map可以是升序，也可是降序，默认情况下是升序，如果需要降序，需要用户在实例化 map时指定比较规则
D：错误，map中key不能修改，因为如果修改了就不能保证红黑树的特性了，即有序
因此：选择B
3.下面关于set的说法正确的是（）
A.set中一定不能存储键值对，只能存储key
B.set可以将序列中重复性的元素去除掉
C.set中不能存储对象，因为对象字段较多，没有办法比较
D.set默认是升序，因为其默认是按照大于的方式比较的
解析:
A：错误，set中可以存储键值对，实例化set时，将set中元素类型设置为pair即可
B：正确，因为set中的key是不能重复的
C：错误，set中任意类型元素都可以存储，存储对象时，需要用户提供比较规则
D：错误，set默认是升序，正确，但是其内部默认不是按照大于比较，而是按照小于比较
因此，选择B
4.下列说法正确的是（）
A.set中的某个元素值不能被直接修改
B.map和unordered_map都是C++11提供的关联式容器
C.因为map和set的底层数据结构相同，因此在实现时set底层实际存储的是<key, key>的键值对
D.map和multimap中都重载了[]运算符
A：正确，因为set要保证其有序，因此set中元素不能被直接修改，若要修改可以先删除，在插入
B：错误，map是C++98中已存在的，unordered_map是C++11中才有的
C：错误，map和set底层结构都是红黑树，而其底层红黑树在实现时并没有区分是存k模型还是KV 模型
D：错误，map中key是唯一的，每个key都有与之对应的value，经常需要通过key获取value，因此 map为了形象简 单重载了[]运算符, multimap中key是可以重复的，如果重载了[]运算符，给定 一个key时，就没有办法返回 value了，因此，multimap中没有重载[]运算符
5.前K个高频单词
代码解析:
bool compare(const pair<string, int>& s1, const pair<string, int>& s2) {// 频率相等，按字母排序if(s1.second == s2.second) return s1.first < s2.first;// 按照频率排序else return s1.second > s2.second;
}class Solution {
public:vector<string> topKFrequent(vector<string>& words, int k) {map<string, int> count;for(string& word : words) {count[word] ++;}vector<pair<string, int>> res(count.begin(), count.end());sort(res.begin(), res.end(), compare);vector<string> ans;for(int i = 0; i < k; i ++) {ans.push_back(res[i].first);} return ans;}
};6.单词识别
代码解析:
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include<algorithm>
using namespace std;
typedef pair<string,int> Word;
bool cmp(Word w1,Word w2)
{return w1.second>w2.second;
}
int main()
{map<string,int> mp;string s;while(getline(cin,s)){for(int i=0,j=0;i<s.size();i++){if(s[i]==' '||s[i]=='.'){string t=s.substr(j,i-j);if(isupper(t[0]))t[0]=tolower(t[0]);j=i+1;mp[t]++;}}vector<Word> v(mp.begin(),mp.end());sort(v.begin(),v.end(),cmp);for(int i=0;i<v.size();i++)cout<<v[i].first<<":"<<v[i].second<<endl;}return 0;
}
本篇类似番外,目的只是方便大家巩固,如有错误感谢指正