STL Set介紹
集合(Set)是一種包含已排序?qū)ο蟮年P(guān)聯(lián)容器。多元集合(MultiSets)和集合(Sets)相像，只不過支持重復(fù)對象,其用法與set基本相同。
Set 又稱集合，實際上就是一組元素的集合，但其中所包含的元素的值是唯一的，且是按一定順序排列的，集合中的每個元素被稱作集合中的實例。因為其內(nèi)部是通過鏈表的方式來組織，所以在插入的時候比vector 快，但在查找和末尾添加上比vector 慢。
multiset 是多重集合，其實現(xiàn)方式和set 是相似的，只是它不要求集合中的元素是唯一的，也就是說集合中的同一個元素可以出現(xiàn)多次。
構(gòu)造：
explicit set(const Compare&=compare());
如：set<int,less<int> > set1;
less<int>是一個標(biāo)準(zhǔn)類，用于形成升序排列函數(shù)對象。降序排列是用greater<int>。
Template<class InputIterator> set(InputIterator, InputIterator,\ const Compare&=compare());
如：set<int ,less<int> >set2(vector1.begin(),vector1.end());
通過指定某一預(yù)先定義的區(qū)間來初始化set對象的構(gòu)造函數(shù)。
set（const set<Key,Compare&>）;
如：set<int ,less<int> >set3(set2);
方法：1.begin() 返回指向第一個元素的迭代器
2.clear() 清除所有元素
3.count() 返回某個值元素的個數(shù)
4.empty() 如果集合為空，返回true
5.end() 返回指向最后一個元素的迭代器
6.equal_range() 返回第一個>=關(guān)鍵字的迭代器和>關(guān)鍵字的迭代器
語法：
pair <iterator,iterator>equal_range( const key_type &key );
//key是用于排序的關(guān)鍵字
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為第一個不被刪除的值)結(jié)束的元素
size_type erase( const key_type &key );
//刪除等于key值的所有元素（返回被刪除的元素的個數(shù)）
//前兩個返回第一個不被刪除的雙向定位器,不存在返回末尾
//第三個返回刪除個數(shù)
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不被插入）結(jié)束返回內(nèi)的元素插入到集合中
pair insert( const TYPE &val );
//插入val元素，返回指向該元素的迭代器和一個布爾值來說明val是否成功被插入
//應(yīng)該注意的是在集合(Sets中不能插入兩個相同的元素)
11.lower_bound() 返回指向大于（或等于）某值的第一個元素的迭代器
語法:
iterator lower_bound( const key_type &key );
//返回一個指向大于或者等于key值的第一個元素的迭代器
12.key_comp() 返回一個用于元素間值比較的函數(shù)
語法:
key_compare key_comp();
//返回一個用于元素間值比較的函數(shù)對象
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() 集合中元素的數(shù)目
17.swap() 交換兩個集合變量
語法:
void swap( set &object ); //交換當(dāng)前集合和object集合中的元素
18.upper_bound() 返回大于某個值元素的迭代器
語法:
iterator upwer_bound( const key_type &key );
//返回一個指向大于key值的第一個元素的迭代器
19.value_comp() 返回一個用于比較元素間的值的函數(shù)
語法:
iterator upper_bound( const key_type &key );//返回一個用于比較元素間的值的函數(shù)對象
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()));
以下轉(zhuǎn)自：
http://blog.csdn.net/wangji163163/article/details/3740948
Set是關(guān)聯(lián)容器。其鍵值就是實值，實值就是鍵值，不可以有重復(fù)，所以我們不能通過set的迭代器來改變set的元素的值，set擁有和list相同的特性：當(dāng)對他進(jìn)行插入和刪除操作的時候，操作之前的迭代器依然有效。當(dāng)然刪除了的那個就沒效了。Set的底層結(jié)構(gòu)是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。
其中個參數(shù)的意義如下：
key：要放入set里的數(shù)據(jù)類型，可以是任何類型的數(shù)據(jù)。
Traits：這是一個仿函數(shù)（關(guān)于仿函數(shù)是什么，我后面的文章會講到）。提供了具有比較功能的仿函數(shù)，來覺得元素在set里的排列的順序，這是一個可選的參數(shù)，默認(rèn)的是std::less<key>，如果要自己提供這個參數(shù)，那么必須要遵循此規(guī)則：具有兩個參數(shù)，返回類型為bool。
Allocator:空間配置器，這個參數(shù)是可選的，默認(rèn)的是std::allocator<key>.
二：set里的基本操作
我們可以通過下面的方法來實例化一個set對象
std::set<int> s;那個s這個對象里面存貯的元素是從小到大排序的，(因為用std::less作為比較工具。)
如果要想在s里面插入數(shù)據(jù)，可以用inset函數(shù)（set沒用重載[]操作，因為set本生的值和索引是相同的)
s.insert(3);s.insert(5).....
因為set是集合，那么集合本身就要求是唯一性，所以如果要像set里面插入數(shù)據(jù)和以前的數(shù)據(jù)有重合，那么插入不成功。
可以通過下面的方法來遍歷set里面的元素
1 std::set<int>::iterator it = s.begin();
2 while(it!=s.end())
3 {
4 cout<<*it++<<endl;//迭代器依次后移，直到末尾。
5 }
如果要查找一個元素用find函數(shù)，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相關(guān)的一組算法
set_intersection() :這個函數(shù)是求兩個集合的交集。下面是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 }
這是個模板函數(shù)，從上面的算法可以看出，傳進(jìn)去的兩個容器必須是有序的。_Dest指向輸出的容器，這個容器必須是預(yù)先分配好空間的，否則會出錯的,返回值指向保存結(jié)果的容器的尾端的下一個位置。eg.
1 set_union() :求兩個集合的并集，參數(shù)要求同上。
2
3 std::set_difference（）：差集
4
5 set_symmetric_difference（）：得到的結(jié)果是第一個迭代器相對于第二個的差集并上第二個相當(dāng)于第一個的差集。代碼：
6
7 struct compare
8 {
9 bool operator ()(string s1,string s2)
10 {
11 return s1>s2;
12 }///自定義一個仿函數(shù)
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