3.9 map/multimap容器
3.9.1 map基本概念
简介：
map中所有元素都是pair
pair中第一个元素为key（键值），起到索引作用，第二个元素为value（实值）
所有元素都会根据元素的键值自动排序
本质：
map/multimap属于关联式容器，底层结构是用二叉树实现
优点：
可以根据key值快速找到value值
map/multimap区别：
map不允许容器中有重复的key值元素
multimap允许容器中有重复key值元素
3.9.2 map构造和赋值
构造函数：
map<T1,T2> mp;
map(const map &mp);
赋值操作：
map &operator=(const map &mp);
3.9.3 map大小和交换
函数原型：
size();
empty();
swap(mp);
3.9.4 map插入和删除
函数原型：
1 insert(elem);
2 clear();
3 erase(pos);//返回下一元素迭代器
4 erase(beg,end);//返回下一元素迭代器
5 erase(key);
3.9.5 map查找和统计
函数原型：
find(key);//若存在，返回该键的元素的迭代器；若不存在，返回mp.end();
count(key);//统计key的元素个数（对map 仅为0/1）
3.9.6 map容器排序
默认排序规则为：按照key值从小到大排序
改变排序规则--利用仿函数
4 STL-函数对象
4.1函数对象
4.1.1简述
概念：
重载函数调用操作符的类，其对象常称为函数对象；
函数对象使用重载的()时，行为类似函数调用，也叫仿函数；
本质：
函数对象（仿函数）是一个类，不是函数
4.1.2函数对象使用
特点：
1函数对象在使用时，可以像普通函数那样调用，可以有参数，可以有返回值
2函数对象超出普通函数概念，函数对象可以有自己的状态、
3函数对象可以作为参数传递
4.2谓词
4.2.1谓词概念
1 返回bool类型的仿函数称为谓词
2 如果operator()接受一个参数，称为一元谓词
3 如果operator()接受两个参数，称为二元谓词
4.3内建函数对象
4.3.1内建函数对象意义
概念：
STL内建了一些函数对象
分类：
算术仿函数
关系仿函数
逻辑仿函数
用法：
这些仿函数所产生的对象、用法和一般函数完全相同；
使用内建函数对象，需要引入头文件#include<functional>
4.3.2算术仿函数
功能：实现四则运算
其中negate是一元运算，其他都是二元运算；
仿函数原型：
1 template<class T> T plus<T>
2 template<class T> T minus<T>
3 template<class T> T multiplies<T>
4 template<class T> T divides<T>
5 template<class T> T modulus<T>//取模仿函数
6 template<class T> T negate<T>//取反仿函数
4.3.3关系仿函数
功能：实现关系对比
仿函数原型：
1 template<class T> bool equal_to<T>
2 template<class T> bool not_equal_to<T>
3 template<class T> bool greater<T>//大于
4 template<class T> bool greater_equal<T>
5 template<class T> bool less<T>
6 template<class T> bool less_equal<T>
4.3.4逻辑仿函数
功能：实现逻辑运算 （很少使用）
函数原型：
1 template<class T> bool logical_and<T>
2 template<class T> bool logical_or<T>
3 template<class T> bool logical_not<T>
5 STL-常用算法
概述：
1 算法主要是由头文件<algorithm> <functional> <numeric>组成；
2 <algorithm>是所有STL头文件中最大的一个，范围涉及到 比较、交换、查找、遍历、复制、修改等等；
3 <numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数；
4 <functional>定义了一些模板类，用以声明函数对象；
5.1常用遍历算法
5.1.1 for_each--最常用
功能：实现遍历容器
函数原型：
for_each(iterator beg,iterator end,_func);//_func函数或函数对象
5.1.2 transform
功能：搬运容器到另一个容器中
函数原型：
transform(iterator beg1,iterator end1,iterator beg2,_func);
5.2常用查找算法
算法简介：
find;
find_if;//按条件查找
adjacent_find;//查找相邻重复元素
binary_search//二分查找
count;
count_if;//按条件统计
分类：
1.内置类型
2.自定义数据类型 必须重载==
5.2.1 find
查找成功，返回指定元素迭代器；查找失败，返回结束迭代器end();
函数原型：
finc(iterator beg;iterator end,value);//按值查找
注意：
1 查找自定义数据类型 必须重载== (cost &)
2 返回的是迭代器
5.2.2 find_if
功能：按条件查找元素
函数原型：
find_if(iterator beg,iterator end,_Pred);
//_Pred函数或者谓词（返回bool类型的仿函数）
5.2.3 adjacent_find
功能：查找相邻重复元素
函数原型：
adjacent_find(iterator beg,iterator end);
//查找相邻重复元素，返回相邻元素的第一个位置的迭代器
5.2.4 binary_search
功能：查找指定元素是否存在
函数原型：
bool binary_search(iterator beg,iterator end,value);
//在无序序列中不可用
注意：只适用于有序序列
5.2.5 count
函数原型：
count(iterator beg;iterator end,value);
5.2.6 count_if
功能：按条件统计元素个数
函数原型：
count_if(iterator beg,iterator end, _Pred);//_Pred谓词
5.3常用排序算法
算法简介：
sort;//排序
random_shuffle;//洗牌 指定范围内的元素随机调整次序
merge;//容器元素合并 并存储到另一容器中
reverse;//反转指定范围的元素
5.3.1 sort
函数原型：
sort(iterator beg,iterator end, _Pred);
//谓词可以改变排序规则
5.3.2 random_shuffle
功能：指定范围内的元素随机调整次序
函数原型：
random_shuffle(iterator beg,iterator end);
5.3.3 merge
功能：两个容器元素合并，并存储到另一容器中
函数原型：
merge(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest);
//注意：两个容器必须是有序的
//dest 目标容器开始迭代器
5.3.4 reverse
功能：反转容器内元素
函数原型：
reverse(iterator beg,iterator end);//指定范围
5.4常用拷贝和替换算法
算法简介：
copy;
replace;
replace_if;//按条件替换
swap;
5.4.1 copy
功能：容器内指定范围的元素拷贝到另一容器中
函数原型：
copy(iterator beg,iterator end,iterator dest);
注意：目标容器要提前开辟空间
5.4.2 replace
功能：指定范围内的旧元素修改为新元素
函数原型：
replace(iterator beg,iterator end,oldvalue,newvalue);
5.4.3 replace_if
功能：将范围内满足条件的元素，替换成指定元素
函数原型：
replace_if(iterator beg,iterator end, _Pred,newvalue);
5.4.4 swap
功能：互换两个容器的元素
函数原型：
swap(container c1,container c2);//必须同类型
5.5 常用算术生成算法
注意：算术生成算法属于小型算法，头文件为<numeric>
算法简介：
accumulate;//计算容器元素累计总和
fill;//向容器中添加元素
5.5.1 accumulate
函数原型：
accumulate(iterator beg,iterator end,value);
//value起始值
5.5.2 fill
函数原型：
fill(iterator beg,iterator end,value);
//value填充的值
5.6常用集合算法
算法简介：
set_intersection;//交集
set_union;//并集
set_difference;//差集
5.6.1 set_intersection
函数原型：
set_intersection(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest);
注意：
1 两个集合必须是有序的
2 目标容器开辟空间需要从两个容器中取小值
3 返回值是交集中最后一个元素位置
5.6.2 set_union
函数原型:
set_union(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest);
5.6.3 set_difference
函数原型：
set_difference(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest);
