STL set和multiset

STL 对这个序列可以进行查找，插入删除序列中的任意一个元素，而完成这些操作的时间同这个序列中元素个数的对数成比例关系，并且当游标指向一个已删除的元素时，删除操作无效。而一个经过更正的和更加实际的定义应该是：一个集合(set)是一个容器，它其中所包含的元素的值是唯一的。这在收集一个数据的具体值的时候是有用的。集合中的元素按一定的顺序排列，并被作为集合中的实例。一个集合通过一个链表来组织，在插入操作和删除操作上比向量(vector)快，但查找或添加末尾的元素时会有些慢。具体实现采用了红黑树的平衡二叉树的数据结构。

目录

1集和多集（set 和multiset 容器类）

2构造

3方法：

4集合操作：

5例子：

1集和多集（set 和multiset 容器类）编辑

#include <set>

一个集合（set）是一个容器，它其中所包含的元素的值是唯一的。

集和多集的区别是：set支持唯一键值，set中的值都是特定的，而且只出现一次；而multiset中可以出现副本键，同一值可以出现多次。

2构造编辑

explicit set(const Compare&=compare());

如：set<int,less<int> > set1;

less<int>是一个标准类，用于形成升序排列函数对象。降序排列是用greater<int>。

Template<class InputIterator> set(InputIterator, InputIterator,\ const Compare&=compare());

如：set<int ,less<int> >set2(vector1.begin(),vector1.end());

通过指定某一预先定义的区间来初始化set对象的构造函数。

set（const set<Key,Compare&>）;

如：set<int ,less<int> >set3(set2);

复制构造函数。

3方法：编辑

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() 返回一个用于比较元素间的值的函数

4集合操作：编辑

std::set_intersection() :这个函数是求两个集合的交集。

std::set_union() :求两个集合的并集

std::set_difference（）：差集

std::set_symmetric_difference（）：得到的结果是第一个迭代器相对于第二个的差集并 上第二个相当于第一个的差集

struct compare{

bool operator ()(string s1,string s2){

return s1>s2;

}///自定义一个仿函数

};

std::set<string,compare> s

string str[10];

string *end = set_intersection(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//求交集，返回值指向str最后一个元素的尾端

end = std::set_union(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//并集

end = std::set_difference(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//s2相对于s1的差集

end = std::set_difference(s2.begin(),s2.end(),s.begin(),s.end(),str,compare());//s1相对于s2的差集

end = std::set_symmetric_difference(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//上面两个差集的并集

5例子：编辑

1///////////////////////////////////////////////////////////////////

#include <iostream>

#include <set>

using namespace std;

int main(void)

{

set<int> set1;

for(int i=0; i<10; ++i)

set1.insert(i);

for(set<int>::iterator p=set1.begin();p!=set1.end();++p)

cout<<*p<<"";

if(set1.insert(3).second)//把3插入到set1中

//插入成功则set1.insert(3).second返回1，否则返回0

//此例中，集中已经有3这个元素了，所以插入将失败

cout<<"set insert success";

else

cout<<"set insert failed";

int a[] = {4, 1, 1, 1, 1, 1, 0, 5, 1, 0};

multiset<int> A;

A.insert(set1.begin(),set1.end());

A.insert(a,a+10);

cout<<endl;

for(multiset<int>::iterator p=A.begin();p!=A.end();++p)

cout<<*p<<" ";

cin.get();

return 0;

}

2////////////////////////////////////////

#include <iostream>

#include <set>

#include <string>

#include <algorithm>

using namespace std;

struct compare

{

bool operator ()(string s1,string s2)

{

return s1>s2;

}///自定义一个仿函数

};

int main()

{

typedef std::set<string,compare> _SET;

_SET s;

s.insert(string("sfdsfd"));

s.insert(string("apple"));

s.insert(string("english"));

s.insert(string("dstd"));

cout<<"s1:"<<endl;

std::set<string,compare>::iterator it = s.begin();

while(it!=s.end())

cout<<*it++<<" ";

cout<<endl<<"s2:"<<endl;

_SET s2;

s2.insert(string("abc"));

s2.insert(string("apple"));

s2.insert(string("english"));

it = s2.begin();

while(it!=s2.end())

cout<<*it++<<" ";

cout<<endl<<endl;

string str[10];

string *end = set_intersection(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//求交集，返回值指向str最后一个元素的尾端

cout<<"result of set_intersection s1,s2:"<<endl;

string *first = str;

while(first<end)

cout <<*first++<<" ";

cout<<endl<<endl<<"result of set_union of s1,s2"<<endl;

end = std::set_union(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//并集 first = str;

while(first<end)

cout <<*first++<<" ";

cout<<endl<<endl<<"result ofset_differenceof s2 relative to s1"<<endl;

first = str;

end = std::set_difference(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//s2相对于s1的差集 while(first<end)

cout <<*first++<<" ";

cout<<endl<<endl<<"result ofset_differenceof s1 relative to s2"<<endl;

first = str;

end = std::set_difference(s2.begin(),s2.end(),s.begin(),s.end(),str,compare());//s1相对于s2的差集

while(first<end)

cout <<*first++<<" ";

cout<<endl<<endl;

first = str;

end = std::set_symmetric_difference(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//上面两个差集的并集 while(first<end)

cout <<*first++<<" ";

cout<<endl;

}