# set
一個紀錄是否有出現過的集合
# 標頭檔
#include<set> |
# 構造器 && 初始化
- 默認構造器： empty container constructor
- 範圍構造器： range constructor
- 複製構造器： copy constructor
#include <iostream> | |
#include <set> | |
struct classcomp { | |
bool operator() (const int& lhs, const int& rhs) const | |
{return lhs<rhs;} | |
}; | |
int main (){ | |
set<int> first; // 默認構造器 | |
int myints[]= {10,20,30,40,50}; | |
set<int> second (myints,myints+5); // 範圍構造器 | |
set<int> third (second); // 複製構造器 | |
set<int> fourth (second.begin(), second.end()); // 範圍 (指標) 構造器 | |
set<int,classcomp> fifth; // 有自訂比較函式的構造器 | |
} |
# insert
| 重載函數 | 形参 |
|---|---|
| 插入單個值 | pair<iterator,bool> insert (const value_type& val); |
| 有位置提示 | iterator insert (const_iterator position, const value_type& val); |
| 範圍 | template |
#include <iostream> | |
#include <set> | |
using namespace std; | |
void print(set<int>tmp){ | |
for(auto it:tmp) | |
cout<<' '<<it; | |
cout<<endl; | |
} | |
int main (){ | |
set<int> myset; | |
set<int>::iterator it; | |
pair<set<int>::iterator,bool> ret; | |
for (int i=1; i<=5; ++i) myset.insert(i*10); // set: 10 20 30 40 50 | |
ret = myset.insert(20); // 沒有插入新值 | |
if (ret.second==false) it=ret.first; // "it" 現在是指 20 的位置 | |
myset.insert (it,25); // 最有效率插入 | |
myset.insert (it,24); // 最有效率插入 | |
myset.insert (it,26); // 不是最有效率插入 | |
int myints[]= {5,10,15}; // 10 已經有了，所以不再插入 | |
myset.insert (myints,myints+3); | |
cout << "myset contains:"; | |
print(myset); | |
} |
輸出
myset contains: 5 10 15 20 24 25 26 30 40 50
# erase
set 刪除已存元素的方式，常見共有三種。
#include <iostream> | |
#include <set> | |
using namespace std; | |
int main (){ | |
set<int> myset; | |
set<int>::iterator it; | |
// insert some values: | |
for (int i=1; i<10; i++) myset.insert(i*10); // 10 20 30 40 50 60 70 80 90 | |
it = myset.begin(); | |
++it; // "it" 指向 20 的位置 | |
myset.erase (it); // 指標清除 | |
myset.erase (40); // 值的清除 | |
it = myset.find (60); | |
myset.erase (it, myset.end()); // 範圍型清除 | |
cout << "myset contains:"; | |
print(myset); | |
return 0; | |
} |
輸出
myset contains: 10 30 50
# find
尋找 set 中某一個值的位置，如果找到的位置為 st.end() 代表尚未找到
#include <iostream> | |
#include <set> | |
using namespace std; | |
int main () { | |
set<int> myset; | |
set<int>::iterator it; | |
for (int i=1; i<=5; i++) myset.insert(i*10); // set: 10 20 30 40 50 | |
it=myset.find(20); | |
myset.erase (it); | |
myset.erase (myset.find(40)); | |
cout << "myset contains:"; | |
print(myset); | |
return 0; | |
} |
輸出
myset contain: 10 30
# count
判斷 set 中，某值是否已出現
#include <iostream> | |
#include <set> | |
using namespace std; | |
int main (){ | |
set<int> myset; | |
for (int i=1; i<5; ++i) myset.insert(i*3); // set: 3 6 9 12 | |
for (int i=0; i<10; ++i) { | |
cout << i; | |
if (myset.count(i)) | |
cout << " is an element of myset.\n"; | |
else | |
cout << " is not an element of myset.\n"; | |
} | |
return 0; | |
} |
輸出
0 is not an element of myset.
1 is not an element of myset.
2 is not an element of myset.
3 is an element of myset.
4 is not an element of myset.
5 is not an element of myset.
6 is an element of myset.
7 is not an element of myset.
8 is not an element of myset.
9 is an element of myset.
# clear
清除整個 set 的工具
#include <iostream> | |
#include <set> | |
using namespace std; | |
int main (){ | |
set<int> myset; | |
myset.insert(100); | |
myset.insert(200); | |
myset.insert(300); | |
cout << "myset contains:"; | |
print(myset); | |
mymap.clear(); | |
myset.insert(1101); | |
myset.insert(2202); | |
cout << "myset contains:"; | |
print(mymap);` | |
} |
輸出
myset contains: 100 200 300
myset contains: 1101 2202
# empty
如果 set 為空， empty 返回 true ;
# size
返回 set 容器元素個數
# multiset
可以記錄出現次數的 set
# 標頭檔
#include<set> |
# 使用
跟 set 的使用幾乎一模一樣，差別在 count 的回傳值不會再只是 bool，而是出現的次數 (int)
#include <iostream> | |
#include <set> | |
using namespace std; | |
int main () { | |
int myints[]={10,73,12,22,73,73,12}; | |
multiset<int> mymultiset (myints,myints+7); | |
cout << "73 appears " << mymultiset.count(73) << " times in mymultiset.\n"; | |
return 0; | |
} |
# 延伸比較
與 priority_queue (優先佇列) 相比， multiset 取出任意一個元素要 O (log n)，但 priority_queue 要 O (n)。（這就是它叫做 queue 的原因）
