STL

map

关联容器，关联数组，“高级数组”
通用于任意格式对象的计数，如cnt["hello"]=1，其中"hello"是key，1是value
插入和查询复杂度为O(logn)

#include<map>

//定义cmp函数，用于map对key的排序
struct cmp
{
    bool operator () (const T1 &a, const T1 &b)const
    {
        ...
    }
};
/*必须用结构体；重定义括号运算符（map底层调用cmp(a,b)比较大小）；内部比较必须为严格大或严格小（map底层调用!cmp(a,b)&&!cmp(b,a)判断是否相等）*/

//声明map
map<T1,T2> m;
map<T1,T2,cmp> m2;

//清空map
m.clear();

//插入(a,b)
m.insert(pair<T1,T2>(a,b));
m.insert(map<T1,T2>::value_type(a,b));
/*以上两种方法效果相同。如果待插入数据key值与已插入数据key值重复，插入失败。insert函数返回一个pair(map迭代器，true/false)*/
m[a]=b;
/*key值重复时，后面的数据覆盖前面的数据*/

//获得map的大小
int sz=m.size();

//遍历map
for(map<T1,T2>::iterator it=m.begin();it!=m.end();it++)cout<<it->first<<'	'<<it->second<<endl;
for(map<T1,T2>::reverse_iterator it=m.rbegin();it!=m.rend();it++)cout<<it->first<<'	'<<it->second<<endl;
for(int i=1;i<=sz;i++)cout<<m[i]<<endl;
/*[begin,end)=(rend,rbegin]*/

//查询a：对应值，存在性，上下界
cout<<m[a]<<endl;
cout<<m.count(a)<<endl;
map<T1,T2>::iterator it=m.find(a);
/*count()函数返回0或1，对应a不在map中和在map中；find()函数返回a在map中的迭代器，如果没找到，返回m.end()*/
map<T1,T2>::iterator it=m.lower_bound(a);
map<T1,T2>::iterator it=m.upper_bound(a);
/*[lower_bound,upper_bound)*/

//删除(a,b)
m.erase(m.find(a));
m.erase(a);
m.erase(m.begin(),m.end());
/*erase的三种重载形式*/

priority_queue

比较

container	cmp
sort
priority_queue
map
set

比较函数

//两个关键字为例
bool cmp(T a,T b)
{
    return a.x<b.y||(a.x==b.y&&a.y<b.y);
}

内部比较

struct node
{
	...
	bool operator < (const node &a)const
	{
		...
	}
}