set和multiset

set和multiset：（两者用法基本相似，一个可重复一个不可重复）

1.一个容器，它其中所包含的元素的值是唯一的，集合中的元素按一定的顺序排列。

2.在插入操作和删除操作上比向量(vector)快，但查找或添加末尾的元素时会有些慢。

 

3.和所有关联式容器类似，通常使用平衡二叉树完成，事实上，set和multiset通常以红黑树实作而成。

4.自动排序的优点是使得搜寻元素时具有良好的性能，具有对数时间复杂度。但是造成的一个缺点就是：

不能直接改变元素值。因为这样会打乱原有的顺序。

改变元素值的方法是：先删除旧元素，再插入新元素。

存取元素只能通过迭代器，从迭代器的角度看，元素值是常数。

 

 

#include <set>

 

构造：

 

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

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

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

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

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

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

 

 

方法：

 

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

 

 

STL中与set相关的算法：

 

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());//上面两个差集的并集