STL Set介紹
集合(Set)是一種包含已排序對象的關聯容器。多元集合(MultiSets)和集合(Sets)相像，只不過支持重復對象,其用法與set基本相同。
Set 又稱集合，實際上就是一組元素的集合，但其中所包含的元素的值是唯一的，且是按一定順序排列的，集合中的每個元素被稱作集合中的實例。因為其內部是通過鏈表的方式來組織，所以在插入的時候比vector 快，但在查找和末尾添加上比vector 慢。
multiset 是多重集合，其實現方式和set 是相似的，只是它不要求集合中的元素是唯一的，也就是說集合中的同一個元素可以出現多次。
構造：
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);
方法：1.begin() 返回指向第一個元素的迭代器
2.clear() 清除所有元素
3.count() 返回某個值元素的個數
4.empty() 如果集合為空，返回true
5.end() 返回指向最后一個元素的迭代器
6.equal_range() 返回第一個>=關鍵字的迭代器和>關鍵字的迭代器
語法：
pair <iterator,iterator>equal_range( const key_type &key );
//key是用于排序的關鍵字
Set<int> ctr;
例如：
Pair<set<int>::iterator,set<int>::iterarot>p;
For(i=0;i<=5;i++) ctr.insert(i);
P=ctr.equal_range(2);
那么*p.first==2;*p.second==3;
7.erase() 刪除集合中的元素
語法:
iterator erase( iterator i ); //刪除i位置元素
iterator erase( iterator start, iterator end );
//刪除從start開始到end(end為第一個不被刪除的值)結束的元素
size_type erase( const key_type &key );
//刪除等于key值的所有元素（返回被刪除的元素的個數）
//前兩個返回第一個不被刪除的雙向定位器,不存在返回末尾
//第三個返回刪除個數
8.find() 返回一個指向被查找到元素的迭代器
語法:
iterator find( const key_type &key );
//查找等于key值的元素，并返回指向該元素的迭代器;
//如果沒有找到,返回指向集合最后一個元素的迭代器
9.get_allocator() 返回集合的分配器
10.insert() 在集合中插入元素
語法:
iterator insert( iterator i, const TYPE &val ); //在迭代器i前插入val
void insert( input_iterator start, input_iterator end );
//將迭代器start開始到end（end不被插入）結束返回內的元素插入到集合中
pair insert( const TYPE &val );
//插入val元素，返回指向該元素的迭代器和一個布爾值來說明val是否成功被插入
//應該注意的是在集合(Sets中不能插入兩個相同的元素)
11.lower_bound() 返回指向大于（或等于）某值的第一個元素的迭代器
語法:
iterator lower_bound( const key_type &key );
//返回一個指向大于或者等于key值的第一個元素的迭代器
12.key_comp() 返回一個用于元素間值比較的函數
語法:
key_compare key_comp();
//返回一個用于元素間值比較的函數對象
13.max_size() 返回集合能容納的元素的最大限值
14.rbegin() 返回指向集合中最后一個元素的反向迭代器
示例：
Set<int> ctr;
Set<int>::reverse_iterator rcp;
For(rcp=ctr.rbegin();rcp!=ctr.rend();rcp++)
Cout<<*rcp<<” ”;
15.rend() 返回指向集合中第一個元素的反向迭代器
16.size() 集合中元素的數目
17.swap() 交換兩個集合變量
語法:
void swap( set &object ); //交換當前集合和object集合中的元素
18.upper_bound() 返回大于某個值元素的迭代器
語法:
iterator upwer_bound( const key_type &key );
//返回一個指向大于key值的第一個元素的迭代器
19.value_comp() 返回一個用于比較元素間的值的函數
語法:
iterator upper_bound( const key_type &key );//返回一個用于比較元素間的值的函數對象
20.Set集合的并，交和差
set_union(a.begin(),a.end(),b.begin(),b.end(),insert_iterator<set<int> >(c,c.begin()));
set_intersection(a.begin(),a.end(),b.begin(),b.end(),insert_iterator<set<int> >(c,c.begin()));
set_difference(a.begin(),a.end(),b.begin(),b.end(),insert_iterator<set<int> >(c,c.begin()));
以下轉自：
http://blog.csdn.net/wangji163163/article/details/3740948
Set是關聯容器。其鍵值就是實值，實值就是鍵值，不可以有重復，所以我們不能通過set的迭代器來改變set的元素的值，set擁有和list相同的特性：當對他進行插入和刪除操作的時候，操作之前的迭代器依然有效。當然刪除了的那個就沒效了。Set的底層結構是RB-tree，所以是有序的。
stl中特別提供了一種針對set的操作的算法：交集set_intersection，并集set_union，差集set_difference。對稱差集set_symeetric_difference，這些算法稍后會講到。
一：set模板類的聲明。
1 template <
2 class Key,
3 class Traits=less<Key>,
4 class Allocator=allocator<Key>
5 >
6 class set。
其中個參數的意義如下：
key：要放入set里的數據類型，可以是任何類型的數據。
Traits：這是一個仿函數（關于仿函數是什么，我后面的文章會講到）。提供了具有比較功能的仿函數，來覺得元素在set里的排列的順序，這是一個可選的參數，默認的是std::less<key>，如果要自己提供這個參數，那么必須要遵循此規則：具有兩個參數，返回類型為bool。
Allocator:空間配置器，這個參數是可選的，默認的是std::allocator<key>.
二：set里的基本操作
我們可以通過下面的方法來實例化一個set對象
std::set<int> s;那個s這個對象里面存貯的元素是從小到大排序的，(因為用std::less作為比較工具。)
如果要想在s里面插入數據，可以用inset函數（set沒用重載[]操作，因為set本生的值和索引是相同的)
s.insert(3);s.insert(5).....
因為set是集合，那么集合本身就要求是唯一性，所以如果要像set里面插入數據和以前的數據有重合，那么插入不成功。
可以通過下面的方法來遍歷set里面的元素
1 std::set<int>::iterator it = s.begin();
2 while(it!=s.end())
3 {
4 cout<<*it++<<endl;//迭代器依次后移，直到末尾。
5 }
如果要查找一個元素用find函數，it = s.find(3);這樣it是指向3的那個元素的。可以通過rbegin，rend來逆向遍歷
1 std::set<int>::reverse_iterator it = s.rbegin();
2
3 while(it!=s.rend())
4
5 {cout<<*it++<<endl;}
還有其他的一些操作在這就不一一列出了。
三：與set相關的一組算法
set_intersection() :這個函數是求兩個集合的交集。下面是stl里的源代碼
1 template<class _InIt1,
2 class _InIt2,
3 class _OutIt> inline
4 _OutIt set_intersection(_InIt1 _First1, _InIt1 _Last1,
5 _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
6 { // AND sets [_First1, _Last1) and [_First2, _Last2), using operator<
7 for (; _First1 != _Last1 && _First2 != _Last2; )
8 if (*_First1 < *_First2)
9 ++_First1;
10 else if (*_First2 < *_First1)
11 ++_First2;
12 else
13 *_Dest++ = *_First1++, ++_First2;
14 return (_Dest);
15 }
這是個模板函數，從上面的算法可以看出，傳進去的兩個容器必須是有序的。_Dest指向輸出的容器，這個容器必須是預先分配好空間的，否則會出錯的,返回值指向保存結果的容器的尾端的下一個位置。eg.
1 set_union() :求兩個集合的并集，參數要求同上。
2
3 std::set_difference（）：差集
4
5 set_symmetric_difference（）：得到的結果是第一個迭代器相對于第二個的差集并上第二個相當于第一個的差集。代碼：
6
7 struct compare
8 {
9 bool operator ()(string s1,string s2)
10 {
11 return s1>s2;
12 }///自定義一個仿函數
13 };
14 int main()
15 {
16 typedef std::set<string,compare> _SET;
17 _SET s;
18 s.insert(string("sfdsfd"));
19 s.insert(string("apple"));
20 s.insert(string("english"));
21 s.insert(string("dstd"));
22 cout<<"s1:"<<endl;
23 std::set<string,compare>::iterator it = s.begin();
24 while(it!=s.end())
25 cout<<*it++<<" ";
26 cout<<endl<<"s2:"<<endl;
27 _SET s2;
28 s2.insert(string("abc"));
29 s2.insert(string("apple"));
30 s2.insert(string("english"));
31 it = s2.begin();
32 while(it!=s2.end())
33 cout<<*it++<<" ";
34 cout<<endl<<endl;
35
36 string str[10];
37 string *end = set_intersection(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//求交集，返回值指向str最后一個元素的尾端
38 cout<<"result of set_intersection s1,s2:"<<endl;
39 string *first = str;
40 while(first<end)
41 cout <<*first++<<" ";
42 cout<<endl<<endl<<"result of set_union of s1,s2"<<endl;
43 end = std::set_union(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//并集
44 first = str;
45 while(first<end)
46 cout <<*first++<<" ";
47 cout<<endl<<endl<<"result of set_difference of s2 relative to s1"<<endl;
48 first = str;
49 end = std::set_difference(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//s2相對于s1的差集
50 while(first<end)
51 cout <<*first++<<" ";
52 cout<<endl<<endl<<"result of set_difference of s1 relative to s2"<<endl;
53 first = str;
54 end = std::set_difference(s2.begin(),s2.end(),s.begin(),s.end(),str,compare());//s1相對于s2的差集
55
56 while(first<end)
57 cout <<*first++<<" ";
58 cout<<endl<<endl;
59 first = str;
60 end = std::set_symmetric_difference(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//上面兩個差集的并集
61 while(first<end)
62 cout <<*first++<<" ";
63 cout<<endl;
64 }
65
66 set<int> s3 ;
67 set<int>::iterator iter = s3.begin() ;
68 set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(),inserter(s3,iter));
69 copy(s3.begin(),s3.end(), ostream_iterator<int>(cout," "));
posted on 2012-06-05 10:51
王海光 閱讀(1172)
評論(0) 編輯 收藏 引用 所屬分類:
STL