首页 > 代码库 > set和map和pair 转自ACdreamers
set和map和pair 转自ACdreamers
set与map容器
首先来看看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 {}
关于比较函数:
如果元素不是结构体,而是基本数据类型,那么就自己定义一个比较函数:
- 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;
- }
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;}
如果元素是结构体,那么比较函数直接可以写在结构体里面。
- struct Student
- {
- string name;
- double score;
- bool operator < (const Student &a) const
- {
- return a.score<score;
- }
- };
- 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多重应照集合可以允许键值重复。
使用方法:
- 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;
- }
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函数的定义如下:
- template pair make_pair(T1 a, T2 b)
- {
- return pair(a, b);
- }
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)); 是同样的效果。
示例:
- int main()
- {
- typedef pair<string,double> lesson;
- typedef multimap<string,lesson> stu;
- stu a;
- a.insert(make_pair("Jack",lesson("math",90.5)));
- a.insert(make_pair("Jack",lesson("history",85.5)));
- a.insert(make_pair("Luce",lesson("math",99.0)));
- map<string,lesson>::iterator it;
- for(it=a.begin();it!=a.end();it++)
- cout<<(*it).first<<" "<<(*it).second.first<<" "<<(*it).second.second<<endl;
- return 0;
- }