c++关联容器概述

关联容器支持高效的关键字查找和访问，两个主要的关联容器类型是map和set

标准库提供以下8个关联容器：

1、定义一个map时，必须既指明关键字类型又指明值类型；而定义一个set时，只需指明关键字类型，因为set中没有值，故set可以用另一个同类型的容器或者从一个值范围来初始化

2、对于multimap和multiset同样，不过允许出现重复的关键字

vectorvec{ 1,5,3,4,4,4,4 };
mapmp;
setst(vec.begin(), vec.end());
multisetmst(vec.begin(), vec.end());

1、对于有序容器，关键字类型必须定义元素比较的方法，默认情况下，标准库使用关键字类型的<运算符来比较两个关键字（因此自定义的结构体作为关键字时需要注意）

2、用来组织一个容器中元素的操作的类型也是该容器类型的一部分，为了指定使用自定义的操作，必须在定义关联容器类型时提供此操作的类型

3、STL标准库中，包含几个可供关联式容器使用的排序规则

4、具体写法如下：

标准库类型：

bool cmp(const int& a, const int& b)
{
	return a > b;
}
setst(cmp);
mapmp(cmp);
//或者
struct cmp
{
	bool operator()(const int& a, const int& b)const
	{
		return a > b;
	}
};
setst;
mapmp;
//或者
map>mp;    //标准库中的比较函数
multiset>st;

自定义类：

struct node
{
	int y;
	string s;
};
bool cmp(const node& a, const node& b)
{
	return a.y > b.y;
}
setst(cmp);
mapmp(cmp);
//或者
struct node
{
	int y;
	string s;
	friend bool operator<(const node& a, const node& b)
	{
		return a.y > b.y;
	}
};
setst;
mapmp;

1、pair保存两个数据成员，类似容器，pair是一个用来生成特定类型的模板，类似于一个只有两个成员的结构体（类）

2、pair上的操作

pair p;			//p是一个pair，两个类型分别为T1和T2的成员都进行了值初始化
pair p(v1, v2);	    //first和second成员分别用v1和v2进行初始化
pair p = { v1,v2 };	//等价于p(v1, v2)
make_pair(v1, v2);		//返回一个用v1和v2初始化的pair，pair的类型从v1和v2的类型推断出来
p.first;	p.second;	//返回p的名为firs、second的（公有）数据成员
p1 relop p2;		   // 关系运算符（<、>、 <= 、 >= ）按字典序定义
p1 == p2; p1 != p2;    //相等性判断利用元素的 == 运算符实现

对于set类型，key_type，value_type是一样的，set的值就是关键字

对于map类型，元素是关键字-值对，每个元素是一个pair对象，由于不能改变关键字部分，故为const类型

我们用作用域运算符来提取一个类型的成员

key_type        //map容器的关键字的类型
mapped_type     //每个关键字对应的值的类型
value_type      //对于map为pair，对于set即key_type

set::value_type v1;        // v1是一个string
set::key_type v2;          // v2是一个string
map::value_type v3;   // v3是一个pair
map::key_type v4;     // v4是一个string
map::mapped_type v5;  // v5是一个int