【C++】map和set用法详解

1.关联式容器

我们接触过STL中的部分容器，比如：vector,list,deque,forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。那么什么是关联式容器？它与序列式容器有什么区别？

关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key,value>结构的键值对，在数据检索时比序列式容器效率更高。

2.键值对

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该单词，在词典就可以找到与其对应的中文含义；比如每个学生的学号跟他的姓名，年龄，专业（类型可定义成数组）存在对应关系，找到学号，就可以查到这个学生的相关信息。

SGI-STL中关于键值对的定义：

//STL中关于键值对的定义
template<class T1,class T2>
struct pair
{typedef T1 first_type;typedef T2 first_type;T1 first;T2 second;//构造函数初始化pair():first(T1())//key,second(T2())//value{}//拷贝构造函数,使用实例pair<string,int>pair(const T1& a,const T2& b):first(a),second(b){}
};

3.树形结构的关联式容器

根据应用场景不同，STL总共实现了两种不同结构的关联式容器：树形结构与哈希结构。树形结构的关联式容器主要有四种：map，set，multimap，multiset。这四种容器的共同点是：使用平衡二叉树（即红黑树）作为底层，容器中的元素是一个有序的序列。下面依次介绍每一个容器。

3.1 set

3.1.1 set的介绍

1.set翻译为集合，是一个内部自动有序且不含重复元素的关联式容器。当我们想要去重，就可以利用到set，是一个很直观的接口，并且加入set之后可以实现自动排序，需要注意的是set的元素默认按照小于比较。
2、在set中，每个value必须是唯一的。set中的元素不能在容器中修改（元素总是const），但是可以在容器中插入或删除数据。一般的做法是先删除旧元素，然后添加新元素，这当然是为了维护里面元素的有序性。
3.set在底层使用二叉搜索树（红黑树）实现的。
4.与map/multimap不同，map/multimap中存储的是真正的键值对<key,value>,而set中只放value，但在底层实际存放的是由<value,value>构成的键值对。
5.在set中查找某个元素，时间复杂度为：log2N

3.1.2 set的模板参数列表

//头文件
#include<set>
std::set
template<class T,class Compare = less<T>,class Alloc = allocator<T>>

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

3.1.3 set的使用

点此进入->set的文档

我在下列代码一一解释了关于set常见的函数该如何使用，

#include<iostream>
#include<set>
using namespace std;
int main()
{set<int> myset;//定义//迭代器的使用set<int>::iterator itlow, itup;for (int i = 1; i < 10; i++){//插入数据//注意set会将元素自动排序myset.insert(i * 10);//10 20 30 40 50 60 70 80 90}//删除35-75之间的数据itlow = myset.lower_bound(35);//返回第一个大于等于key_value的定位器itup = myset.upper_bound(75);//返回最后一个小于等于key_value的定位器//注意：set中的删除操作不进行错误检查，所以用的时候最好用一下find()函数,//返回给定值定位器，如果没找到则返回end()。myset.erase(itlow, itup);/*for (auto it = myset.begin(); it != myset.end(); ++it){cout << *it <<' ';}*///这里可以使用范围for，需要加&，因为拷贝也是存在一定代价的，不需要修改的话，也尽量加const//范围for的底层是迭代器,操作由编译器完成for (auto& s : myset){cout << s << ' ';}cout << endl;//count() 用来查找set中某个键值出现的次数。这个函数在set并不是很实用，在map中的用处比较大//因为一个键值在set只可能出现0或1次，==这样就变成了判断某一键值是否在set出现过==。cout << myset.count(100) << endl;//0不存在cout << myset.count(30) << endl;//1存在return 0;
}

3.2 map

map的介绍

点此进入->map的官方文档

1.map是关联式容器，它按照特定的次序（按照key来排序），存储由key和value组合而成的元素。
2.map中，是真正的键值对<key,value>,键值key和值value的类型可能不同，并且在map内部，key与value通过成员类型value_type绑定在一起，取名为pair。

