1数据插入
1.1 insert插入数据
#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指定位置插入数据
#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);
}
插入数据总是认为成功,如果已经存在，则返回已经存在的位置迭代器，否则，添加新的值，且返回位置迭代器。
1.3 数组/vector构建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])); //由数组构建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构建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循环
for(set<int>::iterator it = m.begin();it != m.end();it++){
cout << *it << endl;
}
- for_each()循环[推荐]
定义函数指针
inline void Display(int val){
cout << val << endl;
}
执行for_each
for_each(m.begin(),m.end(),Display);
- C++11auto迭代器写法
for(auto it = m.begin();it != m.end();it++){
cout << *it << endl;
}
- C++11 for-loop-scope迭代器写法[推荐]
for(auto p : m){
cout << p << endl;
}
- C++11 for_each()与lamdba表达式
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.删除
- 关键字删除
m.erase(val);
- 迭代器删除
m.erase(m.begin());
- 区域删除
m.erase(it_a,it_b);
5.排序
默认按照val升序排列。自定义排序时，可以在实例化加上val的comp仿函数或者重载<运算符。
set<value类型,comp> m;
6应用
set除了去重和排序的功能，还有一个应用是判断重复次数。
例如：
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 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) //如果当前set有num[i]元素则删除它，如果没有则插入
s.insert(nums[i]);
else
s.erase(nums[i]);
}
return *s.begin(); //最后剩下的就是唯一一个只出现了一次的元素
}
};
但是这代码有局限性，假设其余每个元素不止出现两次，上面代码就不能用了，如果是这种情况就应该考虑使用map了，找出value为1的元素就可以了。
不管是用map还是set都算使用了额外的空间，这个题目可以更加优化，两个相同数字异或等于0，所以可以遍历数组，最后剩下的也就是只出现一次的数字。
