STL—— set的使用

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，所以可以遍历数组，最后剩下的也就是只出现一次的数字。