map和set用法详解
- 一，关联式容器
- 二，键值对pair
- 三，set
- 1. set的用法
- 2. multiset的用法
- 四，map
- 1. 键值对pair的介绍
- 2. map用法
- 3. multimap用法
- 五，总结
上一节我们讲解了二叉搜索树，在讲解之前我们先来讲一下set和map，因为set和map的底层是AVL树和红黑树，而AVL树和红黑树又是一种二叉搜索树，所以我们先熟悉一下map的set及其用法，也为后面的模拟实现做铺垫。
一，关联式容器
在前面的STL容器中，我们学习了string，vector，list等，这些都是这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。
而map和set是关联式容器，关联式容器也是用来存储数据的，存储数据时可不是随便存放的，还要与其他数据进行关联，而且与序列式容器不同的是，其里面存储的是 结构的键值对，在数据检索时比序列式容器效率更高。
二，键值对pair
在关联式容器中存储的不单单只是元素，而是一种键值对结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。
其代码是这样的：
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){}};STL总共实现了两种不同结构的管理式容器：
树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。
这四种容器的共同点是：使用 平衡搜索树(即红黑树) 作为其底层结果，容器中的元素是一个有序的序列。下面一依次介绍每一个容器:
三，set
先来看set，set是一个K模型的结构，不能有重复元素。
set是按照一定次序存储元素的容器，其中序遍历可以得到升序序列，这是因为其内部仿函数是less，上图可以看到默认的是less。set中的元素不能修改，set在底层是用二叉搜索树(红黑树)实现的。
所以set实际上是排序+去重
1. set的用法
下面来看set的用法
先来看构造：
set可以构造为空，也可以用迭代器区间构造
set<int> s1;vector<int> v(10,1);set<int> s2(v.begin(),v.end());set<int> s3(s2);然后来看下set的迭代器：
迭代器部分的使用和之前的其他容器没有什么区别
set<int> s;set<int>::iterator it = s.begin();while(it != s.end()){cout<<*it<<" ";++it;}当然也支持范围for，但是注意尽量加上引用，因为其内部存储的是键值对，加上引用可以减少拷贝
for(auto &e : s){cout<<e<<" ";}set不能对数据做修改，只能插入和删除
我们看一下插入：
set可以值插入，也可以传入迭代器位置插入，也可以传入迭代器区间。
set<int> s;s.insert(1);set<int>::iterator it = s.begin();s.insert(it,2);int a[] = {1,2,3,4};s.insert(a.begin(),a.end());来看删除之前先看一下find
find会返回要查找值的迭代器位置，如果找不到，则返回最后一个位置
find一般会和erase搭配使用
现在来看set的删除
可以传入迭代器位置，也可以传入值来删除，也可以传入迭代器区间。
这里删除时传入值和迭代器位置的删除方式略有不同，
set<int> s;//set排序+去重int a[] = { 1,3,5,2,4,8,5,6,7 };for (auto &e : a) {s.insert(e);}auto pos = s.find(3);if (pos != s.end()) {cout << "找到了" << endl;s.erase(pos);}s.erase(1);如果删除的值不存在呢，当传入的是迭代器位置时，不存在会报错，而传入的是值时则不做处理。
auto poss = s.find(10);s.erase(poss);//s.erase(10);报错：
下面来看看count函数，这个接口的作用就是返回set中值的个数，没有则为0 。一般用来检查一个值在不在
再来看下这两个接口，这两个接口是用来确定一段区间，比如要删除set中2~5之间的数，要找到这个区间就传入这个区间的两端的值，会返回这两个位置的迭代器。
具体的使用场景看下面来理解：
可以看到 lower_bound 和 upper_bound 返回的值
void test_set2(){// 排序+去重set<int> s;s.insert(5);s.insert(1);s.insert(6);s.insert(3);s.insert(4);// [60, 70]// [)auto start = s.lower_bound(3);// >=valcout << *start << endl;auto finish = s.upper_bound(5);// >valcout << *finish << endl;//s.erase(start, finish);while (start != finish){cout << *start << " ";++start;}cout << endl;for (auto e : s){cout << e << " ";}cout << endl;}
所以可以得知，lower_bound 返回的是>=所要查找的值，upper_bound 返回的是 >呀查找的值，其实为的是返回的是一个左闭右开的区间。
2. multiset的用法
现在来看multiset，multiset在底层中存储的是的键值对
multiset和set的区别是这个可以存放重复的值。
其他的接口和set相差不大：
multiset也是默认升序的，这里也体现出count接口的作用，统计某个值出现了几次。
void test_set3(){// 排序multiset<int> s;s.insert(5);s.insert(1);s.insert(6);s.insert(3);s.insert(4);s.insert(5);s.insert(1);s.insert(1);s.insert(5);s.insert(1);s.insert(1);s.insert(2);s.insert(7);s.insert(10);multiset<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;cout << s.count(5) << endl;cout << s.count(1) << endl;}但是对于find接口，当一个值出现多次的时候，要返回哪一个呢，我们可以来验证一下
it = s.find(5);while (it != s.end() && *it == 5){// *it += 100;cout << *it << " ";++it;}cout << endl;其实find找到后会返回中序的第一个值。
四，map
map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素
从上图可以看到，map的默认比较器Compare也是less，当其中序遍历时，是按照Key的值来升序排列的。
也就是说map中存储的是一种键值对结构，和set不同的是map里面有两个值，也就是KV模型结构，map也不能存储Key相同的节点。
在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:
typedef pair<const key, T> value_type;1. 键值对pair的介绍
在讲map的用法之前先说一下键值对pair，什么是键值对呢？
用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量
key和value，key代表键值，value表示与key对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义
下面是SGI-STL中关于键值对的定义:
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){}};其中pair中的first就对应的是map中的Key，second对应的是map的Value。
2. map用法
来看一下map的构造
这里和set的差别不大
map的迭代器用法也和set一样，也支持范围for，同样也要注意加上
&
我们直接来看insert
map的插入时和set不同，这里的value_type是一个pair。
返回值也是一个pair
插入时可以用匿名对象：
map<string, string> m;m.insert(pair<string, string>("sort", "排序"));m.insert(pair<string, string>("apple", "苹果"));m.insert(pair<string, string>("BMW", "宝马"));当然最推荐的方式是 make_pair
m.insert(make_pair("jeep", "吉普"));也可以支持隐式类型转换，这里是因为C++11 支持多参数构造函数的隐式类型转换
m.insert({ "apple", "苹果" });插入后我们也可以验证map存储的是pair，查看pair里面的值：
for (auto& kv : m){cout << kv.first << ":" << kv.second << endl;}cout << endl;map也可以在迭代器位置插入和迭代器区间插入
map是支持
[]的，这里的[]和平时我们用的可不一样，
在讲[]之前我们先来想想如何用map来统计每种水果出现的次数：
一般的方法我们是这样：
string s[] = {"apple","binina","jim","tom","apple","jerry","jim","apple"};map<string, int> m;//统计水果个数for (auto &e : s) {map<string, int>::iterator it = m.find(e);//map的find如果找到会返回其迭代器位置，找不到会返回end()if (it != m.end()) {it->second++;}else{m.insert(make_pair(e, 1));}}for (auto& e : m) {cout << e.first << ":" << e.second << endl;}cout << endl;但是我们要是用[]，那么就方便很多：
//用[]统计for (auto& e : s) {m[e];}for (auto& e : m) {cout << e.first << ":" << e.second << endl;}可以看到两种方法的结果是一样的！
这是为什么呢？因为当我们定义map为时，
[]既可以在没有这种水果的时候进行插入，又可以在水果存在的时候统计其出现的次数，并且分别存储在map的Key和Value中。
从下图可以看到这里传入的是map中的Key，返回的是Value。
在其内部其实是调用了insert的，
而为什么要调用insert呢？
这就要先来看看insert的返回值了
这里插入的时候，返回的是也一个pair结构，但是里面存储的一个是iterator迭代器位置，一个是bool值，这里注意：返回的pair和map存储的pair不是同一个
- 当检测到要插入的值不存在时，这个返回的pair中iterator是插入后的位置，bool为true，
- 当检测到要插入的值存在时，这个返回的pair中iterator是要插入的原位置，bool为false，
知道了insert的返回值我们来看[]如何调用insert的
map的erase和set也一样
知道了[]的原理后，[]不仅可以统计次数，还可以插入元素，修改Value值，
map<string, string> dict;dict.insert(make_pair("sort", "排序"));dict.insert(make_pair("string", "字符串"));dict.insert(make_pair("sort", "xxx"));dict["left"]; // 插入cout << dict["sort"] << endl; // 查找dict["sort"] = "xxx"; // 修改dict["right"] = "右边"; // 插入+修改for (auto& kv : dict){cout << kv.first << ":" << kv.second << endl;}cout << endl;3. multimap用法
multimap和multiset一样，和map和set的区别就是可以存储重复的值，但是这里的multimap不支持[]
五，总结
知道了set和map后，我们还是要多做练习才可以更深入的理解。下节我会讲解AVL树，终于要上难度了，希望大家可以在我的讲解下能轻松掌握！！