set的常見用法詳解
- 集合，自動內(nèi)部有序且不含重復(fù)元素的容器蒿秦。
- 使用環(huán)境
- 去掉重復(fù)元素
- 元素比較大或者類型不是int而不能直接開散列表
- 自動排序
- How to use?
#include<set> using namespace std; - set的定義
- 單獨定義一個set：
set<typename> name; - set數(shù)組的定義:
set<typename> nameArray[size];
- 單獨定義一個set：
- 訪問元素
除開vector和string之外的stl容器都不支持*(it+1)的訪問方式 - 常用函數(shù)解析
-
insert(x): O(logN)头朱，自動遞增排序和去重 -
find(value): 返回set中對應(yīng)值為value的迭代器，O(logN)
set<int> st; set<int>::iterator it = st.find(2); printf("%d", *it); // 也可以 printf("%d", *st.find(2));-
erase(): 刪除單個元素，刪除一個區(qū)間內(nèi)的元素刪除單個元素
1.erase(it): it為所需要刪除的迭代器绸栅，O(1).可以結(jié)合find(value)來使用。 例：st.erase(st.find(5));
2.erase(value): value為所需要刪除的元素页屠。O(logN)刪除一個區(qū)間的元素
-st.erase(first, last)刪除[first, last), O(last-first)
size(), O(1)clear(), O(n
-
- 主要作用
- 自動去重按升序排序
- 延伸：
- set中元素是唯一的粹胯，如果需要處理不唯一的情況，則需要使用multiset辰企。另外风纠，c++11標準中還增加了unordered_set,以散列替代set內(nèi)部的紅黑樹實現(xiàn)，使其可以用來處理去重但不排序的需求牢贸，速度比set要快得多
相關(guān)習(xí)題
#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
int N;
scanf("%d", &N);
vector<set<int> > nums(N+1);
for(int i = 1; i <= N; i++) {
int M;
scanf("%d", &M);
for(int j = 0; j < M; j++) {
int num;
// printf("[i: %d]", i);
scanf("%d", &num);
nums[i].insert(num);
}
}
//
int K;
scanf("%d", &K);
for(int a = 0; a < K; a++) {
int x, y;
scanf("%d%d", &x, &y);
int wholesize = nums[x].size() + nums[y].size();
set<int> tmp;
for(set<int>::iterator it1 = nums[x].begin(); it1 != nums[x].end(); it1++) {
tmp.insert(*it1);
}
for(set<int>::iterator it2 = nums[y].begin(); it2 != nums[y].end(); it2++) {
tmp.insert(*it2);
}
int completesize = tmp.size();
int commonsize = wholesize - completesize;
printf("%.1f%%\n", (float(commonsize)/completesize) * 100);
}
return 0;
}
