050-C++之STL-->set、multiset

moc

1、set、multiset简介
1. set是一个集合容器，其中包含的元素是唯一的，集合中旳元素按照一定的顺序排列。
2. set元素的插入过程是按排序规则进行插入（遇到已有元素会插入失败）,所以不能指定插入位置。
3. set采用红黑树变体的数据结构实现，红黑树属于平衡二叉树，在插入和删除操作上比vector快。
4. set容器不可以直接存取元素，即不可以使用at(pos)与[]操作。
5. multiset与set的区别： set中每个元素（按排序插入比较的值）只能出现一次，multiset则允许同一个值的多次出现。
6. 不可以直接修改set或multiset容器中的元素值，因为该容器是自动排序的，如果希望修改一个值，必须先删除原有元素，再插入新的元素。

set容器默认排序是由小到大的，即 set<int>  set1;   等价于  set<int, less<int>> set1;
由大到小设置为：set<int, greater<int>> set2;    // #include "functional"

2、set基本操作
insert(n)          插入元素n到集合
clear()   　　   删除set容器中的所有的元素
empty() 　　　判断set容器是否为空   
max_size() 　  返回set容器可能包含的元素最大个数
size() 　　　　返回当前set容器中的元素个数
begin()     　　返回set容器的第一个迭代器
end() 　　　　返回set容器的最后一个元素的后面迭代器
rbegin()　　　　返回的值和end()相同
rend()　　　　返回的值和begin()相同

1. int main()
   
2. {
   
3.         set<int> s;
   
4.         s.insert(1);
   
5.         s.insert(2);
   
6.         s.insert(3);
   
7.         s.insert(1);
   
8.         cout << "set 的 size 值为 ：" << s.size() << endl;
   
9.         cout << "set 的 maxsize的值为 ：" << s.max_size() << endl;
   
10.         cout << "set 中的第一个元素是 ：" << *s.begin() << endl;
    
11.         cout << "set 中的最后一个元素是:" << *(--s.end()) << endl;
    
12.         s.clear();
    
13.         if (s.empty())
    
14.         {
    
15.                 cout << "set 为空 ！！！" << endl;
    
16.         }
    
17.         cout << "set 的 size 值为 ：" << s.size() << endl;
    
18.         cout << "set 的 maxsize的值为 ：" << s.max_size() << endl;
    
19.         return 0;
    
20. }

复制代码

count()         用来查找set中某个某个键值出现的次数
erase(iterator)          删除定位器iterator指向的值
erase(first,second)    删除定位器first和second之间的值
erase(key_value)      删除键值key_value的值

lower_bound(key_value)    返回第一个大于等于key_value的定位器
upper_bound(key_value)   返回最后一个大于等于key_value的定位器
find()    返回给定值值的定位器，如果没找到则返回end()

注意：set中的删除，插入等操作是不进行任何的错误检查的，比如定位器的是否合法等等，所以用的时候自己一定要注意。

3、set容器-复杂类型自定义排序规则
仿函数：重载了operator()运算符的类。
insert(key_value);   ==>   将key_value插入到set中，返回值是pair<set<int>::iterator,bool>，bool标志着插入是否成功，而iterator代表插入的位置，若key_value已经在set中，则iterator表示的key_value在set中的位置。
其中的pair即为一个对组类型。
对组：  两个值封装在一起的一个单元。
pair<T1, T2>  存放两个值的类型，这两个值的类型可以不一样。
        pair.first      是pair类型里的第一个值，类型为T1;
        pair.second  是pair类型里的第二个值，类型为T2.

1. class Student
   
2. {
   
3. public:
   
4.         Student(char * _name, int _age)
   
5.         {
   
6.                 strcpy_s(name, _name);
   
7.                 age = _age;
   
8.         }
   
9. 
   
10. public:
    
11.         char name[28];
    
12.         int age;
    
13. };
    
14. 
    
15. // 仿函数  (类关键字 class、struct、union)
    
16. struct FunStudent
    
17. {
    
18.         bool operator()(const Student &left, const Student &right)
    
19.         {
    
20.                 if (left.age < right.age)   // 按照年龄从小到大排列
    
21.                 {
    
22.                         return true;
    
23.                 }
    
24.                 else
    
25.                 {
    
26.                         return false;
    
27.                 }
    
28.         }
    
29. };
    
30. 
    
31. 
    
32. int main()
    
33. {
    
34.         set<Student, FunStudent> set1;
    
35. 
    
36.         Student s1("s1", 16);
    
37.         Student s2("s1", 15);
    
38.         Student s3("s1", 19);
    
39.         Student s4("s1", 17);
    
40.         Student s5("s8", 15);
    
41. 
    
42.         set1.insert(s1);
    
43.         set1.insert(s2);
    
44.         set1.insert(s3);
    
45.         set1.insert(s4);
    
46. 
    
47.         // 该函数的返回值是一个对组pair,学会追踪类型    返回结果是一个对组pair
    
48.         pair<set<Student, FunStudent>::iterator, bool> pair1 = set1.insert(s5);
    
49.         if (pair1.second == true)
    
50.         {
    
51.                 cout << "插入元素成功\n";
    
52.         }
    
53.         else
    
54.         {
    
55.                 cout << "插入元素失败\n";
    
56.         }
    
57. 
    
58.         for (auto each : set1)
    
59.         {
    
60.                 cout << each.name << each.age << " ";
    
61.         }
    
62. 
    
63.         system("pause");
    
64.         return 0;
    
65. }

复制代码

LAST：multiset容器的操作和set容器是一致的。

Fivk

1. #include<iostream>
   
2. #include<cstdio>
   
3. #include<algorithm>
   
4. using namespace std;
   
5. 
   
6. int Fivk(int *,int );
   
7. double fivk(int *,int *);
   
8. int b[2001][3]={{0}};
   
9. int main(void)
   
10. {
    
11.         int n,i,j,m,k,t;
    
12.         set<int> a[10000];
    
13.         scanf("%d",&n);
    
14.         for(i=1;i<=n;i++)
    
15.         {
    
16.                 scanf("%d",&m);
    
17.                 for(j=1;j<=m;j++)
    
18.                 {
    
19.                         scanf("%d",&t);
    
20.                         a[i].insart(t);
    
21.                 }
    
22.                 b[i][0]=a[i].size();
    
23.         }
    
24.        
    
25.         scanf("%d",&k);
    
26.        
    
27.         for(i=1;i<=k;i++)
    
28.         {
    
29.                 scanf("%d %d",&b[i][1],&b[i][2]);
    
30.         }
    
31.        
    
32.         for(i=1;i<=k;i++)
    
33.         {
    
34.                 m=b[i][1];
    
35.                 n=b[i][2];
    
36.                 printf("%.2lf%%",100*fivk(a[m].begin,a[n].begin));
    
37.                 if(i<k) printf("\n");
    
38.         }
    
39.         return 0;
    
40. }
    
41. 
    
42. double fivk(int *a1,int *a2)
    
43. {
    
44.         int i,j;
    
45.         double count=0;
    
46.        
    
47.         /*for(i=1;i<=a1[0];i++)
    
48.         {
    
49.                 for(j=1;j<=a2[0];j++)
    
50.                 {
    
51.                         if(a1[i]==a2[j])
    
52.                         {
    
53.                                 count++;
    
54.                                 break;
    
55.                         }
    
56.                 }
    
57.         }*/
    
58.          
    
59.         return (double)(count/(a1[0]+a2[0]-count));
    
60. }

复制代码