关联式容器介绍：
STL中的部分容器，比如：vector、list、deque、 forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？
关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是结构的键值对，在数据检索时比序列式容器效率更高
键值对：用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代 表键值，value表示与key对应的信息
STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层，容器中的元素是一个有序的序列
set
一、set介绍
set是按照特定顺序存储唯一元素的容器
set中的每个元素不可以重复，也不可以更改（为const），但是可以在容器中增加和删除
在内部，set中的元素始终按照其内部比较对象（类型为 Compare）指示的特定严格弱排序标准按其键排序
set的主要功能是排序+去重
set通常用二叉搜索树实现
1.与map/multimap不同，map/multimap中存储的是真正的键值对，set中只放 value，但在底层实际存放的是由构成的键值对
2.set中插入元素时，只需要插入value即可，不需要构造键值对
3.在set中查找一个特定元素的时间复杂度为log2(N)，即二分查找
二、set接口
1.容量操作
| 函数名称 | 功能说明 |
| empty() | 检验set是否为空 |
| size() | 返回容器大小 |
| max_size() | 返回容器最大容量 |
2.修改操作
| 函数名称 | 功能说明 |
| insert() | 默认尾插数据，如果数据已存在会返回现有元素迭代器 |
| erase() | 删除数据 |
| find() | 查找数据，返回数据迭代器 |
| clear() | 清空set容器 |
| count() | 对特定数值进行计数 |
#include<set>
#include<iostream>using namespace std;void test_1()
{cout << "test_1" << endl;set<int> s1;s1.insert(1);s1.insert(2);s1.insert(3);s1.insert(1);s1.insert(4);s1.insert(5);s1.insert(5);for (auto num : s1){cout << num << " ";}cout << endl;
}void test_2()
{cout << "test_2" << endl;set<int> s2;s2.insert(2);s2.insert(4);s2.insert(6);s2.insert(0);s2.insert(1);auto it = s2.begin();auto end = s2.end();while (it != end){cout << *it << " ";it++;}cout << endl;set<int>::reverse_iterator rit = s2.rbegin();set<int>::reverse_iterator rend = s2.rend();while (rit != rend){cout << *rit << " ";rit++;}cout << endl;
}void test_3()
{cout << "test_3" << endl;set<int> s3;s3.insert(2);s3.insert(4);s3.insert(6);s3.insert(0);s3.insert(1);int x;while (cin >> x){auto ret = s3.find(x);if (ret != s3.end()){cout << "在" << endl;}else{cout << "不在" << endl;}}
}void test_4()
{cout << "test_4" << endl;multiset<int> ms1;ms1.insert(2);ms1.insert(4);ms1.insert(6);ms1.insert(0);ms1.insert(1);ms1.insert(1);ms1.insert(2);ms1.insert(3);ms1.insert(4);multiset<int>::iterator it = ms1.begin();while (it != ms1.end()){cout << *it << " ";it++;}cout << endl;//如果有多个相同key，find返回中序的第一个keyauto num = ms1.find(1);while (num != ms1.end() && *num == 1){cout << *num << " ";num++;}cout << endl;
}int main()
{test_1();test_2();//test_3();test_4();return 0;
}三、multiset介绍
multiset是按照特定顺序存储元素的容器，其中多个元素可以具有等效值
相较于set，multiset允许有多个重复值出现，更符合单纯的排序，而非去重
其余属性特征与set类似
map
一、map介绍
map是关联容器，用于存储由键值和映射值的组合形成的元素，遵循特定顺序
在map中，键值通常用于对元素进行排序和唯一标识，而映射值存储与此键关联的内容。键和映射值的类型可能不同
在内部，map中的元素始终按照其内部比较对象（类型为 Compare）指示的特定严格弱排序标准按其键排序
map中的映射值可以通过其相应的键使用括号运算符 （operator[ ]） 直接访问
map通常用二叉搜索树实现
二、map接口
1.容量操作
| 函数名称 | 功能说明 |
| empty() | 检验map是否为空 |
| size() | 返回容器大小 |
| max_size() | 返回容器最大容量 |
2.修改操作
| 函数名称 | 功能说明 |
| insert() | 默认尾插数据，如果数据已存在会返回现有元素迭代器 |
| erase() | 删除数据 |
| find() | 查找数据，返回数据迭代器 |
| clear() | 清空map容器 |
| count() | 对特定数值进行计数 |
其中insert如果插入的是相同的key，则会插入失败；value并不影响插入结果
3.访问操作
| 函数名称 | 功能说明 |
| operator[ ] | 如果 k 与容器中元素的键匹配，则该函数返回对其映射值的引用 如果 k 与容器中任何元素的键不匹配，则该函数将插入具有该键的新元素，并返回对其映射值的引用。请注意，这始终将容器大小增加 1，即使没有为元素分配映射值（元素是使用其默认构造函数构造的） |
| at | 返回对用键 k 标识的元素的映射值的引用。 如果 k 与容器中任何元素的键不匹配，则该函数将引发out_of_range异常 |
mapped_type& operator[] (const key_type& k);[ ]实际上具有四个功能：①插入②修改③插入+修改④查找。其中修是通过返回&value进行修改
#include<map>
#include<iostream>
#include<string>using namespace std;void test_1()
{map<string, string> dict;//pair是采用匿名构造的方法，先构造了一个键值对，然后将键值对插入dictdict.insert(pair<string, string>("sort", "排序"));dict.insert(pair<string, string>("num", "数字"));dict.insert(pair<string, string>("dict", "字典"));dict.insert(pair<string, string>("name", "名字"));//实际上常用的是make_pair，make_pair是一个函数模板，本质上还是调用匿名构造//但是函数内部会调用隐式类型转换dict.insert(make_pair("test", "测试"));dict.insert(make_pair("example", "案例"));dict.insert(make_pair("milk", "牛奶"));//map<string, string>::iterator dit = dict.begin();auto dit = dict.begin();while (dit != dict.end()){cout << (*dit).first << ":" << (*dit).second<< endl;++dit;}cout << endl;
}void test_2()
{string arr[] = { "狗","猫","猴子","猫","猴子","猴子","猫","猴子","猫","狗","狗","猫","猫" };map<string, int> countMap;//for (auto& a : arr)//{// auto ret = countMap.find(a);// if (ret == countMap.end())// {// countMap.insert(make_pair(a, 1));// }// else// {// ret->second++;// }//}for (auto& e : arr){countMap[e]++;//这里的方括号被重载为取value，因此需上面的循环计算}for (auto num : countMap){cout << num.first << ":" << num.second << " ";}cout << endl;
}void test_3()
{map<string, string> dict;dict["left"];//插入,key= "left" value=""dict["right"] = "右边";//插入+修改,key="right",value="右边"dict["length"] = "(长)";//插入+修改dict["length"] = "(长度)";//修改cout << dict["left"] << endl;//查找cout << dict["right"] << endl;//查找cout << dict["length"] << endl;//查找
}
int main()
{test_1();test_2();test_3();return 0;
}
