引入：
集合和映射也是兩個常用的容器。set就是數學上的集合——每個元素最多只出現一次。和sort一樣，自定義類型也可以構造set，但同樣必須定義“小于”運算符。

頭文件：
#include<set>（當然，如果愿意，你也可以用#include<bits/stdc++.h>這個萬能庫，但是會導致內存巨大。。。

聲明：

set<int > s;//普通的定義（不允許元素重復） struct rec{...};set<rec > s;//結構體 multiset<double > s;//（允許集合中元素重復） //注意：set和multiset存儲的元素必須定義“小于號”運算符

size/empty/clear：
與vector類似，分別為元素個數、是否為空、清空。前兩者的時間復雜度為\(O(1)\)。

迭代器：
set和multiset的迭代器稱為“雙向訪問迭代器”（類似于指針），不支持“隨機訪問”，支持星號“*"解除引用，僅支持“++”和“- -”兩個與運算相關的操作。
設\(it\)是一個迭代器，例如set<int > :: iterator it;
若把\(it\)++，則\(it\)將會指向下一個元素。這里的“下一個”是指在元素從小到大排序的結果中，排在\(it\)下一名的元素。同理，若把\(it\)- -，則\(it\)將會指向排在“上一個”的元素。
請注意，執行“++”和“- -”操作的時間復雜度都是\(O(log n)\)。執行操作前后，務必仔細檢查，避免迭代器指向的位置超出首、尾迭代器之間的范圍。

begin/end：
返回集合的首、尾迭代器，時間復雜度為\(O(1)\)。
s.begin() 是指向集合中最小元素的迭代器。
s.end() 是指向集合中最大元素的下一個位置的迭代器。換言之，就像 vector 一樣，是一個“前閉后開”的形式。因此 - -end() 是指向集合中最大元素的迭代器。

insert：
s.insert(x) 把一個元素 x 插入到集合 s 中，時間復雜度為\(O(log n)\)。
在 set 中，若元素已存在，則不會重復插入該元素，對集合的狀態無影響。

下面的代碼把 n 個整數插入有序多重集 multiset ，并從小到大輸出，時間復雜度\(O(n log n)\)，相當于進行了一次排序。假設 n 個整數目前存儲在數組 a[1~n]中。

multiset<int > s; for(int i=1;i<=n;i++)s.insert(a[i]); for(multiset<int > :: iterator it=s.begin();it!=s.end();it++) cout<<*id<<endl;

find：
s.find(x) 在集合s中查找等于 x 的元素，并返回指向該指針的迭代器。若不存在，則返回 s.end() 。時間復雜度\(O(log n)\)。

lower_bound/upper_bound：
這兩個函數的用法與 find 類似，但查找的條件略有不同，時間復雜度\(O(log n)\)。
s.lower_bound(x) 查找>=x 的元素中最小的一個，并返回指向該元素的迭代器。
s.upper.bound(x) 查找 >x 的 元 素中最小的一個，并返回指向該元素的迭代器。

erase：
設 it 是一個迭代器， s.erase(it) 從 s 中刪除迭代器 it 指向的元素，時間復雜度為\(O(log n)\)。
設 x 是一個元素， s.erase(x) 從 s 中刪除所有等于 x 的元素，時間復雜度為\(O(k+logn)\)，其中 k 為被刪除的元素個數。
如果想從 multiset 中刪掉至多1個等于 x 的元素，可以執行：

if((it==s.find(x))!=s.end())s.erase(it);

count：
s.count(x) 返回集合 s 中等于 x 的元素個數，時間復雜度為\(O(k+logn)\)，其中 k 為元素 x 的個數。

//劉汝佳大神的書《算法競賽入門經典》上的例題:

[UVa 10815]Andy's First Dictionary 安迪的第一個字典

//此處貼上lrj資源包里的標程 //由于string已經定義了“小于”運算符，直接使用set保存單詞集合即可#include<iostream> #include<string> #include<set> #include<sstream> using namespace std;set<string> dict; string s, buf;int main() {while(cin >> s) {for(int i = 0; i < s.length(); i++)if(isalpha(s[i])) s[i] = tolower(s[i]); else s[i] = ' ';stringstream ss(s);while(ss >> buf) dict.insert(buf);}for(set<string>::iterator it = dict.begin(); it != dict.end(); ++it)cout << *it << "\n";return 0; }

轉載于:https://www.cnblogs.com/Luvwgyx/p/8455273.html

總結

以上是生活随笔為你收集整理的C++ STL set（集合）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。