本文共 5209 字，大约阅读时间需要 17 分钟。

都是之前的博客了，发现草稿箱里面还有很多……

Set的说明

图示

Set 集合类似于一个罐子，把一个对象添加到Set集合时，Set集合无法记住添加这个元素的顺序，所以Set里的元素不能重复（否则系统无法准确识别这个元素）

List集合非常像一个数组，它可以记住每次添加元素的顺序，只是List长度可变。

Map集合也像一个罐子，只是它里面的每项数据都由两个值组成。

 

头文件

#include      <set>

定义

set<string>   my_set; //string是关键字，类似map中的第一个，也可是char等数据类型

迭代器

set<string>::iterator set_it;//从声明可以看出指向关键字

 set_it=my_set.begin();//指向首

Set的用法

创建set对象

为了管理set的二叉树链表数据，先用的构造函数，创建一个set对象(1) set() 用默认的less<T>和内存分配器，创建一个没有任何数据元素的set对象。 set<int> s;  //创建了空的set对象s，元素类型为整型int;(2) set(const key_compare& comp) 指定一个比较 comp 来创建set对象，内存分配器为默认值。 //定义字符串比较 strLess struct strLess {     bool operatro() (const char *s1, const char *s2) const     {          return strcmp(s1,  s2)  < 0;      } }; //创建对象s set<const char*, strLess> s(strLess());(3)set(const set&) set，通过红黑树的，实现两个的元素、头结点和节点个数的拷贝。 //set<int> s1; set<int> s2 (s1);(4)set(InputIterator first, InputIterator last) 用区间迭代器[first, last)所指的元素，创建一个set对象。 int iArray = { 13, 32,19 }; set<int> s(iArray, iArray+3);(5)set(InputIterator first, InputIterator last, const key_compare& comp) 用区间迭代器[first, last)所指的元素和comp函数对象，创建一个set对象。 const char* szArray = {"hello", "dog", "bird" }; set<const char* , strLess> s(szArray, szArray+3, strLess() );

元素的插入

set没有尾部插入函数()，元素的插入一般使用insert进行动态检索插入。

注：

       (1)   //不可用下标方法插入遍历

       (2)   my_set.insert({‘a’}); //insert返回一个pair类型，第一个是一个迭代器指向元素，第二个是一个bool值，插入成功返回true，已经存在返回false       (3)   vector<int> vec={2,4,6,8,10};my_set.insert(vec.begin(),vec.end());        (4)   my_set.insert({1,2,3,4,5,6,7}); 

(1)pair<iterator, bool> insert(const value_type& v) 将元素v插入set容器，要求v值不与set容器的任何元素重复，否则插入失败。返回一个pair配对对象，提供所插入元素的迭代器位置和true/false插入成功标志。

(2)iterator insert(iterator position, const value_type& v) 将元素v插入set容器，参数position提示可在position位置之前插入v，所返回的插入位置视实际情况而定，不一定能在position位置之前插入。(3)void insert(inputIterator fist, InputIterator last) 将某迭代器区间[first, last)所指的数据作为元素，插入到set容器。

元素的删除

与插入一样，set容器也具有高效的红黑树元素的删除处理， 并自动重新调整内部的红黑树平衡。

(1)   my_set.erase(my_Itr); 

(2)   my_set.erase("c");

  还是注意，第一种情况在迭代期间是不能被删除的，道理和foreach时不能删除元素一样。

(1) void erase(iterator position) 删除position所指的元素

(2) erase(const key_type& k) 删除等于键值k的那个元素，对于set容器来说，此函数总是返回值1， 因为set容器不会出现重复的元素值（键值）。

(3)void erase(iterator first, iterator last) 删除set迭代器区间[first, last)上的所有元素。

(4)void clear() 删除所有元素，但不会删除内部红黑树的头节点。

元素的遍历访问

iterator begin();

iterator  end();

元素的反向遍历

利用set容器定义的方向迭代器reverse_iterator和const_reverse_iterator，可实现红黑树的逆，从而将元素从大到小遍历出来。 reverse_iterator rbegin(); reverse_iterator rend();

元素的搜索

set容器提供了一个应用红黑树进行搜索的函数find，返回的迭代器值为搜索到的元素位置，如果元素不存在，则返回end结束元素位置

set容器的迭代器提供了访问内部红黑树中元素的操作，通常先用begin和end函数找出遍历开始的首元素和结束元素，然后通过迭代器的“++”操作，有小到到大取出元素值。

