首页 > 代码库 > set和map和pair 转自ACdreamers

set和map和pair 转自ACdreamers

    

        set与map容器             

        分类:             C/C++             

首先来看看set集合容器:

 

set集合容器实现了红黑树的平衡二叉树数据结构,在插入元素时它会自动调整二叉树的排列,把该元素放到适当的位置,并且保证左右子树平衡。平衡二叉检索树采用中序遍历算法。

 

对于set,vector,map等等,它们的前向迭代器定义是这样的(以set为例):

 

set<int>::iterator it;

for(it=s.begin();it!=s.end();it++){}

 

那么反向迭代器呢?

 

set<int>::reverse_iterator rit;

for(rit=s.rbegin();rit!=s.rend();rit++){}

 

常用方法:insert(),erase(),find(),clear()

find()方法是查找元素方法,如果找到就返回该元素迭代器的位置,否则就返回最后一个元素后面的一个位置。

 

这样来使用:

it=s.find(5);

if(it!=s.end()) {}

else            {}

 

 

关于比较函数:

 

如果元素不是结构体,而是基本数据类型,那么就自己定义一个比较函数:

[cpp] view plaincopyprint?在CODE上查看代码片派生到我的代码片
  1. struct cmp  
  2. {  
  3.     bool operator()(const int &a,const int &b)  
  4.     {  
  5.         return a>b;  
  6.     }  
  7. };  
  8.   
  9. int main()  
  10. {  
  11.     set<int,cmp> s;  
  12.     for(int i=1;i<10;i++)  
  13.        s.insert(i);  
  14.     set<int,cmp>::iterator it;  
  15.     for(it=s.begin();it!=s.end();it++)  
  16.         cout<<*it<<" ";  
  17.     return 0;  
  18. }  
struct cmp{    bool operator()(const int &a,const int &b)    {        return a>b;    }};int main(){    set<int,cmp> s;    for(int i=1;i<10;i++)       s.insert(i);    set<int,cmp>::iterator it;    for(it=s.begin();it!=s.end();it++)        cout<<*it<<" ";    return 0;}

如果元素是结构体,那么比较函数直接可以写在结构体里面。

[cpp] view plaincopyprint?在CODE上查看代码片派生到我的代码片
  1. struct Student  
  2. {  
  3.     string name;  
  4.     double score;  
  5.     bool operator < (const Student &a) const  
  6.     {  
  7.         return a.score<score;  
  8.     }  
  9. };  
  10.   
  11. set<Student> s;  
struct Student{    string name;    double score;    bool operator < (const Student &a) const    {        return a.score<score;    }};set<Student> s;

对于set容器来说,它不能有关键字相同的元素同时存在,如果要保留相同的元素,就用multiset多重集合容器。

其基本操作跟set集合容器差不多一样。定义方法是:multiset<string> ms;

 

 

map映照容器:

 

map映照容器的元素数据是由一个键值和一个映照数据组成的,键值与映照数据之间具有一一对应关系。map也是用红黑树实现

的。同set一样,map不允许插入元素键值相同,而multimap多重应照集合可以允许键值重复。

 

使用方法:

[cpp] view plaincopyprint?在CODE上查看代码片派生到我的代码片
  1. int main()  
  2. {  
  3.     map<string,double> m;  
  4.     m["Jack"]=98.0;  
  5.     map<string,double>::iterator it;  
  6.     for(it=m.begin();it!=m.end();it++)  
  7.         cout<<(*it).first<<" "<<(*it).second<<endl;  
  8.     return 0;  
  9. }  
int main(){    map<string,double> m;    m["Jack"]=98.0;    map<string,double>::iterator it;    for(it=m.begin();it!=m.end();it++)        cout<<(*it).first<<" "<<(*it).second<<endl;    return 0;}

主要方法有:insert(),clear(),erase(),find()等等,基本跟set一样。对于multimap使用方法跟map差不多一样。

 

std::pair主要的作用是将两个数据组合成一个数据,两个数据可以是同一类型或者不同类型。

例如 std::pair<int,float> 或者 std::pair<double,double>等。pair实质上是一个结构体,其主要的两个成员变量是first和second,这两个变量可以直接使用。初始化一个pair可以使用构造函数,也可以使用std::make_pair函数。

make_pair函数的定义如下:

[cpp] view plaincopyprint?在CODE上查看代码片派生到我的代码片
  1. template pair make_pair(T1 a, T2 b)   
  2. {   
  3.     return pair(a, b);   
  4. }  
template pair make_pair(T1 a, T2 b) {     return pair(a, b); }

所以m.insert(pair<string,double>("Luce",88.5));

与 m.insert(make_pair("Luce",88.5)); 是同样的效果。

 

示例:

[cpp] view plaincopyprint?在CODE上查看代码片派生到我的代码片
  1. int main()  
  2. {  
  3.     typedef pair<string,double> lesson;  
  4.     typedef multimap<string,lesson> stu;  
  5.     stu a;  
  6.     a.insert(make_pair("Jack",lesson("math",90.5)));  
  7.     a.insert(make_pair("Jack",lesson("history",85.5)));  
  8.     a.insert(make_pair("Luce",lesson("math",99.0)));  
  9.     map<string,lesson>::iterator it;  
  10.     for(it=a.begin();it!=a.end();it++)  
  11.         cout<<(*it).first<<" "<<(*it).second.first<<" "<<(*it).second.second<<endl;  
  12.     return 0;  
  13. }