C++ Sets & MultiSets 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

STL Set 交集 合集 差集

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,"???"));

總結(jié)

以上是生活随笔為你收集整理的C++ Sets MultiSets的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。