2019校招深信服编程题（找出前10个访问网站的id发奖金）

题目描述：
输入一组数据，找出前10个输入的不同的数作为访问网站的用户id，发奖金。
输入第一个数n表示后面要输入多少个访问网站的id（可能重复）
输出第一个数表示得奖金的用户数，后面每一行输出得奖的用户id，注意是按照访问网站的时间顺序输出。

#include<iostream>
#include<set>
#include<vector>

using namespace std;

int main()
{
    set<int> s_users;   //使用set的目的就是去重，只插入不重复的id。但是坏处是会被排序
    vector<int> v_users;    //判断插入成功的，则存入vector，作为结果保存，可按时间顺序输出
    int n;
    cin >> n;   //输入后续要输入的访问次数
    int count = 0;  //记录统计的非重复id数，达到10个时退出循环，输出结果
    for (int i = 0; i < n; i++)
    {
        int id;
        cin >> id;
        pair<set<int>::iterator, bool> pr = s_users.insert(id);  //最核心语句，根据insert返回值判断
        if (pr.second == true)
        {
            //说明此id第一次出现，加入set成功。则加入到vector
            v_users.push_back(id);
            count++;
            if (10 == count)
            {
                break;
            }
        }
    }

    cout << v_users.size() << endl;
    for (int id:v_users)
    {
        cout << id << endl;
    }
        return 0;
}

上面解法的重点在于会使用pair<set<int>::iterator, bool> pr = s_users.insert(id);，然后就可以根据返回值判断是否插入成功。但是如果不知道这一句怎么办呢？
下面是一种稍显复杂，但是也挺有意思的解法。先用一个user结构体保存用户id以及访问网站的顺序index。先用set集合根据用户id来去重，但是得到的集合是按照用户id排序了的，而我们输出答案的时候要按照index排序输出。可以将set集合中的元素都复制添加到一个vector中，然后让vector根据index排序，再按照vector输出答案即可。
》在这种解法中还可以看到set自定义排序方式，使用STL的sort函数的自定义为vector排序方式。

#include<iostream>
#include<set>
#include<vector>
#include<algorithm> //使用全局的sort()函数会用到

using namespace std;
//使用struct和class的区别主要是，struct内成员默认是public，而class是默认private
struct user 
{
    int id; //用户id
    int index;  //访问网站的次序
    user(int &a, int &b):id(a),index(b){}
    //重载<操作符，试试能不能直接用于less的比较
    bool operator<(const user &a) const     //注意const不能少，否则编译报错
    {
        //return this->index < a.index; //用于vector根据index使用STL的sort进行排序
        return this->id < a.id; //用于set在定义时用于模板第二参数重载less根据id进行排序
    }
};
//仿函数，作为set定义时的参数，用于排序
class s_user_comp
{
public:
    bool operator()(const user &a, const user &b) 
    {
        //仿函数中必定会重载()操作符
        return a.id < b.id;
    }
};

//只定义一个函数，使用的时候直接将函数名作为sort()的第三参数，当做函数指针调用
bool v_users_comp_func(const user &a, const user &b)
{
    return a.index < b.index;
}
//使用仿函数来为sort()函数提供第三参数
class v_users_comp_obj
{
public:
    bool operator()(const user &a, const user &b)
    {
        //仿函数中必定会重载()操作符
        return a.index < b.index;
    }
};

int main()
{
    int n;
    cin >> n;
    //set<user, s_user_comp> s_users;   //使用外部的仿函数类来定义<
    //使用user类中重载的<来定义<，默认的less仿函数内部因为会用到<比较，此时能检测到<被重载了
    set<user> s_users;      
    s_users.clear();
    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        s_users.insert(user(a,i));  //用user(a,i)构造一个临时对象
        if (s_users.size() == 10)
        {
            break;  //检查的set中已有10个不同的id的用户，则退出循环
        }
    }

    int size = s_users.size();
    cout << size << endl;
    vector<user> v_users;

    for (user u:s_users)
    {
        //遍历set，将元素都复制加入到vector
        v_users.push_back(u);
    }
    //使用函数指针进行排序，没问题，可以输出正确答案
    //sort(v_users.begin(), v_users.end(), v_users_comp_func);  
    //使用仿函数传入临时对象进行排序，没问题，可以输出正确答案
    sort(v_users.begin(), v_users.end(), v_users_comp_obj());   
    //使用user类内部重载的<号进行排序，没问题，可以输出正确答案
    //sort(v_users.begin(), v_users.end()); 
    for (user u : v_users)
    {
        //遍历vector，输出需要的用户id
        cout << u.id << endl;
    }

    return 0;
}

【总结】
1、对于set中自定义排序方式，可以有两种。
一是在要加入到set的元素user的类中重载<操作符，这样在set对象定义时只需简单的set<user> s_users;即可；
二是在外部自定义仿函数(一个类)s_user_comp，重载()操作符，传入user引用作为重载函数的参数，使用时要将仿函数名传入set模板中替换掉默认的less仿函数，如set<user, s_user_comp> s_users;。
2、对于给STL的sort函数自定义排序方式，可以有三种方式。
一是使用传入两个迭代器参数的sort函数，但是要在user类中重载<操作符；sort(v_users.begin(), v_users.end());
二是使用传入3个参数的sort函数，在外部自定义一个普通的比较函数，并传入函数名作为函数指针给sort的第三个参数；sort(v_users.begin(), v_users.end(), v_users_comp_func);
三是使用传入3个参数的sort函数，在外部自定义一个仿函数（类），并传入仿函数临时对象(类名())，作为sort的第三个参数。sort(v_users.begin(), v_users.end(), v_users_comp_obj());