STL之红黑树容器:set,hash_set,multiset,hash_map,multimap

  1. 云栖社区>
  2. 博客>
  3. 正文

STL之红黑树容器:set,hash_set,multiset,hash_map,multimap

涂作权 2014-08-30 22:58:00 浏览831
展开阅读全文


1红黑树set(不能包含重复元素)

案例1:红黑树容器set,插入,查找

#include<iostream>

#include<set>

usingnamespacestd;

 

//set中不能有重复的元素,它是一个红黑树容器

voidmain()

{

   set<int>myset;

   myset.insert(10);

   myset.insert(9);

   myset.insert(8);

   myset.insert(7);

   myset.insert(5);

   myset.insert(5);

   myset.insert(6);

   myset.insert(7);

   //myset.insert(7);重复会被舍弃

   autofindpos =myset.find(10);

   cout <<" find -> " << *findpos << " \n";

 

   autoib =myset.begin();

   autoie =myset.end();

   for (;ib !=ie;ib++)

   {

       cout << *ib << "  ";

   }

   cout <<"\n" <<myset.size() << endl;

   cin.get();

}

 

案例2

#include<iostream>

#include<set>

 

usingnamespacestd;

 

structstrless

{

   //二分查找法依赖于有序,字符串有序

   bool operator()(constchar *str1,constchar *str2)//二分查找法依赖于有序,字符串有序

   {

       returnstrcmp(str1,str2) < 0;

   }

};

 

//红黑树,处理纯数字非常少,经常处理类对象以及字符串

voidmain()

{

   constchar *cmd[] = { "abc","calc","notepad","const","xyz","ghj" };

   //strless():表示比大小的

   //set是一个红黑树,不可以用下标的方式

   set<constchar*,strless>myset(cmd,cmd + 6,strless());

   myset.insert("1234");

   myset.insert("4567");

 

   //pair起到获取插入返回值,第一个类型,类型比大小的方式

   //pair相当于是一对的意思,同时可以装两个东西

   pair<set<constchar *>::iterator,bool>p =myset.insert("9876");

   cout <<"pair start" <<endl;

   cout << *(p.first) << " " <<p.second << endl;

   cout <<"pair over" <<endl;

   cout <<"----正向迭代---" << endl;

 

   autoib =myset.begin();

   autoie =myset.end();

   for (;ib !=ie;ib++)

   {

       cout << *ib << endl;

   }

   

   cout <<"----反向迭代---" << endl;

 

   autorb =myset.rbegin();

   autore =myset.rend();

   for (;rb !=re;rb++)

   {

       cout << *rb << endl;

   }

   //查找

   set<constchar *,strless>::iteratorpfind =myset.find("xyz");

   std::cout << "\n\n\n" << *pfind << endl;

 

   cin.get();

}

运行结果:

2. hash_set

案例1

#include<hash_set>

#include<iostream>

#include<algorithm>

#include<string>

 

usingnamespacestd;

 

voidmain()

{

   hash_set<constchar *>hs;//C++11自带子字符串的哈希

 

   hs.insert("chian");

   hs.insert("chi123an");

   hs.insert("chi23an");

   hs.insert("chzcian");

   hs.insert("1chzcian");

 

   //这里得到的是一个指针

   autopfind =hs.find("chi23an");

 

   if (pfind == hs.end())

   {

       std::cout << "没有";

   }

   else

   {

       std::cout << *pfind;

   }

   cin.get();

   //运行结果:chi23an

}

案例2

#include<hash_set>

#include<iostream>

#include<algorithm>

#include<string>

 

usingnamespacestd;

 

voidmain()

{

   hash_set<int>hs;

   hs.insert(91);

   hs.insert(21);

   hs.insert(41);

 

   autoib =hs.begin();

   autoie =hs.end();

   for (;ib !=ie;ib++)

   {

       cout << *ib << endl;

   }

   //查找211

   autopfind =hs.find(211);

   if (pfind == ie)

   {

       std::cout << "没有";

   }

   else

   {

       std::cout << *pfind;

   }

   cin.get();

}

3.multiset(每个元素的节点是一个链表)

案例1:multisetset的区别是:multiset允许重复

#include<iostream>

#include<set>

#include<stdio.h>

#include<list>

#include<vector>

#include<algorithm>

#include<functional>

 