typedef pair<const key,T> value_type

3. 在内部，map中的元素总是按照键值key进行比较排序的。
4. map支持下标访问，即在[]中放入key，就可以找到与key对应的value。在map中key不允许修改，key对应的value可以修改。
5. map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。

map的模板参数列表

相比set，map多了一个参数

#include<map>
std::map
template<class key,class T,class Compare = less<key>,class Alloc = allocator<pair<const Key,T>>

key: 键值对中key的类型
T： 键值对中value的类型
Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比
较
Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的
空间配置器
注意：在使用map时，需要包含头文件。

map的使用

map的官方文档已包括所有关于map的接口函数，现在我们来尝试使用它的常用接口。
最重要的应该有：插入函数insert，[ ]下标访问操作符，对于pair的理解，迭代器的使用，删除函数。

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{//定义一个map对象map<int, string> Stu;//1.用insert函数插入pairStu.insert(pair<int, string>(01, "张三"));Stu.insert(pair<int, string>(02, "李四"));Stu.insert(pair<int, string>(03, "王五"));//但是我们发现在这里，写一个pair很不方便，因此我们可以用make_pair//make_pair的底层：是一个函数模板，还是调用pair去构造/*template<class T1,class T2>pair<T1,T2> make_pair(T1 x,T2 y){return (pair<T1, T2>(x, y));}*/Stu.insert(make_pair(04, "李芳"));//3.第三种用[]的方式插入数据Stu[123] = "王五";//4.map的迭代器//map<int, string>::iterator it = Stu.begin();auto it = Stu.begin();while (it != Stu.end()){cout << it->first << ":" << it->second << endl;++it;}//最好加上引用，如果不修改的话，把const加上更好for (const auto& kv : Stu){cout << kv.first << ":"<< kv.second << endl;}cout << endl;return 0;
}

活学活用：统计水果出现的次数

//利用map，统计水果出现的次数string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };map<string, int> countMap;for (auto& e: arr){//map<string, int>::iterator it = countMap.find(e);auto it = countMap.find(e);//find函数找不到则返回end()if (it == countMap.end()){countMap.insert(make_pair(e,1));}else{it->second++;}}//有个更简洁的方法//for (auto& e : arr)//{//	countMap[e]++;//}for (const auto& e : countMap){cout << e.first << ":" << e.second;}

关于map的元素访问总结

1. map中的元素是键值对，我们需要学习pair，然后学会使用map容器，插入数据，管理数据。
2. map中的key是唯一的，并且不能修改。
3. map默认按照小于（升序）的方式，并且是对key排序的。map中的元素如果用迭代器去遍历，是采用中序遍历的方式，可以得到一个有序序列。
4. map的底层是一个平衡二叉树（红黑树），查找效率很高O(logN)。
5. map中[ ]下标访问操作符是一个大头，它支持查找，修改，插入。operator[ ]向map中插入元素的原理：用<key,T()>构造一个键值对，然后调用insert()函数将该键值对插入到map中，map中的键值对key一定是唯一的，如果key已经存在，插入失败，insert函数返回该key所在位置的迭代器。如果key不存在，插入成功，insert函数返回新插入元素所在位置的迭代器。
6. operator[ ]函数最后将insert返回值键值对中的value返回。（也就是pair类中的second成员）
7. 注意：在元素访问时，有一个与operat[ ]类似的函数，是at()函数，但是这个函数不常用，它们都是通过key找到与key对应的value然后返回其引用，不同的是：当key不存在时，operator[]会用默认的pair插入，返回该默认的value，而at（）函数会直接抛异常。
8. operator[]底层实现如下->
   

3.3multimap

注意：multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重复的。

multimap中的接口可以参考map，功能都是类似的。
注意：

1. multimap中的key是可以重复的。
2. multimap中的元素默认将key按照小于来比较。
3. multimap中没有重载operator[]操作。
4. 使用时与map包含的头文件相同。