目录

一、map和set的使用

1、序列式容器和关联式容器

2、set的使用讲解

 3、map的使用讲解

二、multiset和multimap 

1、multiset和multimap的使用

2、OJ题：前k个高频单词

---

一、map和set的使用

1、序列式容器和关联式容器

序列式容器：vector/list/string/deque

序列式容器才支持push等操作，关联式容器不支持

关联式容器：map/set/unordered_map/unordered_set

set和map的底层实现是平衡搜索二叉树

---

2、set的使用讲解

• set就是搜索树中的key模型
• set的特性：①、会对插入的数据自动排序 ②、set是不允许修改值的 ③、set中不允许出现重复的数值，即使存在，也只会留一个
• set的遍历：①、迭代器遍历 ②、范围for遍历（因为支持迭代器遍历就一定支持范围for）
• set的拷贝构造
• set的插入只有insert，其没有push、pop等，因为它是关联式容器
• set的find，find找到了会返回被查找元素的迭代器，没找到返回end()，故应检查找没找到
• 那set的find和库里面提供的find有什么区别呢？
• 都可实现查找，区别在于效率
• set是搜索二叉树的：时间复杂度：O（logN），而算法中的是O（N）
• 算法中的find是个模板，其实现是为了所有容器可以通用它，故set尽量用自己的find 
• set的删除
• ①、erase(待删除位置的迭代器)  ②、erase(待删除数据) ③、erase(s.begin(), s.end())【即迭代器头和尾，其效果等价于clear   】

因为set是key模型，是看在不在，如果把中国所有人的信息存入到set中，最多搜索次数才31次，因为搜索二叉树的效率：O（logN）2^31就=20多亿了，这个效率是非常好的

代码如下：

void test_set()
{set<int> s;s.insert(3);s.insert(1);s.insert(4);s.insert(3);s.insert(7);//set : 排序+去重set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;//支持迭代器，就支持范围forfor (auto e : s){cout << e << " ";}cout << endl;set<int> copy(s);//set的深拷贝for (auto& e : copy){cout << e << " ";}cout << endl;//auto pos = s.find(3);//可用auto推导类型//set<int>::iterator pos = s.find(3);//find查找返回迭代器 find找到了会返回元素的迭代器，没找到返回end()//if (pos != s.end())//{//找到了才能删除//	s.erase(pos);//erase会删除迭代器位置的数据//}//若erase直接给值，若值不存在，也不会报错，但迭代器必须存在那个位置set<int>::iterator pos = find(s.begin(), s.end(), 3);//使用算法中的findif (pos != s.end()){s.erase(pos);}for (auto& e : s){cout << e << " ";}cout << endl;
}

运行结果： 

  

---

 3、map的使用讲解

• map就是搜索树中的key/value模型
• map的遍历：①、迭代器遍历 ②、范围for遍历
• map的类型是pair，pair存的一个是key的，一个是value的类型
• map的构造函数：①、pair构造函数 ②、make_pair函数模板构造一个pair对象