usingnamespacestd;

//multisetset的区别是允许重复

voidmain()

{

   multiset<int>myset; //头文件set

   myset.insert(11);

   myset.insert(12);

   myset.insert(13);

   myset.insert(10);

   myset.insert(10);

   myset.insert(100);

   autoib =myset.begin();

   autoie =myset.end();

 

   for (;ib !=ie;ib++)

   {

       std::cout << *ib <<std::endl;

       printf("%p,%p\n",ib,ib._Ptr);//ib本质是智能指针

       //建议使用下面的方式打印出外部指针和内部指针

       printf("%p\n",ib);//ib本质是智能指针

       //打印内部指针

       printf("%p\n",ib._Ptr);//ib本质是智能指针

   }

   cin.get();

}

运行结果是:

案例2

#define_CRT_SECURE_NO_WARNINGS

#include<set>

#include<iostream>

#include<string>

 

//multiset每一个节点都是一个链表,set每个节点就是一个节点

usingnamespacestd;

 

structstudent

{

   intid;

   charname[30];

};

 

//排序

structstuless

{

   bool operator()(conststudent &s1,conststudent &s2)

   {

       returns1.id < s2.id;

   }

};

 

voidmain()

{

   studentsarray[3] = { { 10,"tansheng" }, { 3,"liguilong" }, { 4,"xiongfei" } };

   multiset<student,stuless>myset(sarray,sarray + 3,stuless());

   studentstu1;

   stu1.id = 20;

   strcpy(stu1.name,"mouzhiwei");

   myset.insert(stu1);

   strcpy(stu1.name,"mouzhiwei1");

   myset.insert(stu1);

   strcpy(stu1.name,"mouzhiwei2");

   myset.insert(stu1);

   autoib =myset.begin();

   autoie =myset.end();

   for (;ib !=ie;ib++)

   {

       cout << (*ib).id << " " << (*ib).name << endl;

   }

 

   cin.get();

}

4.hash_map

案例:

#include<hash_map>//也是红黑树,是一个映射

 

#include<iostream>

#include<map>

 

usingnamespacestd;

 

voidmain()

{

   map<int,constchar *>m;

   m.insert(pair<int,constchar *>(201,"司令1"));

   m.insert(pair<int,constchar *>(101,""));

   m.insert(pair<int,constchar *>(401,"司令11111"));

   m.insert(pair<int,constchar *>(301,"司令"));

 

   autoib =m.begin();

   autoie =m.end();

   for (;ib !=ie;ib++)

   {

       cout << (*ib).first << "  " << (*ib).second << "\n";

   }

   std::cout << "------------" <<std::endl;

   {

       hash_map<int,constchar *>m;

       m.insert(pair<int,constchar *>(201,"司令1"));

       m.insert(pair<int,constchar *>(101,""));

       m.insert(pair<int,constchar *>(401,"司令11111"));

       m.insert(pair<int,constchar *>(301,"司令"));

 

       std::cout << "---正向迭代---" << std::endl;

       autoib =m.begin();

       autoie =m.end();

       for (;ib !=ie;ib++)

       {

           cout << (*ib).first << "  " << (*ib).second << "\n";

       }

       autotofind =m.find(1101);

       if (tofind == ie)

       {

           cout <<"没有找到";

       }

       else

       {

           cout <<"\n\n\n" << (*tofind).first << " " << (*tofind).second;

       }

   }

 

   cin.get();

}

运行结果:

5. multimap每一个一个节点是映射的链表的开头

案例1

#include<iostream>

#include<map>

 

usingnamespacestd;

//map,mutlimap区别是map每一个节点是一个映射

//multimap每一个一个节点是映射的链表的开头

voidmain()

{

   map<constchar*,int>m;

   m.insert(pair<constchar *,int>("司令1", 101));

   m.insert(pair<constchar *,int>("司令2", 102));

   m.insert(pair<constchar *,int>("司令3", 103));

   m.insert(pair<constchar *,int>("司令1", 104));

 

   map<constchar *,int>::iteratorib =m.begin();

   autoie =m.end();

   for (;ib !=ie;ib++)

   {

       cout << (*ib).first << "  " << (*ib).second << "\n";

   }

 

   cin.get();

}

运行结果:

 

 

 

网友评论

登录后评论
0/500
评论
涂作权
+ 关注