1數(shù)據(jù)插入
1.1 insert插入數(shù)據(jù)
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
void Display(int val){
cout << val << endl;
}
int main(){
set<int> m;
for(int i=0;i<10;i++){
m.insert(i);
}
for_each(m.begin(),m.end(),Display);
}
1.2 insert指定位置插入數(shù)據(jù)
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
void Display(int val){
cout << val << endl;
}
int main(){
set<int> m;
for(int i=0;i<10;i++){
m.insert(i);
}
m.insert(m.begin(),100);
for_each(m.begin(),m.end(),Display);
}
插入數(shù)據(jù)總是認(rèn)為成功,如果已經(jīng)存在湾宙，則返回已經(jīng)存在的位置迭代器樟氢，否則，添加新的值侠鳄，且返回位置迭代器埠啃。
1.3 數(shù)組/vector構(gòu)建set
1 #include <iostream>
2 #include <set>
3 #include <algorithm>
4
5 using namespace std;
6
7 void Print(int n)
8 {
9 cout<<n<<" ";
10 }
11
12
13 int main()
14 {
15 int arr[] = {1,2,3,3,6,6,5,5,4,4,7};
16 set<int> s(arr,arr+sizeof(arr)/sizeof(arr[0])); //由數(shù)組構(gòu)建set
17 for_each(s.begin(),s.end(),Print);
18 cout<<endl;
19
20 s.erase(s.begin(),s.end());
21 for_each(s.begin(),s.end(),Print);
22 cout<<endl;
23
24 vector<int> vec(arr,arr+sizeof(arr)/sizeof(arr[0]));
25 set<int> s1(vec.begin(),vec.end()); //由vector構(gòu)建set
26 for_each(s1.begin(),s1.end(),Print);
27 cout<<endl;
28 }
//set可以做去重和排序處理
1 2 3 4 5 6 7
1 2 3 4 5 6 7
2遍歷
- 迭代器for循環(huán)
for(set<int>::iterator it = m.begin();it != m.end();it++){
cout << *it << endl;
}
- for_each()循環(huán)[推薦]
定義函數(shù)指針
inline void Display(int val){
cout << val << endl;
}
執(zhí)行for_each
for_each(m.begin(),m.end(),Display);
- C++11auto迭代器寫(xiě)法
for(auto it = m.begin();it != m.end();it++){
cout << *it << endl;
}
- C++11 for-loop-scope迭代器寫(xiě)法[推薦]
for(auto p : m){
cout << p << endl;
}
- C++11 for_each()與lamdba表達(dá)式
for_each(m.begin(),m.end(),[](int p){
cout << p << endl;
});
3.查找
3.1 count()判斷值是否存在
if(m.count(val) == 1){
//如果存在
...
}
3.2 find()判斷值是否存在以及位置
set<int>::iterator it = m.find(val);
if(m.end() != it){
...
}
4.刪除
- 關(guān)鍵字刪除
m.erase(val);
- 迭代器刪除
m.erase(m.begin());
- 區(qū)域刪除
m.erase(it_a,it_b);
5.排序
默認(rèn)按照val升序排列。自定義排序時(shí)伟恶，可以在實(shí)例化加上val的comp仿函數(shù)或者重載<運(yùn)算符碴开。
set<value類型,comp> m;
6應(yīng)用
set除了去重和排序的功能，還有一個(gè)應(yīng)用是判斷重復(fù)次數(shù)博秫。
例如：
給定一個(gè)非空整數(shù)數(shù)組潦牛，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)兩次挡育。找出那個(gè)只出現(xiàn)了一次的元素巴碗。
說(shuō)明：
你的算法應(yīng)該具有線性時(shí)間復(fù)雜度。 你可以不使用額外空間來(lái)實(shí)現(xiàn)嗎即寒？
示例 1:
輸入: [2,2,1]
輸出: 1
示例 2:
輸入: [4,1,2,1,2]
輸出: 4
class Solution {
public:
int singleNumber(vector<int>& nums) {
set<int> s;
for(int i = 0;i < nums.size();i++)
{
if(s.count(nums[i]) == 0) //如果當(dāng)前set有num[i]元素則刪除它橡淆，如果沒(méi)有則插入
s.insert(nums[i]);
else
s.erase(nums[i]);
}
return *s.begin(); //最后剩下的就是唯一一個(gè)只出現(xiàn)了一次的元素
}
};
但是這代碼有局限性，假設(shè)其余每個(gè)元素不止出現(xiàn)兩次母赵，上面代碼就不能用了逸爵，如果是這種情況就應(yīng)該考慮使用map了，找出value為1的元素就可以了凹嘲。
不管是用map還是set都算使用了額外的空間痊银，這個(gè)題目可以更加優(yōu)化，兩個(gè)相同數(shù)字異或等于0施绎，所以可以遍歷數(shù)組溯革，最后剩下的也就是只出現(xiàn)一次的數(shù)字。