set<char>::iterator   my_Itr=my_set.begin();           *my_Itr;//元素

 my_set.find('a');//返回迭代器，指向key=='a'的元素,若没有此元素返回my_set.end();

  my_set.count('a');//返回关键字等于'a'的数量，对已set不允许重复关键字，返回值永远是0或1

 不过注意，键本身是不能被修改的，除非删除。 

 迭代数据 

  for   (my_Itr=my_Map.begin();   my_Itr!=my_Map.end();   ++my_Itr)   {} 

 其它方法 

  my_set.size()               返回元素数目    my_set.empty()       判断是否为空    my_set.clear()           清空所有元素    可以直接进行赋值和比较：=,   >,   >=,   <,   <=,   !=   等等 

set使用练习：输出字符中不重复的字符

 

#include
   
    int main(){char c;set
    
      set_c;//创建setwhile(cin.get(c))set_c.insert(c);//插入，set不支持下标,insert返回pair,first指向元素，second是一个boll值，true表示插入成功，false表示已有元素set
     
      ::iterator iterator=set_c.begin();//创建迭代器指向首while(iterator!=set_c.end()){cout<<* iterator;//输出迭代器指向，只读，不可修改值iterator++;}}
     
    
   

我对set所存疑难点

• ——>
• ——>

相关例题

Ugly numbers

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... shows the first 11 ugly numbers. By convention, 1 is included. Write a program to find and print the 1500’th ugly number.

Input

There is no input to this program. Output Output should consist of a single line as shown below, with ‘’ replaced by the number computed. Sample

Output

The 1500'th ugly number is

prime factor质因数

分析

题意：输出第1500个丑数（丑数：仅由质因数2，3，5相乘得来）

#include
   
    #include
    
     #include
     
      using namespace std;int ugly[1510];int main(){		memset(ugly,0,sizeof(ugly));		int a,b,c;		a=b=c=1;		ugly[1]=1;		for(int i=2;i<=1500;i++)		{			ugly[i]=min(ugly[a]*2,min(ugly[b]*3,ugly[c]*5));			if(ugly[i]==ugly[a]*2)  a++;			if(ugly[i]==ugly[b]*3)  b++;			if(ugly[i]==ugly[c]*5)  c++;					}		printf("The 1500'th ugly number is:<%d>\n",ugly[1500]);	return 0;}
     
    
   

思路分析

定义一个集合，该集合中有元素1，如果x在集合中，并且y是x的下一个丑数，那么x*2，x*3，x*5也在集合中，其它数不再集合中，这三个数中必定是2x最小，因此首先放入数组中，而此时*2最小的应该是x的下一个丑数y*2，此时应该找出y*2，x*3，x*5中最小的数放入数组，以此类推，具体操作如下：

                                                                                                  代码分析

 

1.  1
2. *2
3. *3
4. *5

  选出乘积最小的，加入到结果集中，相应指针右移  

1.  1     2
2. *3   *2
3. *5

  选出乘积最小的，加入到结果集中，相应指针右移  

1.  1     2    3
2. *5   *2
3. *3

  选出乘积最小的，加入到结果集中，相应指针右移  

1. 1     2    3    4
2. *5   *3    *2

  选出乘积最小的，加入到结果集中，相应指针右移  

1. 1     2     3    4
2. *3   *2
3. *5

  以此类推，直到获得1500的结果集，实现代码如上

这样就避免了有重复数字的问题，但是如果依次来求每一个丑数，有重复数字怎么做呢？

我们用set来写一下这个代码

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;typedef long long LL;const int a[3]={2,3,5};int main() {	priority_queue
       
        
         ,greater
         
           > que;//从小到大 set
          
            s; que.push(1); s.insert(1); for(int i=1;;i++) { LL x=que.top(); que.pop(); if(i==1500) { printf("The 1500'th ugly number is %lld.\n",x); break; } for(int j=0;j<3;j++) { LL y=x*a[j]; if(!s.count(y)) { s.insert(y); que.push(y); } } } return 0;}
          
         
        
       
      
     
    
   

当然，只要能AC，管他三七二十一，某位陈独秀的代码也AC了

#include
   
    using namespace std;int main() {		printf("The 1500'th ugly number is 859963392");		return 0;}
   

强大的一批……

 

转载地址：https://blog.csdn.net/hou_shiyu/article/details/81220387 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！