C++map和set

什么是关联式容器？

在初阶阶段，我们已经接触过STL中的部分容器，比如：vector、list、deque、forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。那关联式容器又是什么呢？其实关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高。

键值对

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。

树形结构的关联式容器

根据应用场景的不同，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。

set的概念

定义： set是关联容器，也就是按照一定次序存储元素的容器

T: set中存放元素的类型，实际在底层存储<value, value>的键值对。
Compare：set中元素默认按照小于来比较
Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理

我们可以通过cplusplus网站查到set的一些成员函数：
网站点击进入

代码实现一个set:

#include<iostream>
#include<set>
using namespace std;void test_set1()
{set<int>  s;s.insert(3);s.insert(1);s.insert(4);s.insert(7);s.insert(2);s.insert(1);//排序+去重auto it = s.begin();//关联式容器的迭代器 it//set<int>::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也能查找,因为find写的是一个模板,底层是迭代器实现的，但是效率不高if (pos != s.end()){s.erase(pos);//找到pos删除}//s.erase(1) << endl;//给值删除cout << s.erase(1) << endl;//对于基于值的版本，该函数返回擦除的元素数量   cout << s.erase(3) << endl;//对于基于值的版本，该函数返回擦除的元素数量  for (auto e : s){cout << e << " ";} cout << endl;	
}
int main()
{test_set1();return 0;
}

输出结果：

第一行结果：通过运行我们看到第一行的输出结果是按照升序排序并且数据不重复，我们插入（insert）的是两个1，输出一个1，说明set底层按照二叉搜索树走中序进行了排序并且还去重。
第二行结果：为了方便我们也可以用范围for来输出结果，因为范围for的底层也是迭代器实现的。
erase删除元素的时候，函数会返回擦除的元素数量，0表示找到pos位置的元素并删除了，1表示pos没有去找还在，元素是直接删除的。

总结：

1. 与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对。
2. set中插入元素时，只需要插入value即可，不需要构造键值对。
3. set中的元素不可以重复(因此可以使用set进行去重)。
4. 使用set的迭代器遍历set中的元素，可以得到有序序列
5. set中的元素默认按照小于来比较
6. set中查找某个元素，时间复杂度为:(O)logN,也就是说查找一千个元素找10次、一百万个元素找20次、10亿个元素才找30次左右
7. set中的元素不允许修改(为什么?)
8. set中的底层使用二叉搜索树(红黑树)来实现的，并且左右两边比较均衡，因为二叉搜索树有退化成单支的情况，所以准确来说底层是平衡二叉搜索树来实现的

multiset的使用

定义: multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。
代码实现：

void test_set2()
{multiset<int>  s;//multiset允许冗余，排序s.insert(3);s.insert(3);s.insert(3);s.insert(1);s.insert(4);s.insert(3);s.insert(7);s.insert(3);s.insert(2);s.insert(1);auto it = s.begin();//关联式容器的迭代器 it
//set<int>::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);//multiset从第一个3开始查找while (pos != s.end()){cout << *pos << " ";++pos;}cout << endl;
}

从上面的运行结果我们不难看出multiset支持键值冗余，可以排序，我们用find查找的时候只需要找到第一个3往后面走(pos++)就能找到所有的3。

总结：

1. multiset中再底层中存储的是<value, value>的键值对
2. mtltiset的插入接口中只需要插入即可
3. 与set的区别是，multiset中的元素可以重复，set是中value是唯一的
4. 使用迭代器对multiset中的元素进行遍历，可以得到有序的序列
5. multiset中的元素不能修改
6. 在multiset中找某个元素，时间复杂度为:O(logN)
7. multiset的作用：可以对元素进行排序
   lower_bound、upper_bound和equal_range的使用：

lower_bound(val)：返回一个指向当前 set 容器中第一个大于或等于 val 的元素的双向迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
upper_bound(val)：返回一个指向当前 set 容器中第一个大于 val 的元素的迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
equal_range：返回一个区域的边界，该区域包含容器中等效于 val 的所有元素。由于 set 容器中的所有元素都是唯一的，因此返回的范围最多包含一个元素。

#include<iostream>
using namespace std;
#include<set>
int main()
{set<int> myset;//定义一个名为myset的关联式容器set<int>::iterator itlow, itup;for (int i = 1; i < 10; i++)myset.insert(i * 10);//itlow = myset.lower_bound(30);itlow = myset.lower_bound(35);//>=itup = myset.upper_bound(60);//>myset.erase(itlow, itup);//迭代给的区间是左闭右开cout << "myset contains:";for (set<int>::iterator it = myset.begin(); it != myset.end(); ++it)//查询或者遍历set中的元素时，可以用到iterator迭代器cout << ' ' << *it;cout << '\n';return 0;
}

我们给的是下限val是35，上限是val60，那么会删除[40-70)的值域，区间是左闭右开，也就是删除40、50和60。

#include <set>
#include<iostream>
using namespace std;
int main()
{std::set<int> myset;for (int i = 1; i <= 5; i++) myset.insert(i * 10);   // myset: 10 20 30 40 50std::pair<std::set<int>::const_iterator, std::set<int>::const_iterator> ret;ret = myset.equal_range(30);std::cout << "the lower bound points to: " << *ret.first << '\n';std::cout << "the upper bound points to: " << *ret.second << '\n';return 0;
}

这里我们用到了pair，下面会讲pair的用法，该函数返回一对，其成员first是范围的下限（与 lower_bound 相同），second 是上限（与 upper_bound 相同）。因此，equal_range只需要设定一个val就可以了，那么这个set也可以说是指向元素的双向迭代器类型。

pair和make_pair

