关联式容器
C++STL包含了序列式容器和关联式容器：
- 序列式容器：vector/list/deque
- 关联式容器：set/map等
关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高。
键值对
用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量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)
{}
};
树形结构的关联式容器
根据应用场景的不桶，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。
树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。unordered系列均为哈希结构。
set
set的介绍
- set是按照一定次序存储元素的容器。
- 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
- 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
- set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。
- set在底层是用二叉搜索树(红黑树)实现的。
set的使用
#include <iostream>
#include <set>
using namespace std;
int main()
{
//插入元素（去重且排序）
set<int> s; // 默认是升序
// set<int, greater<int>> s; // 这样是降序
s.insert(4);
s.insert(4);
s.insert(1);
s.insert(3);
s.insert(6);
s.insert(6);
// 迭代器遍历
set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
*it++;
}
cout << endl;
// 范围for遍历
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
// 删除3 （存在）
s.erase(3);
// 删除4
set<int>::iterator pos = s.find(4);
if (pos != s.end())
{
s.erase(pos);
}
// s.erase(100); // 删除不存在的值没有影响
// s.erase(s.end()); 会崩掉
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
//容器中值为4的元素个数
cout << s.count(6) << endl; // 1
//容器大小
cout << s.size() << endl; // 4
//清空容器
s.clear();
//容器判空
cout << s.empty() << endl; // 1
return 0;
}
multiset
multiset容器与set容器的底层实现一样，都是平衡搜索树（红黑树）;
multiset容器和set容器的唯一区别就是multiset容器当中存储的元素是可以重复的。
#include <iostream>
#include <set>
using namespace std;
int main()
{
// 查找在不在
// 插入元素（重复且排序）
multiset<int> ms;
ms.insert(1);
ms.insert(2);
ms.insert(3);
ms.insert(3);
ms.insert(2);
ms.insert(3);
for (auto e : ms)
{
cout << e << " ";
}
cout << endl; //1 2 2 3 3 3 4
return 0;
}
multiset
- find()：返回第一个中序的第一个val
- count()：返回值为val的元素个数
set
- find()：返回值为val的元素的迭代器l
- count()：值为val的元素存在则返回1，不存在则返回0
map
map的介绍
- map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
- 在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:typedef pair<const key, T> value_type;
- 在内部，map中的元素总是按照键值key进行比较排序的。
- map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
- map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
- map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。
map的使用
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<string, string> m;
// 构造匿名对象插入
m.insert(pair<string, string>("left", "左边"));
m.insert(pair<string, string>("right", "右边"));
m.insert(pair<const char*, const char*>("up", "上边"));
// 调用make_pair函数模板插入
// 我们只需向make_pair函数传入key和value，
// 该函数模板会根据传入参数类型进行自动隐式推导，
// 最终构造并返回一个对应的pair对象。
m.insert(make_pair("down", "下边")); // 推荐这个最优（能省即省，能少敲就少敲，qwq）
// 迭代器遍历
map<string, string>::iterator it = m.begin();
while (it != m.end())
{
cout << "<" << (*it).first << "," << (*it).second << ">" ;
// it.operatot() 返回 *pair
// cout << "<" << it.operator->()->first << "," << it.operator->()->second << ">";
cout << "<" << it->first << "," << it->second << ">" ;
cout << endl;
++it;
}
cout << endl;
// 范围for遍历
for (auto e : m)
{
cout << "<" << e.first << "," << e.second << ">";
cout << endl;
}
cout << endl;
// pair里的 key有const，而value没有const
for (auto& e : m)
{
e.first += '1'; // 不可修改
e.second += '1'; // 可修改
cout << "<" << e.first << "," << e.second << ">";
cout << endl;
}
cout << endl;
return 0;
}
make_pair函数模板：
template <class T1, class T2>
pair<T1, T2> make_pair(T1 x, T2 y)
{
return (pair<T1, T2>(x, y));
}
insert的返回值
insert函数的返回值也是一个pair对象，该pair对象中第一个成员的类型是map的迭代器类型，第二个成员的类型的一个bool类型，具体含义如下：
- 若待插入元素的键值key在map当中不存在，则insert函数插入成功，并返回插入后元素的迭代器和true。
- 若待插入元素的键值key在map当中已经存在，则insert函数插入失败，并返回map当中键值为key的元素的迭代器和false。
map的[ ]
mapped_type& operator[] (const key_type& k);
[ ]运算符重载实现的逻辑实际上就是以下三个步骤：
- 调用insert函数插入键值对。
- 拿出从insert函数获取到的迭代器。
- 返回该迭代器位置元素的值value。
mapped_type& operator[] (const key_type& k) { //1、调用insert函数插入键值对 pair<iterator, bool> ret = insert(make_pair(k, mapped_type())); //2、拿出从insert函数获取到的迭代器 iterator it = ret.first; //3、返回该迭代器位置元素的值value return it->second; }
- 如果k不在map中，则先插入键值对<k, v()>，然后返回该键值对中v对象的引用。
- 如果k已经在map中，则返回键值为k的元素对应的v对象的引用。
#include <iostream>
#include <map>
using namespace std;
int main()
{
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
map<string, int> countMap;
for (auto& str : arr)
{
//auto ret = countMap.find(str);
//if (ret == countMap.end())
//{
// // 么有表示第一次出现，插入
// countMap.insert(make_pair(str, 1));
//}
//else
//{
// // 次数++
// ret->second++;
//}
countMap[str]++; // 6 3 2
}
for (auto& str : arr)
{
countMap[str]++; // 12 6 4
}
for (auto& kv : countMap)
{
cout << kv.first << ":" << kv.second << endl;
}
return 0;
}
multimap
multimap容器与map容器的底层实现一样，也都是平衡搜索树（红黑树）;
multimap容器和map容器的区别与multiset容器和set容器的区别一样，multimap容器当中存储的元素是可以重复的。
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main()
{
multimap<string, string> mm;
//插入元素（重复且排序）
mm.insert(make_pair("left", "左边"));
mm.insert(make_pair("left", "左边"));
mm.insert(make_pair("right", "右边"));
mm.insert(make_pair("up", "上边"));
mm.insert(make_pair("left", "左边"));
mm.insert(make_pair("right", "右边"));
mm.insert(make_pair("up", "上边"));
for (auto e : mm)
{
cout << "<" << e.first << "," << e.second << ">";
cout << endl;
}
cout << endl;
return 0;
}
multimap
- find()：返回底层搜索树中序的第一个键值为key的元素的迭代器
- count()：返回键值为key的元素个数
map
- find()：返回值为key的元素的迭代器
- count()：键值为key的元素存在则返回1，不存在则返回0