void test_map1()
{map<int, int> m;//m.insert(1, 1);//编译不通过m.insert(pair<int, int>(1, 1));//pair构造函数，构造一个匿名对象m.insert(pair<int, int>(3, 3));m.insert(pair<int, int>(2, 2));m.insert(make_pair(4, 4));	   //函数模板构造一个pair对象map<int, int>::iterator it = m.begin();while (it != m.end()){	//*it等价于pair,而要访问它的成员cout << it->first << ":" << it->second << " " << endl;//也可以用(*it).first    (*it).second//operator* 返回值是节点中值的引用//operator->返回值是节点中值的指针，即pair<k,v>指针//本质上为了可读性，这里省略了一个->++it; }cout << endl;for (auto& e : m){//first就是key值，即pair中的第一个值，second就是value值，即pair中的第二个值cout << e.first << ":" << e.second << endl;}}

 

---

• map构造函数两种方法的区别

void test_map2()
{//一般写项目不会把std库中的全引进来，而是如下代码，make_pair明显更加简洁std::map<std::string, std::string> dict;dict.insert(pair<std::string, std::string>("metric", "米制的"));dict.insert(make_pair("potent", "强大的"));dict.insert(make_pair("deplete", "大量减少"));std::map<std::string, std::string>::iterator it = dict.begin();while (it != dict.end()){cout << it->first << ":" << it->second << endl;++it;}cout << endl;
}

可见使用make_pair会使代码更简洁

---

以下是map的应用：统计水果出现的次数【本质是key/value模型的应用】

法一：利用map的find（用key值来查找，而不是value值）

void test_map3()
{//用STL中的map怎么统计水果出现的次数呢？string strs[] = { "西瓜","樱桃","苹果","西瓜","西瓜","西瓜","西瓜","苹果" };map<string, int> countMap;for (auto & str : strs){map<string, int>::iterator ret = countMap.find(str);if (ret != countMap.end()){ret->second++;//相当于value++}else{//第一次出现，直接插入value为1countMap.insert(make_pair(str, 1));}}for (auto& e : countMap){cout << e.first << ":" << e.second << endl;}
}

---

法二、map的operator[ ]求解

我们之前学的容器只有string，vector和deque才有operator[ ]，而这里map的operator[ ]还有所不同

下面是operator[ ]的底层

可见给operator[ ]一个key值，它返回对应的value值的引用

那就可以把求水果出现的次数代码用operator[ ]实现进一步优化

void test_map3()
{//用STL中的map怎么统计水果出现的次数呢？string strs[] = { "西瓜","樱桃","苹果","西瓜","西瓜","西瓜","西瓜","苹果" };map<string, int> countMap;for (auto& str : strs){//法二、operator[]实现countMap[str]++;//给key值:字符串,返回对应value的引用:次数}for (auto& e : countMap){cout << e.first << ":" << e.second << endl;}
}

---

法三、map的insert求解

operator[ ]的底层是调用insert实现的，故想了解operator[ ]要先了解insert

insert的其中一个版本是

pair<iterator, bool> insert (const value_type& val);

它返回值的意思：

单元素版本：（1）返回pair，其成员pair::first设置为一个迭代器，该迭代器指向新插入的元素或映射中具有等效键的元素。如果插入了新元素，则pair::第二个元素设为true，如果已经存在等效键，则设为false。

理解：

insert对于插入不存在的数据充当插入作用，pair的first指向新插入元素，second设为true，但若插入一个已经存在的数据，insert充当查找作用，pair的first指向之前存在的那个元素，second设为false

利用insert这个版本的特点，我们可以把水果出现的次数再写一个insert的版本

void test_map3()
{//用STL中的map怎么统计水果出现的次数呢？string strs[] = { "西瓜","樱桃","苹果","西瓜","西瓜","西瓜","西瓜","苹果" };map<string, int> countMap;for (auto & str : strs){//法三、insert实现pair<map<string, int>::iterator, bool> ret = countMap.insert(make_pair(str, 1));//也可写为auto ret = countMap.insert(make_pair(str, 1));//如果插入成功，那就说明之前在map中没出现过，value为1即可if (ret.second == false){//插入失败，说明之前存在这个数据,迭代器指向之前出现的那个元素ret.first->second++;//用迭代器访问到这个元素的value值}}for (auto& e : countMap){cout << e.first << ":" << e.second << endl;}
}

---

那insert是如何实现map的operator[]的？

• 如果水果不在map中，则[ ]会insert插入pair<str, int()> 等价于 pair<str, 0>，那么返回映射对象（次数）的引用就进行了++1
• 如果水果在map中，则operator[ ]返回水果对应的映射对象（次数）的引用，对它++

---

下面讲解下map的operator[ ]的多种功能

void test_map3()
{//用STL中的map怎么统计水果出现的次数呢？string strs[] = { "西瓜","樱桃","苹果","西瓜","西瓜","西瓜","西瓜","苹果" };map<string, int> countMap;for (auto & str : strs){//法二、operator[]实现countMap[str]++;//给key值:字符串,返回对应value的引用:次数}countMap["香蕉"];       //插入,因为第一次出现countMap["香蕉"] = 1;   //修改，因为operator[]返回value的引用，故可修改cout << countMap["香蕉"] << endl;//查找，因为香蕉已经存在了countMap["哈密瓜"] = 5; //插入+修改，哈密瓜第一次出现，并对他的value进行了修改map<string, string> dict;dict.insert(make_pair("sort", "排序"));dict["string"];//key为string，value是string类型的构造函数【因为其是缺省值】，即空串  //插入（一般不会这样用）dict["string"] = "字符串";//返回value的引用，可以对其进行修改，能修改是因为返回value的引用 //修改，不算插入因为已存在dict["left"] = "左边";//插入+修改，因为"左边"第一次出现，故插入，插入后又对其value进行了修改for (auto& e : countMap){cout << e.first << ":" << e.second << endl;}
}

注：传参只能传key，不能只传value不传key，因为底层是搜索树，搜索树要用key去比较大小，key只要进去了就不能修改了

一般使用operator[]去

• 插入+修改
• 修改

一般不会用它去查找，因为如果key不在会插入数据

总结：

---

二、multiset和multimap 

1、multiset和multimap的使用

 multiset和multimap除了在set和map的基础上支持数据重复出现外，根本没什么区别

void test_multi()
{//与set的区别是允许键值key冗余（重复）multiset<int> ms;ms.insert(3);ms.insert(2);ms.insert(3);ms.insert(1);ms.insert(4);ms.insert(5);for (auto e : ms){cout << e << " ";}cout << endl;auto pos = ms.find(3);cout << *pos << endl;++pos;cout << *pos << endl;++pos;//multi_map和map的区别和set与multi_set的区别一样//额外区别是muti_map没有operator[]，因为当有多个相同的可以时，不知道返回哪个key对应的valuemultimap<string, int> mm;mm.insert(make_pair("苹果", 1));mm.insert(make_pair("苹果", 1));mm.insert(make_pair("苹果", 3));mm.insert(make_pair("西瓜", 2));mm.insert(make_pair("西瓜", 1));}

 

---

2、OJ题：前k个高频单词

思路：

①、先创建个map对象，利用operator[ ]对其中的字符串排序（会按ASCII码排序），那么key值应该是string，因为map是按照key值从低到高排序的 

②、因为出现频率高的在前，且还有重复数据的出现，故使用multimap和仿函数

把countMap中的数据插入到multimap中，multimap的key值是int类型的，那相当于multimap按出现频率排序，那出现频率高的就会在前，而出现频率相同的，之前operator[ ]已排好序了，按字典顺序排的，小的ASCII码在前

③、因为返回vector<string>，故只把multimap中的string存入到结果中即可，访问他的string即迭代器位置->second

class Solution {
public:vector<string> topKFrequent(vector<string>& words, int k) {map<string, int> countMap;//统计每个字符串出现了多少次for (auto& e : words){countMap[e]++;//map会自动对key值排序，即对string排序，并修改对应的value值}//但我们现在需对value值排序，即对int排序,因为要找出现频率高的//法一、将pair<string, int>键值对放到vector中，用sort排序，还要写一个//按int比较的仿函数，因为sort是快排实现的，不稳定，排完了，还需对次数相同的按字母排,要存入vector是因为//sort只供支持随机访问的容器使用，如vector、deque//法二、用multimap按次数排序，利用仿函数控制从大到小排multimap<int, string,greater<int>> sortMap;//multimap可以保证数据的重复出现for (auto& kv : countMap){sortMap.insert(make_pair(kv.second, kv.first));//排完序后插入到multimap,其会按int从大到小排//排完后//出现次数高的在前面，而出现次数相同的，之前已用operator[]按string排序了}vector<string> v;auto it = sortMap.begin();while (it != sortMap.end()){if (k == 0)break;v.push_back(it->second);//插入字符串++it;--k;//插入完一个就--}return v;}
};