pair:此类将一对值耦合在一起，这些值可能属于不同类型的：因为pair的底层是struct实现的,不是class，所以可以直接使用pair的成员变量first和second ,也就是说当一个函数需要返回2个数据的时候，这2个数据可以是不同类型，可以选择pair。
简单实现一下：

#include<iostream>
#include<set>
using namespace std;
int main()
{//pair对象pair<int, double> p1;p1.first = 1;p1.second = 2.5;cout << p1.first << ' ' << p1.second << endl;return 0;}

make_pair:模板类型可以从传递给的参数隐式推导,如果包含不同类型的其他对象是隐式可转换的，则可以从包含不同类型的其他对象构造对象(利用make_pair创建新的pair对象)
简单实现一下：

#include<iostream>
#include<set>
using namespace std;
int main()
{pair<int, double> p1;p1 = make_pair(1, 1.5);cout << p1.first << " " << p1.second << endl;int a = 10;string m = "loquot";pair<int, string> newObj;newObj = make_pair(a, m);cout << newObj.first << ' ' << newObj.second << endl;system("pause");return 0;
}

map的概念

定义：map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
实现map并统计出水果的次数：

#include<iostream>
#include<map>
#include<set>
#include<string>
using namespace std;
int main()
{map<string, string> dict;//定义一个字典dict.insert(pair<string, string>("排序", "sort"));dict.insert(pair<string, string>("左边", "left"));dict.insert(pair<string, string>("右边", "right"));dict.insert(make_pair("字符串", "string"));dict["迭代器"] = "iterator";//插入+修改dict["insert"];//插入dict.insert(pair<string, string>("左边", "***"));//插入失败,搜索树只compare keydict["insert"] = "插入";//修改cout << dict["左边"] << endl;//查找   //key在就是查找，不在就是插入//map<string, string>::iterator it = dict.begin();dict.insert(make_pair("字符串", "string"));auto it = dict.begin();//while (it != dict.end()) //{ //	//cout<<(*it).first <<" "<<(*it).second<< endl;//	//pair不支持流插入,struct类型没有访问限定符，可以直接获取it的元素//	cout << it->first<<":" << it->second << endl;//	//类型是结构体的时候，第一个箭头返回的是数据的指针，第二个箭头访问这个值，两个箭头不好看，编译器做了处理省略了一个箭头//	++it;//} //统计次数for (const auto& kv : dict){//dict的每一个值是pair,pair里的每一个值是string,不加引用就是string的拷贝构造，代价太大cout << kv.first << ":" << kv.second << endl;//*it的元素赋值给了kv}string arr[] = { "苹果","西瓜","香蕉","草莓","苹果","西瓜","苹果","苹果","西瓜","苹果","香蕉","苹果","香蕉" };map<string, int> countMap;//map<string,int>::iterator it=countMap;
//for (auto& e : arr){auto it = countMap.find(e);//查找水果if (it == countMap.end())//没有{countMap.insert(make_pair(e, 1));}else  {it->second++;//次数加加}}for (const auto& kv : countMap){//dict的每一个值是pair,pair里的每一个值是string,不加引用就是string的拷贝构造，代价太大cout << kv.first << ":" << kv.second << endl;//*it的元素赋值给了kv}return 0;}

map中方括号[]的功能有三点：
1.插入
2.修改
3.查找

用“[]”实现统计水果的次数

#include<iostream>
#include<map>
#include<set>
#include<string>
using namespace std;
int main()
{map<string, string> dict;//定义一个字典auto it = dict.begin();//统计次数for (const auto& kv : dict){//dict的每一个值是pair,pair里的每一个值是string,不加引用就是string的拷贝构造，代价太大cout << kv.first << ":" << kv.second << endl;//*it的元素赋值给了kv}string arr[] = { "苹果","西瓜","香蕉","草莓","苹果","西瓜","苹果","苹果","西瓜","苹果","香蕉","苹果","香蕉" };map<string, int> countMap;
//用方括号也能实现统计次数
for (auto& e : arr)
{countMap[e]++;
}
for (const auto& kv : countMap)
{cout << kv.first << ":" << kv.second << endl;//*it的元素赋值给了kv}cout << endl;return 0;
}

总结：

1. map中的的元素是键值对
2. map中的key是唯一的，并且不能修改
3. 默认按照小于的方式对key进行比较
4. map中的元素如果用迭代器去遍历，可以得到一个有序的序列
5. map的底层为平衡搜索树(红黑树)，查找效率比较高$O(lo{g}_{2}N)$
6. 支持[]操作符，operator[]中实际进行插入查找

multimap的使用

定义：multimap是多重映射是关联容器，用于存储由键值和映射值的组合形成的元素，遵循特定顺序，并且多个元素可以具有等效的键,和multiset一样支持冗余。

#include<iostream>
#include<map>
#include<set>
#include<string>
using namespace std;
int main()
{multimap<string, string> dict;dict.insert(make_pair("left", "左边"));dict.insert(make_pair("left", "剩余"));dict.insert(make_pair("string", "字符串"));dict.insert(make_pair("left", "xxx"));for (const auto& kv :dict){cout << kv.first << ":" << kv.second << endl; }string arr[] = { "苹果","西瓜","香蕉","草莓","苹果","西瓜","苹果","苹果","西瓜","苹果","香蕉","苹果","香蕉" };multimap<string, int> countMap;//map<string,int>::iterator it=countMap;for (auto& e : arr){auto it = countMap.find(e);//查找水果if (it == countMap.end())//没有{countMap.insert(make_pair(e, 1));}else{it->second++;//次数加加}}for (const auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;//*it的元素赋值给了kv}cout << endl;system("pause");return 0;}

通过结果我们看到使用multimap也能很好的统计出水果出现的次数，因为muitmap支持键值冗余，我们使用的成员函数find会先查找此类水果有没有出现，有就加加次数不会再反复insert，没有我没再insert然后再加加次数。