【概述】

set 和 multiset?是集合數(shù)據(jù)容器，通過鏈表進(jìn)行組織，具體實現(xiàn)采用了紅黑樹的平衡二叉樹的數(shù)據(jù)結(jié)構(gòu)，兩者均定義在 <set> 頭文件中，其會根據(jù)特定的規(guī)則，自動將元素排序。

兩者不同在于，set 不允許元素重復(fù)，而 multiset 允許元素重復(fù)。

在插入操作和刪除操作上比 vector 快，但查找或添加末尾的元素時會有些慢。

【定義】

定義：?set<type> setName、multiset<type> multisetName

• set<type> s：產(chǎn)生一個空的 set/multiset，其中不含任何元素
• set<type> s(op)：以 op 為排序準(zhǔn)則，生成一個 set/multiset
• set<type> s1(s2)：產(chǎn)生某個 set/multiset 的副本，所有元素均被復(fù)制
• set<type> s(beg, end)：以迭代器的區(qū)間 [beg; end] 內(nèi)的元素產(chǎn)生一個 set/multiset
• set<type> s(beg, end, op)：以 op 為排序準(zhǔn)則，利用迭代器的區(qū)間 [beg; end] 內(nèi)的元素生成一個 set/multiset

默認(rèn)情況下，由小到大排序，若想按照自己的方式排序，一般重載小于號

struct type{int x,y;bool operator < (const type &a) const{if(x!=a.x)return x<a.x;return y<a.y;} } set<type> s;

【基本操作】

對于 set<type> s 的基本操作有：

• s.size()：返回容器大小
• s.empty()：返回容器是否為空。
• s.clear()：清空容器
• s.count(elem)：返回元素值為?elem?的元素的個數(shù)
• s.insert(elem) ：加入一個?elem?副本，返回新元素位置
• s.erase(elem)：移除與?elem?元素相等的所有元素，返回被移除的元素個數(shù)

【迭代器操作】

對于?set<type> s 的迭代器 it 的操作有：

• s.begin()：返回一個雙向迭代器，指向第一個元素
• s.end()：返回一個雙向迭代器，指向最后一個元素的下一?個位置
• s.erase(it)：移除迭代器?it 所指位置上的元素，無返回值
• s.lower_bound(elem)：返回?elem?的第一個可安插的位置，即元素值?>= elem?的第一個元素位置
• s.upper_bound(elem)：返回?elem?的最后一個可安插的位置，即元素值 > elem?的第一個元素的位置

【自定義數(shù)據(jù)類型】

當(dāng)要在 multiset 中存儲自定義數(shù)據(jù)類型時，除了要寫自定義類型的存儲結(jié)構(gòu)外，還要寫一個比較函數(shù) cmp 來告訴 multiset 如何去比較自定義類型。

struct?Node{int?x,y; }; struct cmp{bool operator()(const Node &a,const Node &b){if(a.x==b.x)return a.y<b.y;return a.x<b.x;} }; multiset<Node,cmp> s;

?

總結(jié)

以上是生活随笔為你收集整理的C++语言基础 —— STL —— 容器与迭代器 —— set 与 multiset的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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