C++ STL set和multiset的使用 1,set的含义是集合,它是一个有序的容器,里面的元素都是排序好的,支持插入,删除,查找等操作,就 像一个集合一样。所有的操作的都是严格在logn时间之内完成,效率非常高。 set和multiset的区别是:set插入的元素不能相同,但是multiset可以相同。 创建 multiset<ss> base; 删除:如果删除元素a,那么在定义的比较关系下和a相等的所有元素都会被删除 base.count( a ):set能返回0或者1,multiset是有多少个返回多少个. Set和multiset都是引用<set>头文件,复杂度都是logn 2,Set中的元素可以是任意类型的,但是由于需要排序,所以元素必须有一个序,即大小的比较关系,比如 整数可以用<比较. 3,自定义比较函数; include<set> typedef struct { 定义类型 } ss(类型名); struct cmp { bool operator()( const int &a, const int &b ) const { 定义比较关系<} }; (运算符重载,重载<) set<ss> base; ( 创建一个元素类型是ss,名字是base的set ) 注:定义了<,==和>以及>=,<=就都确定了,STL的比较关系都是用<来确定的,所以必须通 过定义< --“严格弱小于”来确定比较关 4,set的基本操作: begin() 返回指向第一个元素的迭代器 clear() 清除所有元素 count() 返回某个值元素的个数 empty() 如果集合为空,返回true end() 返回指向最后一个元素的迭代器 equal_range() 返回集合中与给定值相等的上下限的两个迭代器 erase() 删除集合中的元素 find() 返回一个指向被查找到元素的迭代器 get_allocator() 返回集合的分配器 insert() 在集合中插入元素 lower_bound() 返回指向大于(或等于)某值的第一个元素的迭代器 key_comp() 返回一个用于元素间值比较的函数 max_size() 返回集合能容纳的元素的最大限值 rbegin() 返回指向集合中最后一个元素的反向迭代器 rend() 返回指向集合中第一个元素的反向迭代器 size() 集合中元素的数目 swap() 交换两个集合变量 upper_bound() 返回大于某个值元素的迭代器 value_comp() 返回一个用于比较元素间的值的函数 5,自定义比较函数: For example: #include<iostream> #include<set> using namespace std; typedef struct { int a,b; char s; }newtype; struct compare //there is no (). { bool operator()(const newtype &a, const newtype &b) const { return a.s<b.s; } };//the “; ” is here; set<newtype,compare>element; int main() { newtype a,b,c,d,t; a.a=1; a.s='b'; b.a=2; b.s='c'; c.a=4; c.s='d'; d.a=3; d.s='a'; element.insert(a); element.insert(b); element.insert(c); element.insert(d); set<newtype,compare>::iterator it; for(it=element.begin(); it!=element.end();it++) cout<<(*it).a<<" "; cout<<endl; for(it=element.begin(); it!=element.end();it++) cout<<(*it).s<<" "; } element自动排序是按照char s的大小排序的; 6.其他的set构造方法; #include <iostream> #include <set> using namespace std; bool fncomp (int lhs, int rhs) {return lhs<rhs;} struct classcomp { bool operator() (const int& lhs, const int& rhs) const {return lhs<rhs;} }; int main () { set<int> first; // empty set of ints int myints[]= {10,20,30,40,50}; set<int> second (myints,myints+5); // pointers used as iterators set<int> third (second); // a copy of second set<int> fourth (second.begin(), second.end()); // iterator ctor. set<int,classcomp> fifth; // class as Compare bool(*fn_pt)(int,int) = fncomp; set<int,bool(*)(int,int)> sixth (fn_pt); // function pointer as Compare return 0; }