目录
一、预备知识：
1、关联式容器：
在以前阶段，已经接触过STL中的部分容器，比如：vector、list、deque等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。
那什么是关联式容器？它与序列式容器有什么区别？
关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，<key,value> 结构就是根据键值key以某种特定的方式来存放的，而value则是通过寻找key所在的位置，就可以找到value了。比如在下面中，就是一个<key, value>结构，可以通过中文（key）来找到每一个对应的英文（value），也可以说这些value是通过每个对应的key找到的。
2、键值对：
用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。
如上所示：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。
在标准库中提供了类似下面pair这种结构体来进行操作：
pair作用是将两个普通元素first和second（可以是 C++ 基本数据类型、结构体、类自定的类型）创建成一个新元素<first, second>。
#include<iostream>
using namespace std;
namespace ppr
{
//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)
{}
};
}
int main()
{
pair<string, int> p1("hehe", 888);
ppr::pair<int, string> p2(999, "hehe");
cout << "p1:" << p1.first << " " << p1.second << endl;
cout << "p2:" << p2.first << " " << p2.second << endl;
return 0;
}pair中的first表示键值，second则表示实值，在给关联式容器中插入数据时，可以构建pair对象，毕竟存在模版参数，所以自己来控制pair的两个类型，就可以通过first来找到second。
比如上面就构建了一个键值key为string，实值value为int的键值对p1和键值key为int，实值value为string的键值对p2，其中pair中的first是key，second是value。
除了以上这种方法，在库中设了一个函数模版make_pair，可以自主传参，从而去构建对象
make_pair在库中的实现如下：
template <class T1,class T2>
pair<T1,T2> make_pair (T1 x, T2 y)
{
return ( pair<T1,T2>(x,y) );
}
编译器会将这个函数转化成内联函数，这样话就节省了很多时间，但也不会造成过多的空间消耗。
3、树形结构的关联式容器：
根据应用场景的不同，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。
树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。
C++ 11 还新增了4种哈希容器：unordered_map，unordered_multimap，unordered_set，unordered_multiset。但是哈希容器底层采用的是哈希表，而不是红黑树。
不同的是哈希结构的关联式容器比给予树形结构的关联式容器，提高添加和删除元素的速度以及提高查找算法的效率。
二、set：
1、set的介绍：
set是按照一定次序存储元素的容器，它是key结构的，只包含一个键值，如上的官方文档中，T就是set的键值类型，Compare是根据后面参数判断是升序还是降序，Alloc是空间配置器。
理解：
set中的元素不可以重复(因此可以使用set进行去重)，使用set的迭代器遍历set中的元素，可以得到有序序列。
2、使用：
1、set的构造：
int main()
{
set<int> s1;
cout << "构造空的set：s1" << endl;
set<int>::iterator it1 = s1.begin();
while (it1 != s1.end())
{
cout << *it1 << " ";
it1++;
}
cout << endl;
int arr[] = { 5,2,2,1,5,6,3,2,7,8 };
set<int> s2(arr, arr + sizeof(arr)/sizeof(arr[0]));
cout << "用区间元素构造set：s2" << endl;
set<int>::iterator it2 = s2.begin();
while (it2 != s2.end())
{
cout << *it2 << " ";
it2++;
}
cout << endl;
cout << "set的拷贝构造：s3" << endl;
set<int> s3(s2);
set<int>::iterator it3 = s3.begin();
while (it3 != s3.end())
{
cout << *it3 << " ";
it3++;
}
cout << endl;
return 0;
}
通过以上代码可以看到，set构造后通过迭代器遍历会去重和排序，去重实质上是如果在set中存在就不会insert进去。
2、set的各种功能：
功能样例：
int main()
{
vector<int> arr1 = { 1,2,3,4,6,7,8,9,0 };
set<int> s1(arr1.begin(), arr1.end());
cout << "迭代器遍历容器" << endl;
set<int>::iterator it1 = s1.begin();
while (it1 != s1.end())
{
cout << *it1 << " ";
it1++;
}
cout << endl;
cout << "insert 元素:" << endl;
s1.insert(99);
s1.insert(5);
s1.insert(-1);
for (const auto& e : s1)
cout << e << " ";
cout << endl;
cout << "erase 元素:" << endl;
s1.erase(5);
s1.erase(7);
s1.erase(-1);
for (const auto& e : s1)
cout << e << " ";
cout << endl;
vector<int> arr2 = { 11, 22, 88, 33, 55, 44, 99 };
set<int> s2(arr2.begin(), arr2.end());
cout << "s2遍历:" << endl;
for (const auto& e : s2)
cout << e << " ";
cout << endl;
cout << "s1 和 s2交换后:" << endl;
s1.swap(s2);
cout << "s1:" << endl;
for (const auto& e : s1)
cout << e << " ";
cout << endl;
cout << "s2:" << endl;
for (const auto& e : s2)
cout << e << " ";
cout << endl;
cout << "s1.find(44): " << endl;
cout << (s1.find(44) != s1.end()) << endl;
set<int> s3(s1.find(44), s1.end());
//找到后返回当前位置的迭代器
cout << "s3:" << endl;
for (const auto& e : s3)
cout << e << " ";
cout << endl;
cout << "s1.find(4): " ;
cout << (s1.find(4) != s1.end()) << endl;
cout << "s1的size:" << s1.size() << endl;
cout << "s2的size:" << s2.size() << endl;
cout << "s3的size:" << s3.size() << endl << endl;
//count是计算容器中指定元素的个数的，但是set的元素不能有多个，所以count也就只能统计在不在
vector<int> arr = {1,3,5,6,7,8,0};
set<int> s5(arr.begin(), arr.end());
for (int i = 0;i<10;i++)
{
if (s5.count(i))
cout << i << " 在 s5 中" << endl;
else
cout << i << " 不在 s5 中" << endl;
}
return 0;
}
在set中，默认是升序的，但是可以改变第二个模版参数Compare来进行控制升降序
int main()
{
vector<int> arr3 = { 11,22,33,44,55,66,77,88,99,100 };
set<int> s6(arr3.begin(), arr3.end());
set<int, greater<int>> s7(arr3.begin(), arr3.end());
cout << "s6:";
for (const auto& e : s6)
cout << e << " ";
cout << endl;
cout << "s7:";
for (const auto& e : s7)
cout << e << " ";
cout << endl;
return 0;
}
3、multiset
multiset 与 set 的区别：set支持唯一键值，每个元素值只能出现一次；而 multiset 中同一值可以出现多次。
其余操作基本是相同的。
vector<int> arr = { 1,2,2,2,2,3,3,3,4,5,6,7,8,9,9 };
multiset<int> ms(arr.begin(), arr.end());
for (auto e : ms)
cout << e << " ";
cout << endl;
注意：
在查找后返回的是第一个的迭代器，并且count计数也在这用。
int main()
{
vector<int> arr = { 1,2,2,2,2,3,3,3,4,5,6,7,8,9,9 };
multiset<int> ms(arr.begin(), arr.end());
for (auto e : ms)
cout << e << " ";
cout << endl;
cout << "查找3，返回的是第一个出现的3的迭代器" << endl;
multiset<int>::iterator it = ms.find(3);
while (it != ms.end())
{
cout << *it << " ";
it++;
}
cout << endl;
cout << "count在这也很好用" << endl;
cout << "计数2 : " << ms.count(2) << endl;
cout << "计数3 : " << ms.count(3) << endl;
return 0;
}
三、map：
1、map的介绍：
1、map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
2、在map中，键值key通常用于排序惟一的标识元素，而值value中存储与此键值key关联的 内容。
3、键值key和值value的类型可以不同，并且在map的内部，key与value通过成员类型 value_type绑定在一起，为其取别名称为pair。
比如：
在英汉对应的词典中就用到了这种KV模型
如上所示文档中，Key就是键值对中的键值，T则是键值对中的实值，在 map 中会用到前面提到过的pair结构，其中 first 表示键值，second 表示实值。
在访问map中的键值和实值时，需要通过pair对象指定访问，比如m.first
2、使用：
1、map的构造：
int main()
{
map<int, int> m1;
vector<pair<int, string>> arr = { make_pair(1,"one"),make_pair(2,"two"),make_pair(3,"three")
,make_pair(4,"four"),make_pair(5,"five"),make_pair(6,"six") };
map<int, string> m2(arr.begin(), arr.end());
for (auto& e : m2)
{
cout << e.first << " " << e.second << endl;
}
cout << endl;
cout << "m3拷贝构造m2" << endl;
map<int, string> m3(m2);
for (auto& e : m3)
{
cout << e.first << " " << e.second << endl;
}
cout << endl;
return 0;
}
2、map的各种功能：
总的来说和set大差不差，主要是多了operator[ ]
功能样例：
int main()
{
vector<pair<int, string>> arr1 = { make_pair(1,"one"),make_pair(2,"two"),make_pair(3,"three")
,make_pair(4,"four"),make_pair(5,"five"),make_pair(6,"six") };
map<int, string> m1(arr1.begin(), arr1.end());
cout << "迭代器遍历m1：" << endl;
map<int, string>::iterator it1 = m1.begin();
while (it1 != m1.end())
{
cout << it1->first << " " << it1->second << endl;
it1++;
}
cout << endl;
cout << "插入元素后" << endl;
m1.insert({ 7,"seven" });
for(auto& e : m1)
cout << e.first << " " << e.second << endl;
cout << "根据键值 删除元素后" << endl;
m1.erase(1);
m1.erase(7);
for (auto& e : m1)
cout << e.first << " " << e.second << endl;
cout << endl;
cout << "构造新的m2" << endl;
vector<pair<int, string>> arr2 = { make_pair(11,"eleven"),make_pair(12,"twelve"),make_pair(13,"thirteen")
,make_pair(14,"fourteen"),make_pair(15,"fifteen"),make_pair(16,"sixteen") };
map<int, string> m2(arr2.begin(), arr2.end());
for (auto& e : m2)
cout << e.first << " " << e.second << endl;
cout << "m1和m2交换后：" << endl;
m1.swap(m2);
cout << "m1:" << endl;
for (auto& e : m1)
cout << e.first << " " << e.second << endl;
cout << "m2:" << endl;
for (auto& e : m2)
cout << e.first << " " << e.second << endl;
cout << endl<< "根据键值查找元素：" << endl;
cout << "m1.find(11): ";
cout << (m1.find(11) != m1.end()) << endl << endl;
cout << "m1的size:" << m1.size() << endl;
cout << "m2的size:" << m2.size() << endl;
cout << endl;
map<int, int> m3;
cout << "m1的empty:" << m1.empty() << endl;
cout << "m3的empty:" << m3.empty() << endl;
return 0;
}
3、map的operator[ ]
operator[]的原理是：
用<key, T()>构造一个键值对，然后调用insert()函数将该键值对插入到map中
如果key已经存在，插入失败，insert函数返回该key所在位置的迭代器
如果key不存在，插入成功，insert函数返回新插入元素所在位置的迭代器
operator[]函数最后将insert返回值键值对中的value(实值)返回。
也就是说：
operator[ ]返回的是当前键值对应的实值，如果当前键值不存在，则会插入新的键值对，然后在返回新的键值对的实值。
int main()
{
vector<pair<int, string>> arr1 = { make_pair(1,"one"),make_pair(2,"two"),make_pair(3,"three")
,make_pair(4,"four"),make_pair(5,"five"),make_pair(6,"six") };
map<int, string> m1(arr1.begin(), arr1.end());
cout << m1[1] << endl;
cout << m1[3] << endl;
cout << m1[7] << endl;
m1[7] = "seven";
m1[8];
m1[9] = "nine";
for (auto& e : m1)
cout << e.first << " " << e.second << endl;
return 0;
}
应用（计数）
int main()
{
vector<string> v1 = { "苹果","香蕉","西瓜","西瓜" ,"西瓜" ,"西瓜","香蕉","香蕉","苹果" };
map<string, int> m1;
for (auto& e : v1)
{
map<string, int>::iterator ret = m1.find(e);
if (ret == m1.end())
m1.insert(make_pair(e, 1));
else
ret->second++;
}
for (auto& e : m1)
cout << e.first << ":" << e.second << endl;
return 0;
}
那么operator[]就可以优化上述的代码：
int main()
{
vector<string> v1 = { "苹果","香蕉","西瓜","西瓜" ,"西瓜" ,"西瓜","香蕉","香蕉","苹果" };
map<string, int> m1;
for (auto& e : v1)
m1[e]++;
for (auto& e : m1)
cout << e.first << ":" << e.second << endl;
return 0;
}
3、multimap:
multimap和map的关系，和multiset和set的关系差不多。都是将容器中不能重复的值 变为 可以存在重复的值。
int main()
{
vector<pair<int, string>> arr1 = { make_pair(1,"one"),make_pair(2,"two"),make_pair(3,"three")
,make_pair(4,"four"),make_pair(5,"five"),make_pair(6,"six") };
multimap<int, string> m1(arr1.begin(), arr1.end());
map<int, string> m2(arr1.begin(), arr1.end());
m1.insert(make_pair(2, "two"));
m1.insert(make_pair(2, "two"));
m1.insert(make_pair(2, "two"));
m1.insert(make_pair(7, "seven"));
cout << "multimap<int, string> m1(arr1.begin(), arr1.end());" << endl;
for (auto& e : m1)
cout << e.first << " " << e.second << endl;
cout << endl;
m2.insert(make_pair(2, "two"));
m2.insert(make_pair(2, "two"));
m2.insert(make_pair(2, "two"));
m2.insert(make_pair(7, "seven"));
cout << "map<int, string> m2(arr1.begin(), arr1.end());" << endl;
for (auto& e : m2)
cout << e.first << " " << e.second << endl;
return 0;
}
注意：
因为multimap可以存在数据重复，那么就不能够提供[]运算符，因为不知道是修改的哪一个
map可以随便修改value的值
