set概述

set是根据元素值进行排序的集合，且集合中不存在重复元素。set是由二叉搜索树实现，且对树进行了平衡处理，使得元素在树中的分布较均匀，所以set中的插入、删除以及搜索操作的复杂度都是O(logn)。

set常用成员函数

  1. begin() -- 返回指向set开头的迭代器
  2. end() -- 返回指向set末尾的迭代器
  3. size() -- 返回set中的元素总数
  4. clear() -- 清空set中所有元素
  5. erase(x) -- 删除含有x的元素
  6. insert(x) -- 插入元素x
  7. find(x) -- 搜索与x相等的元素，并返回指向该元素的迭代器，若找不到与x相等的元素则返回末尾end()

set的典型应用

题目描述

Kiana拿到了一个可以控制路灯的遥控器。她只需要在遥控器上输入一个编号，就可以改变该编号对应的那盏路灯的状态。在初始状态下所有的灯都是熄灭的。Kiana很喜欢这个遥控器，她胡乱地开关着那些路灯，直到某一刻她发现当前恰好只有一个路灯是亮的，她想知道正在亮着的是哪个路灯，可是那盏灯离她太远了，她看不清那盏灯的编号。还好遥控器保留了她所有的操作记录，请你根据她的操作记录推测出亮着的灯的编号。

输入描述

第一行为一个整数n，代表共有n条操作记录
接下来一行有n个数，代表 n 个被操作的路灯编号 numi。
n < 1e6
num < 1e10

输出描述

输出为一个整数，即开着的灯的编号

解题技巧

由于使用数组存以及搜索不是爆时间就是爆内存，所以直接巧妙利用set中的函数解题。

C++代码

#include<iostream>
#include<cstdio>
#include<set>
#define ll long long
using namespace std;

set<ll> s;

int main(){
    int n;
    cin>>n;
    while(n--){
        ll x;
        scanf("%lld",&x);
        if(s.find(x)!=s.end())
            s.erase(x);
        else
            s.insert(x);
    }
    cout<<*s.begin();
    return 0;
}

写在后面

这道题还有另一种解法更为巧妙方便，利用异或运算符！！！

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

int main() {
    int n;
    cin >> n;
    ll ans = 0, x;
    while(n--) {
        scanf("%lld", &x);
        ans ^= x;
    }
    printf("%lld", ans);
    return 0;
}