set和map的基本使用
目录
关联式容器
要点分析
键值对
pair介绍
set
模板参数列表：
set的构造：
常用接口
操作
multiset
map
map的构造
插入
make_pair
map的迭代器
operator[]
multimap
multimap中为什么没有重载operator[]
关联式容器
关联式容器也是用来存储数据的，和vector、list这样的序列式容器不同的是，它里面存储的是<key,value>结构的键值对，在数据检索时效率很高。在STL库中有两种不同结构的关联式容器，树形结构与哈希结构。树形结构的关联式容器包括set、multiset、map、multimap这四种，也是下面要谈论的主要内容。
要点分析
键值对
要走进关联式容器，首先要理解键值对的概念，这一概念在之前的文章中也有介绍，键值对是用来表示对应关系的结构，结构中一般包含两个成员变量key和value,key代表键值，value代表与之对应的信息。例如：下述图片中的名著和作者就是一一对应的关系！
pair介绍
pair这个类是对键值对的定义，将一对不同类型的数据组合（T1和T2）组合在一起，结构中包含两个成员变量分别是key和value,它们的类型是T1和T2。
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){}
}set
set的底层是用二叉搜索树来实现的。set中只放value，但在底层实际存放的是由<value, value>构成的键值对。
模板参数列表：
●T: set中存放元素的类型，实际在底层存储<value, value>的键值对。
●Compare：set中元素默认按照小于来比较。
●Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理。
set的构造：
void TestSet3()
{//构造空的setset<int> s1;//根据区间构造setint arr[10] = {0,1,3,4,5,7,9,6,2,8};int size = sizeof(arr) / sizeof(int);set<int> s2(arr,arr+size);}
常用接口
修改操作
插入
void SetInsert()
{set<int> ss;ss.insert(5);ss.insert(3);ss.insert(2);ss.insert(2);ss.insert(4);ss.insert(2);ss.insert(2);for (auto& e : ss){cout << e << " ";}
}
需要注意的是，当要插入的数据已经存在，将不会继续插入。
删除
void Seterase()
{set<int> ss;ss.insert(1);ss.insert(2);ss.insert(3);ss.insert(4);ss.insert(5);for (auto& e : ss){cout << e << " ";}cout << endl;ss.erase(3);for (auto& e : ss){cout << e << " ";}cout << endl;ss.erase(5);for (auto& e : ss){cout << e << " ";}cout << endl;ss.erase(1);for (auto& e : ss){cout << e << " ";}
}
交换
void setswap()
{set<int> s1;s1.insert(1);s1.insert(3);s1.insert(5);s1.insert(7);s1.insert(9);cout << "交换前s1：";for (auto& e : s1){cout << e << " ";}set<int> s2;s2.insert(2);s2.insert(4);s2.insert(6);s2.insert(8);s2.insert(10);cout << endl;cout << "交换前s2：";for (auto& e : s2){cout << e << " ";}s1.swap(s2);cout << endl;cout << "交换后s1：";for (auto& e : s1){cout << e << " ";}cout << endl;cout << "交换后s2：";for (auto& e : s2){cout << e << " ";}
}
清理
void setclear()
{set<int> s1;s1.insert(2);s1.insert(4);s1.insert(6);s1.clear();
}
迭代器
void set_iterator()
{int arr[10] = {1,3,5,7,9,2,4,6,8,10};int size = sizeof(arr) / sizeof(int);set<int> s1(arr,arr+size);//auto it1 = s1.begin();set<int>::iterator it1 = s1.begin();while (it1 != s1.end()){cout << *it1 << " ";it1++;}//auto it2 = s2.rbegin()set<int>::reverse_iterator it2 = s1.rbegin();cout << endl;while (it2 != s1.rend()){cout << *it2 << " ";it2++;}
}
容量
void setempty_size()
{int arr[10] = { 1,3,5,7,9,2,4,6,8,10 };int size = sizeof(arr) / sizeof(int);set<int> s1(arr, arr + size);cout << "是否为空：" << s1.empty() << endl;cout << "有效元素个数：" << s1.size() << endl;s1.clear();cout << "是否为空：" << s1.empty() << endl;cout << "有效元素个数：" << s1.size() << endl;
}
操作
find:
void setfind()
{int arr[10] = { 1,3,5,7,9,2,4,6,8,10 };int size = sizeof(arr) / sizeof(int);set<int> s1(arr, arr + size);for (auto& e : s1){cout << e << " ";}cout << endl;auto it = s1.find(5);if (it != s1.end()){cout <<"找到了：" << *it << endl;}else{cout << "没找到！" << endl;}it = s1.find(100);if (it != s1.end()){cout << "找到了：" << *it << endl;}else{cout << "没找到！" << endl;}
}
count:
void setcount()
{int arr[10] = { 1,3,1,7,1,2,1,6,8,10 };int size = sizeof(arr) / sizeof(int);set<int> s1(arr, arr + size);for (auto& e : s1){cout << e << " ";}cout << endl;cout << s1.count(1) << endl;cout << s1.count(2) << endl;cout << s1.count(50) << endl;
}
对于count这个接口，你可能不太理解它为什么会存在，它好像只能确定数据是否出现过，查找数据已经有find了，好像没什么“用武之地”。哈哈哈，它的“志向”当然不在此处，我们接着向下看！
multiset
multiset在接口的用法上大致相同，相比较set而言multiset允许重复数据的出现：
void _multiset()
{int arr[10] = { 1,3,1,7,1,2,1,6,8,10 };int size = sizeof(arr) / sizeof(int);multiset<int> s(arr,arr+size);for (auto& e : s){cout << e << " ";}}
count接口上场：
void _multiset_count()
{int arr[10] = { 1,3,1,7,1,2,1,6,2,10 };int size = sizeof(arr) / sizeof(int);multiset<int> s(arr, arr + size);for (auto& e : s){cout << e << " ";}cout << endl;cout << s.count(1) << endl;cout << s.count(2) << endl;cout << s.count(10) << endl;
}
小问题：既然multiset允许数据的重复，那么当我们查找数据的时候，找到的是哪一个呢？
void _multiset_find()
{int arr[10] = { 1,3,1,7,1,2,3,6,3,10 };int size = sizeof(arr) / sizeof(int);multiset<int> s(arr, arr + size);for (auto& e : s){cout << e << " ";}cout << endl;multiset<int>::iterator it = s.find(3);while (it != s.end()){cout << *it << " ";it++;}
}
测试后发现，find找到的位置是中序遍历第一次找到的元素位置。其余接口和set的使用大多一样，这里就不在测试了。
map
●key: 键值对中key的类型
●T： 键值对中value的类型
map的构造
插入
查询文档了解到，insert的返回值是一个pair,需要的参数也是一个pair。
void maptest2()
{map<string, string> notepad;notepad.insert(pair<string,string>("张三","赤峰"));notepad.insert(pair<string,string>("李四","北京"));for (auto& e : notepad){cout << e.first << ":" << e.second << endl;}//auto pr = notepad.insert(pair<string, string>("王麻子", "西安"));pair<map<string,string>::iterator,bool> pr = notepad.insert(pair<string, string>("王麻子", "西安"));cout << (pr.first)->first <<":"<<(pr.first)->second<< endl;
}
接收insert后的返回值，并进行分析：
通过上述测试对insert有了大致的了解，但是插入的过程中代码显得好笨重，pair<string,string>......每次都要写好长好长，这个时候就要介绍一个帮我们偷懒的朋友了：make_pair!
make_pair
make_pair的返回值是一个pair,根据模板参数T1,T2确定pair中两个元素的类型，根据参数x,y确定元素值。也就是说在上述代码插入数据的部分可以这样写：
map<string, string> s;
s.insert(make_pair("张小红","内蒙古"));
map的迭代器
void mapTest4()
{map<string, string> notepad;notepad.insert(make_pair("张三", "赤峰"));notepad.insert(make_pair("李四", "北京"));notepad.insert(make_pair("王麻子", "西安"));notepad.insert(make_pair("张小红", "内蒙古"));map<string, string>::iterator it1 = notepad.begin();cout << "-----------正向迭代器-----------" << endl;while (it1 != notepad.end()){//cout << (*it1).first << ":" << (*it1).second << endl;cout << it1->first << ":" << it1->second << endl;it1++;}cout << "-----------反向迭代器-----------" << endl;map<string, string>::reverse_iterator it2 = notepad.rbegin();while (it2 != notepad.rend()){//cout << (*it2).first << ":" << (*it2).second << endl;cout << it2->first << ":" << it2->second << endl;it2++;}
}
operator[]
operator[]重载和以往的[]重载相比有一些不一样，传过来的参数是key,返回值是value。在这过程中，首先向this插入make_pair，insert的返回值类型又是一个pair<iterator,bool>,访问pair的first元素获取到一个迭代器，迭代器找到的位置又是一个pair<key，value>,返回该pair的第二个元素也就是value。
观察上图分析后，[]除了访问元素外，还能进行查找，修改，插入的操作。
void mapTest5()
{map<string,int> grade;//插入，前提是该数据原来并不存在grade["语文"];//[]返回值是value,可以对其进行修改grade["语文"] = 99;//查找，根据key查找对应的valuecout << grade["语文"] << endl;
}
应用场景1：统计“象牙山村”选举票数！
void mapset1()
{map<string, int> count;string arr[10] = {"刘能","谢广坤","谢广坤","赵四","王老七","刘能","刘能","王老七","刘能","谢广坤"};for (auto& e : arr){auto it = count.find(e);if (it == count.end()){//插入count.insert(make_pair(e,1));}else{//(*it).second++;it->second++;}}cout << "-------象牙山选举大会--------" << endl;for (auto& e : count){cout << e.first << ":" << e.second <<"票"<< endl;}
}
使用[]的版本：
void maptest1()
{map<string, int> count;string arr[10] = {"刘能","谢广坤","谢广坤","赵四","王老七","刘能","刘能","王老七","刘能","谢广坤"};for (auto& e : arr){count[e]++;}cout << "-------象牙山选举大会--------" << endl;for (auto& e : count){cout << e.first << ":" << e.second <<"票"<< endl;}
}
对比两组代码，后者是不是简单了不少呢，[]使用起来非常的方便，但同时也是一把双刃剑，需要我们对其底层原理有所了解，在使用的时候也一定要细心。
multimap
multimap和map的区别：map中的key是唯一的，而multimap中key是可以重复的。
void Test6()
{multimap<string, string> dict;dict.insert(make_pair("左边", "left"));dict.insert(make_pair("左边", "LEFT"));dict.insert(make_pair("左边", "****"));
}
multimap中为什么没有重载operator[]
在了解过map的[]重载后，你知道[]需要key来访问value。那么在multimap这种允许key重复出现的场景下，xxx[key]访问到的value不一定是唯一的，这时的修改操作也不知道该去修改哪一个value，所以multimap没有重载[]。
小结：关联式容器的介绍到这就结束了，有些接口没有涉及到，有兴趣的小伙伴可以继续查找文档探索！
<set> - C++ Reference
<map> - C++ Reference