C++ STL set和multiset的使用 hunst_xiehonghao 总结

C++ STL set和multiset的使用

1，set的含义是集合，它是一个有序的容器，里面的元素都是排序好的，支持插入，删除，查找等操作，就 像一个集合一样。所有的操作的都是严格在logn时间之内完成，效率非常高。 set和multiset的区别是：set插入的元素不能相同，但是multiset可以相同。

创建 multiset<ss> base;

删除：如果删除元素a,那么在定义的比较关系下和a相等的所有元素都会被删除

base.count( a )：set能返回０或者１，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() 返回一个用于比较元素间的值的函数

1：

set元素的插入：

#include <iostream>#include <string>#include <set>using namespace std;void printSet(set<int> s){ set<int>::iterator i; for(i=s.begin();i!=s.end();i++)        printf("%d ",*i); cout<<endl;}void main(){ //创建空的set对象，元素类型为int， set<int> s1; for (int i = 0; i <5 ; i++)  s1.insert(i*10); printSet(s1); cout<<"s1.insert(20).second = "<<endl;; if (s1.insert(20).second)//再次插入20     cout<<"Insert OK!"<<endl; else  cout<<"Insert Failed!"<<endl; cout<<"s1.insert(50).second = "<<endl; if (s1.insert(50).second) {cout<<"Insert OK!"<<endl; printSet(s1);} else  cout<<"Insert Failed!"<<endl; pair<set<int>::iterator, bool> p;  p = s1.insert(60); if (p.second) {cout<<"Insert OK!"<<endl; printSet(s1);} else  cout<<"Insert Failed!"<<endl;}继续更新中

2: set 的 empty erase 删除特定元素

#include <iostream>#include <set>using namespace std;int main (){  set<int> myset;  myset.insert(20);  myset.insert(30);  myset.insert(10);  while (!myset.empty())  {     cout <<" "<< *myset.begin();     myset.erase(myset.begin());  }  cout << endl;  return 0;}

//set::find  #include <iostream>#include <set>using namespace std;int main (){  set<int> myset;  set<int>::iterator it;  for (int i=1; i<=5; i++) myset.insert(i*10);    // set: 10 20 30 40 50  it=myset.find(20);  myset.erase (it);  myset.erase (myset.find(40));  myset.erase (30);  cout << "myset contains:";  for (it=myset.begin(); it!=myset.end(); it++)    cout << " " << *it;  cout << endl;  return 0;}

lower_bound()返回一个 iterator 它指向在[first,last)标记的有序序列中可以插入value，而不会破坏容器顺序的第一个位置，而这个位置标记了一个大于等于value 的值。　　例如，有如下序列：　　ia[]={12,15,17,19,20,22,23,26,29,35,40,51};　　用值21调用lower_bound(),返回一个指向22的iterator。用值22调用lower_bound(),也返回一个指向22的iterator。

iterator upper_bound( const key_type &key ):返回一个迭代器，指向键值> key的第一个元素。

// 6.set::lower_bound/upper_bound#include <iostream>#include <set>using namespace std;int main (){  set<int> myset;  set<int>::iterator it,itlow,itup;  for (int i=1; i<10; i++) myset.insert(i*10); // 10 20 30 40 50 60 70 80 90  itlow=myset.lower_bound (30);                //    >=   itup=myset.upper_bound (60);                 //     >               printf("%d %d",*itlow,*itup);  //  30 70  return 0;}

// 7.set::equal_elements#include <iostream>#include <set>using namespace std;int main (){  set<int> myset;  pair<set<int>::iterator,set<int>::iterator> ret;  for (int i=1; i<=5; i++) myset.insert(i*10);   // set: 10 20 30 40 50  ret = myset.equal_range(30);  cout << "lower bound points to: " << *ret.first << endl;  cout << "upper bound points to: " << *ret.second << endl;  return 0;} //lower bound points to: 30//upper bound points to: 40

set结构体的应用

#include<iostream>#include<set>using namespace std;struct haha{int a,b;char s;friend bool operator<(struct haha a,struct haha b){return a.s<b.s;}};set<struct haha>element;int main(){struct haha 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(d);element.insert(b);element.insert(c);element.insert(a);set<struct haha>::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<<" ";}

multiset的删除 重要

a.erase(x);//删除集合中所有的x
multiset<int>::iterator it = a.find(x);if (it != a.end()) {    a.erase(it);  //这里是删除其中的一个x;  删除的是一个位置  而arase是删除所有位置}

部分参考地址：

http://www.cnblogs.com/agpro/archive/2010/06/23/1763536.html