第一节 关联容器

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++中,返回值不是这样)。

1multiset的用法

#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。