C++ set使用方面的小tip（补充有优先队列的使用）

• • • • 平时写文章比较少，知识层次也有限，如有不妥欢迎大家批评指正，我们共同进步。

下面先给出该题目的简单介绍，偷个懒就不打字了，直接截图

下面是实现的代码：

class FM{
public:
    string food,cuisine;
    int rate;
    FM(){
        food = cuisine = "";
        rate = 0;
    }
    FM(string food,string cuisine,int rate):food(food),cuisine(cuisine),rate(rate){
        //cout<<"普通构造函数被调用了"<
        //cout<<"拷贝构造函数被调用了"<
        if (rate == other.rate)
            return food > other.food;
        return rate < other.rate;
    }
};

class FoodRatings {
    unordered_map fs;
    unordered_map> cs;
public:
    FoodRatings(vector &foods, vector &cuisines, vector &ratings) {
        for (int i = 0; i < foods.size(); ++i) {
            string f = foods[i], c = cuisines[i];
            int r = ratings[i];
            FM fm(f,c,r);
            fs[f] = fm;
            cs[c].emplace(fm);
        }
    }

    void changeRating(string food, int newRating) {
        string c = fs[food].cuisine;
        cs[c].erase(fs[food]);
        fs[food].rate = newRating;
        cs[c].emplace(fs[food]);
    }

    string highestRated(string cuisine) {
        return cs[cuisine].rbegin()->food;
    }
};

这个题目不难，中等水平，不过却包含了非常多的知识点

一. set与unordered_set的存储区别
set的底层实现是平衡二叉树，而unordered_set是哈希表，这就要求unordered_set的内容必须是可哈希的，而set则不需要；set是有序的，unordered_set是无序的；set搜索元素的复杂度是对数级别，而unordered_set是线性级别。
二. 如何利用set对自定义类型进行排序
set中的元素自动排序，这就要求不能直接改变元素的内容，因为这样会破坏排好的序，必须先删除再插入；set有内置的排序函数，但是对于自定义类型，则需要先对操作符进行重载，当然也有自定义比较函数的，不过我认为重载操作符比较直观。

class FM{
public:
    string food,cuisine;
    int rate;
    FM(){
        food = cuisine = "";
        rate = 0;
    }
    FM(string food,string cuisine,int rate):food(food),cuisine(cuisine),rate(rate){
        //cout<<"普通构造函数被调用了"<
        //cout<<"拷贝构造函数被调用了"<
        if (rate == other.rate)
            return food > other.food;
        return rate < other.rate;
    }
};

重载操作符，参数必须为常量引用，否则会报错。另外自定义数据类型要实现普通构造函数和拷贝构造函数，拷贝构造函数的参数也必须是常量引用，可以使用初始化列表进行初始化。
三. 什么情况下会调用拷贝构造函数
1.显式地以一个类对象作为另一个类对象的初值
2.当类对象被作为参数交给函数时
3.当函数返回一个类对象时
对于本题

fs[f] = fm;//没有调用拷贝构造函数
cs[c].insert(fm);//调用了拷贝构造函数

set调用insert语句时调用了FM类的拷贝构造函数，哈希表fs没有调用任何构造函数，只是做了关联。
四. begin()和end()
对于set而言，我们可以用begin()或rbegin()来取得排序的第一个元素和最后一个元素，但不能使用end(),因为end()指向的是最后一个元素的下一个元素，其实也就是空。

下面把使用优先队列（默认也就是大顶堆）的解法也贴出来，优先队列的自定义排序

class FM{
public:
    string food,cuisine;
    int rate;
    FM(){
        food = cuisine = "";
        rate = 0;
    }
    FM(string food,string cuisine,int rate):food(food),cuisine(cuisine),rate(rate){
        //cout<<"普通构造函数被调用了"<
        //cout<<"拷贝构造函数被调用了"<
        if (rate == other.rate)
            return food > other.food;
        return rate < other.rate;
    }
};

class FoodRatings {
    unordered_map fs;
    unordered_map> cs;
public:
    FoodRatings(vector &foods, vector &cuisines, vector &ratings) {
        for (int i = 0; i < foods.size(); ++i) {
            string f = foods[i], c = cuisines[i];
            int r = ratings[i];
            FM fm(f,c,r);
            fs[f] = fm;
            cs[c].push(fm);
        }
    }

    void changeRating(string food, int newRating) {
        string c = fs[food].cuisine;
        fs[food].rate = newRating;
        cs[c].push(fs[food]);// 直接添加新数据，后面 highestRated 再删除旧的
    }

    string highestRated(string cuisine) {
        while(true){
            string f = cs[cuisine].top().food;
            if(fs[f].rate!=cs[cuisine].top().rate) cs[cuisine].pop();
            else break;
        }
        return cs[cuisine].top().food;
    }
};

还是使用了和set方案一样的自定义类FM，因为类里面已经重载了<操作符，所以直接一行代码就能实现初始化：

priority_queue

大顶堆对应的排序规则就是<或者仿函数less<>，如果是小顶堆则时>或仿函数greater<>，大顶堆就是队头元素最大。
除了重载操作符，也可以使用仿函数来实现，不过太麻烦，还是重载操作符来的直观。