集合（set和multiset）

set/multiset 的简介      set 是一个 集合 容器，其中所包含的元素是 唯一 的， 集合中的元素按一定的顺序排列 。元素插入过程是按排序规则插入， 所以不能指定插入位置。      set 采用红黑树变体的数据结构实现， 红黑树属于平衡二叉树。 在插入操作和删除操作上比 vector 快。      set 不可以直接存取元素。（不可以使用 at.(pos) 与 [] 操作符）。      multiset 与 set 的区别： set 支持唯一键值， 每个元素值只能出现一次； 而 multiset 中 同一值可以出现多次 。      不可以直接修改 set 或 multiset 容器中的元素值， 因为该类容器是自动排序的。 如果希望修改一个元素值， 必须先删除原有的元素， 再插入新的元素。

     #include <set>

#include"set" #include"iostream" #include"algorithm" #include"functional" using namespace std; void print(set<int>se_1) { for (set<int>::iterator it = se_1.begin(); it != se_1.end(); it++) { cout << *it << " "; } cout << endl; } void printG(set<int,greater<int>>se_1) { for (set<int，greater<int> >::iterator it = se_1.begin(); it != se_1.end(); it++) { cout << *it << " "; } cout << endl; } void printM(multiset<int>se_1) { for (set<int>::iterator it = se_1.begin(); it != se_1.end(); it++) { cout << *it << " "; } cout << endl; } /*初始化*/ int main01() { set<int> se_1; multiset<int>se_2;//尖括号内可以是基本类型和自定义类型 int a[] = { 14, 12, 12, 12, 12, 43, 34, 25, 26, 67, 18, 39 }; for(int i = 0; i < 12; i++) { se_1.insert(a[i]);//12，14，18，25，26，34，39，43，67 se_2.insert(a[i]);//12，12, 12, 12, 14，18，25，26，34，39，43，67 // multiset允许有重复值 } cout << "通过insert函数方式初始化："; print(se_1); printM(se_2); set<int> se_3 = se_1; cout << "通过复制构造函数方式初始化："; print(se_3); set<int>se_4(a,a+sizeof(a)/sizeof(int)); cout << "通过构造函数方式初始化："; print(se_4); return 0; } /*插入与删除*/ /* set 的插入与迭代器  set.insert(elem); //在容器中插入元素。  set.begin(); //返回容器中第一个数据的迭代器。  set.end(); //返回容器中最后一个数据之后的迭代器。  set.rbegin(); //返回容器中倒数第一个元素的迭代器。  set.rend(); //返回容器中倒数最后一个元素的后面的迭代器。 */ /* set 的删除  set.clear(); //清除所有元素  set.erase(pos); //删除 pos 迭代器所指的元素， 返回下一个元素的迭代器。  set.erase(beg,end); //删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。  set.erase(elem); //删除容器中值为 elem 的元素。 */ int main02() { int a[] = {11,12,13,14,15}; int b[] = {10,20}; set<int>se_1(a, a + 5); set<int>se_2(b,b+2); ///元素插入 se_1.insert(35); se_1.insert(25); se_1.insert(48); cout << "插入： "; print(se_1);//11,12,13,14,15,25,35,48 se_1.insert(se_2.begin(),se_2.end());//10,11,12,13,14,15,20,25,35,48 print(se_1); cout << "大小： " << se_1.size()<<endl; //元素删除/ se_1.erase(15);//10,11,12,13,14,20,25,35,48 set<int>::iterator it1 = se_1.begin(); se_1.erase(it1);//11,12,13,14,20,25,35,48 set<int>::iterator it2 = se_1.begin(); set<int>::iterator it3 = se_1.begin(); it3++; it3++; se_1.erase(it2,it3);//13,14,20,25,35,48 cout << "删除： "; print(se_1); return 0; } /* Set 集合的元素排序  set<int,less<int> > setIntA; //该容器是按升序方式排列元素。  set<int,greater<int>> setIntB; //该容器是按降序方式排列元素。  set<int> 相当于 set<int,less<int>>。  less<int>与 greater<int>中的 int 可以改成其它类型， 该类型主要要跟 set 容纳的数据 类型一致。  疑问 1： less<>与 greater<>是什么？  疑问 2： 如果 set<>不包含 int 类型， 而是包含自定义类型， set 容器如何排序？  要解决如上两个问题， 需要了解容器的函数对象， 也叫伪函数， 英文名叫 functor。 struct greater { bool operator() (const int& iLeft, const int& iRight) { return (iLeft>iRight); //如果是实现 less<int>的话， 这边是写 return (iLeft<iRight); } } 容器就是调用函数对象的 operator()方法去比较两个值的大小。 */ class Student { public: Student(int id, string name) { this->id = id; this->name = name; } string printname() { return name; } friend ostream& operator<<(ostream&out, Student &t); public: int id; string name; }; ostream& operator<<(ostream&out, const Student &t) { out << t.id<<"," ; for (int i = 0; i < t.name.length(); i++) { out << t.name[i]; } return out; } struct stuFunctor //函数对象 { bool operator()(const Student &s1, const Student &s2) { return (s1.id>s2.id); } }; int main03() { int a[] = { 14, 12, 12, 12, 12, 43, 34, 25, 26, 67, 18, 39 }; set<int, less<int> >se_1(a, a + sizeof(a) / sizeof(int)); set<int, greater<int> >se_2(a, a + sizeof(a) / sizeof(int)); cout << "最大值优先排序"; print(se_1);//12，14，18，25，26，34，39，43，67 cout << "最小值优先排序"; printG(se_2);//67, 43, 39, 34, 26, 25, 18, 14, 12 set<Student, stuFunctor>stu1; stu1.insert (Student(100,"zhao")); stu1.insert(Student(101,"qian")); stu1.insert(Student(102,"sun ")); stu1.insert(Student(103,"li ")); for ( set<Student>::iterator it=stu1.begin(); it!=stu1.end(); it++) { //重载<< cout << *it << "\t ";//103,li 102,sun 101,qian 100,zhao } cout << endl; return 0; } /* set 的查找  set.find(elem); //查找 elem 元素， 返回指向 elem 元素的迭代器。  set.count(elem); //返回容器中值为 elem 的元素个数。 对 set 来说， 要么是 0， 要 么是 1。 对 multiset 来说， 值可能大于 1。  set.lower_bound(elem); //返回第一个>=elem 元素的迭代器。  set.upper_bound(elem); // 返回第一个>elem 元素的迭代器。  */ int main04() { int a[] = { 14, 12, 12, 12, 12, 43, 34, 25, 26, 67, 18, 39 }; set<int>se_1(a,a+sizeof(a)/sizeof(int)); set<int>::iterator it1= se_1.find(25); cout << "返回迭代器指针所指向的数据： "<<*it1 << endl; cout << "返回set容器中12的个数： " << se_1.count(12) << endl; //对 set 来说， 要么是 0， 要么是 1。 对 multiset 来说， 值可能大于 1。 set<int>::iterator it2 = se_1.lower_bound(25); cout << "输出所有大于等于25的数: "; for (; it2!=se_1.end(); it2++) //25,26,34,39,43,67,输出所有大于等于25的数 { cout << *it2 << " "; } cout << endl; set<int>::iterator it3 = se_1.upper_bound(25); cout << "输出所有大于25的数: "; for (; it3 != se_1.end(); it3++) //26,34,39,43,67,输出所有大于等于25的数 { cout << *it3 << " "; } cout << endl; return 0; } /* set.equal_range(elem); //返回容器中与 elem 相等的上下限（首次相等和最后一次相等）的两个迭代器。 上限是闭区间， 下限是开区间， 如[beg,end)。  以上函数返回两个迭代器， 而这两个迭代器被封装在 pair 中。  以下讲解 pair 的含义与使用方法。 */ /* pair< set<int>::iterator, set<int>::iterator > pairIt = setInt.equal_range(5); pair 的使用  pair 译为对组， 可以将两个值视为一个单元。  pair<T1,T2>存放的两个值的类型， 可以不一样，如 T1 为 int， T2 为 float。 T1,T2 也可 以是自定义类型。  pair.first 是 pair 里面的第一个值， 是 T1 类型。  pair.second 是 pair 里面的第二个值，是 T2 类型。 */ int main05() { int a[] = { 14, 12, 12, 25, 12, 12, 25, 43, 34, 25, 26, 67, 25, 18, 39 }; multiset<int>se_1(a, a + sizeof(a) / sizeof(int)); pair<multiset<int>::iterator, multiset<int>::iterator> it1 = se_1.equal_range(25);//返回集合中等于25的迭代器指针 multiset<int>::iterator te; for (te=it1.first; te!= it1.second; te++) { cout << *te << " "; } cout << endl; return 0; } int main() { //main01();//初始化 //main02();//元素插入与删除 //main03();//排序 //main04();//查找 main05();//pair(set.equal_range(elem);) system("pause"); return 0; }

//案例1

//假设公司雇员属性有姓名、部门名称。管理雇员类仅包含（1）添加雇员功能，（2）显示功能， //要求部门名称升序排列，若部门名称相同，则按升序排列 //雇员（基础类）/管理雇员类 #include"iostream" using namespace std; #include"string" #include"set" //雇员类 class Employee { public: string name; string department; public: Employee(string nam, string dep) { name = nam; department = dep; } hanshu duixiang bool operator<(const Employee &e)const { bool mark = (department.compare(e.department) > 0) ? true : false; if (department.compare(e.department) == 0) { mark = (name.compare(e.name) > 0) ? true : false; } return mark; } }; //guyuanguanli class EManager { public: multiset<Employee> se_1; public: bool add(Employee&e) { se_1.insert(e); return true; } void show() { multiset<Employee>::iterator it = se_1.begin(); for (; it != se_1.end(); it++) { cout << it->name <<" "<< it->department << endl; } } }; int main() { Employee e1("zhangsan", "装备部"); Employee e2("lisi", "制造部"); Employee e3("wangwu", "制造部"); Employee e4("zhaoliu", "人力部"); EManager em1; em1.add(e1); em1.add(e2); em1.add(e3); em1.add(e4); em1.show(); system("pause"); return 0; }