第一节 关联容器
set/multiset/map/multimap
内部元素有序排列，新元素插入的位置决定于它的值，查找速度快。
除了各容器都有的函数外，还支持以下成员函数：
find: 查找等于某个值 的元素(x小于y和y小于x同时不成立即为相等)
lower_bound : 查找某个下界
upper_bound : 查找某个上界
equal_range : 同时查找上界和下界
count :计算等于某个值的元素个数(x小于y和y小于x同时不成立即为相等)
insert: 用以插入一个元素或一个区间
第二节 set和multiset
预备知识：pair模板
template<class _T1, class _T2>
struct pair{
typedef _T1 first_type;
typedef _T2 second_type;
_T1 first;
_T2 second;
pair():first(),second(){}//如果first和second是对象的话，就用无参构造函数来初始化
pair(const _T1&__a,const _T2&__b):first(__a),second(__b){}
//构造函数有两个静态变量__a和__b，分别用来初始化first和second
template<class _U1, class _U2>
pair(const pair<_U1,_U2>&__p):first(__p.first),second(__p.second){}
};
第三个构造函数是一个函数模板，用以下例子来示例一下：
pair<int, int>
p(pair<double, double>(5.5,4.6));
//p.first = 5, p.second = 4
1.multiset
template<class Key, class Pred = less<Key>, class A = allocator<Key> >
class multiset { …… };
在这里面，Pred类型的变量决定了multiset中的元素“一个比另一个小”是怎么定义的。multiset运行过程中，比较两个元素x，y的大小的做法，就是生成一个Pred类型的变量，假定为op，若表达式op<x,y>返回值为true，则x比y小。Pred的缺省值类型是less<Key>。
less模板：
template<class T>
struct less : public binary_function<T, T, bool>
{ bool operator()(const T& x, const T& y) { return x < y ; } const; };
//less模板是靠 < 来比较大小的
表2.1 multiset的成员函数
| 函数名 | 作用 |
| iterator find(const T &val) | 在容器中查找值为val的元素，返回其迭代器。如果找不到，返回end()。 |
| iterator insert(const T & val); | 将val插入到容器中并返回其迭代器。 |
| void insert( iterator first,iterator last); | 将区间[first,last)插入容器。 |
| int count(const T & val); | 统计有多少个元素的值和val相等。 |
| iterator lower_bound(const T & val); | 查找一个最大的位置it,使得[begin(),it)中所有的元素都比val小。（返回大于等于val的第一个数字的地址） |
| iterator upper_bound(const T & val); | 查找一个最小的位置it,使得[it,end())中所有的元素都比val大。（返回比val大的第一个数字的地址） |
| pair<iterator,iterator> equal_range(const T & val); | 同时求得lower_bound和upper_bound。 |
| iterator erase(iterator it); | 删除it指向的元素，返回其后面的元素的迭代器(Visual studio 2010上如此，但是在C++标准和Dev C++中，返回值不是这样)。 |
（1）multiset的用法
#include <set>
using namespace std;
class A { };
int main() {
multiset<A> a;
a.insert(A());//error
}
主函数中第一句话没有什么问题，但是第二句话存在问题。因为multiset<A> a等价于multiset<A, less<A>> a，这样插入元素的时候，multiset会将插入元素同已有元素进行比较。由于a中的元素都是A类型的，插入的也是一个A类型的，所以需要对A类型的对象进行比较，这要求A的对象能用<比较，即需要对<进行重载。
例程：
#include <iostream>
#include <set>
using namespace std;
template<class T>
void Print(T first, T last)
{
for(;first!=last;++first)
cout<<*first<<” “;
cout<< endl;
}
class A{
private:
int n;
public:
A(int _n){n = _n;}
friend bool operator<(const A &a1, const A &a2){return a1.n<a2.n;}
friend ostream & operator<<(ostream & o, const A &a2){o<<a2.n;return o;}
friend class MyLess;
};
struct MyLess{
bool operator ()(const A & a1, const A & a2)//按个位数比较
{return (a1.n%10)<(a2.n%10);}
};
typedef multiset<A> MSET1;
typedef multiset<A,MyLess> MSET2;//MSET用MyLess::operator()比较大小
int main(){
const int SIZE = 6;
A a[SIZE]={4,22,19,8,33,40};
MSET1 m1;
m1.insert(a,a+SIZE);
m1.insert(22);
cout<<“1)”<<m1.count(22)<<endl;//output:1)2
cout<<“2)”<<Print(m1.begin(),m1.end());//output: 2)4 8 19 22 22 33 40
MSET1::iterator pp = m1.find(19);
if(pp!=m1.end())
cout<<“found”<<endl;
cout<<“3}”;cout<<*m1.lower_bound(22)<<“,”<<*m1.upper_bound(22)<<endl;//output:22 23
pp = m1.erase(m1.lower_bound(22),m1.upper_bound(22));//pp指向被删除元素的下一个元素
cout<<“4)”;Print(m1.begin(),m1.end());//输出4 8 19 33 40
cout<<“5)”;cout<<*p>>endl;//输出33
MSET2 m2;
m2.insert(a,a+SIZE);
cout<<“6)”;Print(m2.begin(),m2.end());//输出6)40 22 33 4 8 19
return 0;
}
以上程序已弄明白，但是要多看看，理解下。
2.set
template<class Key, class Pred = less<Key>, class A = allocator<Key>>
class set{}
插入set中已有元素时，忽略插入。例程如下：
#include <iostream>
#include <set>
using namespace std;
int main() {
typedef set<int>::iterator IT;
int a[5] = { 3,4,6,1,2 };
set<int> st(a, a + 5);
pair<IT,bool> result;
result = st.insert(5);
if (result.second)
cout << *result.first << “inserted” << endl;
if (st.insert(5).second) cout << *result.first << endl;
else
cout << *result.first << “already exists” << endl;
pair<IT, IT>bounds = st.equal_range(4);
cout << *bounds.first << “.” << *bounds.second;
system(“pause”);
return 0;
}
定义的result是一个pair类型的对象，其里面的first是IT类型，second是bool类型（pair类定义见本节的预备知识）。下面得到的result对象里面的IT就是迭代器指向5所在位置，而second的值为true（因为插入成功）。
if (st.insert(5).second)这句话实际上是先执行了st.insert(5)之后，判断其second值是false还是true。由于前面已经插入了5，所以这里肯定插入不成功，所以second肯定是false。
第三节 map和multimap
1.multimap
template<class Key, class T, class Pred = less<Key>, class A = allocator<T>>
class multimap{
typedef pair<const Key, T>value_type;
};//Key代表关键字的类型
multimap中的元素由 <关键字,值>组成，每个元素是一个pair对象，关键字就是first成员变量,其类型是Key。
multimap 中允许多个元素的关键字相同。元素按照first成员变量从小到大排列，缺省情况下用 less<Key> 定义关键字的“小于”关系。
例程：
#include <iostream>
#include <map>
using namespace std;
int main() {
typedef multimap<int, double, less<int>> mmid;
mmid pairs;
cout << “1)” << pairs.count(15) << endl;
pairs.insert(mmid::value_type(15, 2.7));//typedef pair<const Key, T>value_type
pairs.insert(mmid::value_type(15, 99.3));
cout << “2)” << pairs.count(15) << endl;//求关键字等于15的个数，应该输出
pairs.insert(mmid::value_type(30, 111.11));
pairs.insert(mmid::value_type(10, 22.22));
pairs.insert(mmid::value_type(25, 33.333));
pairs.insert(mmid::value_type(20, 9.3));
for (mmid::const_iterator i = pairs.begin(); i != pairs.end(); ++i)
cout << “(” << i->first << “,” << i->second << “)” << “,”;
cout << endl;
system(“pause”);
return 0;
}
multimap例题：一个学生成绩录入和查询系统。接受以下两种输入：
Add name id score
Query score
name是个字符串，中间没有空格，代表学生姓名。id是个整数，代表学号 。score是个整数，表示分数。学号不会重复，分数和姓名都可能重复。
两种输入交替出现。第一种输入表示要添加一个学生的信息，碰到这种输入，就记下学生的姓名、id和分数。第二种输入表示要查询，碰到这种输入 ，就输出已有记录中分数比score低的最高分获得者的姓名、学号和分数。如果有多个学生都满足条件，就输出学号最大的那个学生的信息。如果找不到满足条件的学生，则输出“Nobody”。
输入样例：
Add Jack 12 78
Query 78
Query 81
Add Percy 9 81
Add Marry 8 81
Query 82
Add Tom 11 79
Query 80
Query 81
输出果样例：
Nobody
Jack 12 78
Percy 9 81
Tom 11 79
Tom 11 79
程序如下：
#include <iostream>
#include <map>
#include <string>
using namespace std;
class CStudent {
public:
struct CInfo
{
int id;
string name;
};
int score;
CInfo info;
};
typedef multimap<int, CStudent::CInfo> MAP_STD;//pair模板只允许first和second两个参数
int main() {
MAP_STD mp;
CStudent st;
string cmd;
while(cin>>cmd){
if (cmd == “Add”) {
cin >> st.info.name >> st.info.id >> st.score;
mp.insert(MAP_STD::value_type(st.score, st.info));
//mp.insert(make_pair(st.scorest.info));也可以
}
else if (cmd == “Query”) {
int score;
cin >> score;
MAP_STD::iterator p = mp.lower_bound(score);
if (p != mp.begin()) {
–p;
score = p->first;//比要查询分数低的最高分
MAP_STD::iterator maxp = p;//已经是比分数低的最高分的位置
int maxId = p->second.id;
for (; p != mp.begin() && p->first == score; –p) {
if (p->second.id > maxId)
{
maxp = p;
maxId = p->second.id;
}
}
if (p->first == score) {
if (p->second.id > maxId) {
maxp = p;
maxId = p->second.id;
}
}
cout << maxp->second.name << ” ” << maxp->second.id << ” ” << maxp->first << endl;
}
else
cout << “Nobody” << endl;
}
}
system(“pause”);
return 0;
}
2.map
template<class Key, class T, class Pred = less<Key>,
class A = allocator<T> >
class map {
typedef pair<const Key, T> value_type;
};
map中的元素都是pair模板类对象。关键字（first成员变量）各不相同。元素按照关键字从小到大排列，缺省情况下用less<Key>，即“<”定义“小于”。
3.map的[]成员函数
若pairs为map模版类的对象，
pairs[key]
返回对关键字等于key的元素的值(second成员变量）的引用。若没有关键字为key的元素，则会往pairs里插入一个关键字为key的元素，其值用无参构造函数初始化，并返回其值的引用。
如：
map<int, double> pairs;
则
pairs[50]=5;会修改paris中关键字为50的元素，使其值变为5。若不存在关键字等于50的元素，则插入此元素，并使其值变为5。
