C++自定义排序的比较函数：自定义Cmp结构体并重载()，可持有额外信息

摘要: C++ 自定义比较函数，持有额外信息

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本文我们以 leetcode 的一道题为例，看一下 C++ 中需要持有额外信息的自定义比较函数的写法。

题目

力扣791. 自定义字符串排序

字符串 S 和 T 只包含小写字符。在S中，所有字符只会出现一次。

S 已经根据某种规则进行了排序。我们要根据 S 中的字符顺序对 T 进行排序。更具体地说，如果 S 中 x 在 y 之前出现，那么返回的字符串中 x 也应出现在 y 之前。

返回任意一种符合条件的字符串 T。

提示：

S的最大长度为26，其中没有重复的字符。
T的最大长度为200。
S和T只包含小写字符。

样例1
输入:
S = “cba”
T = “abcd”
输出: “cbad”
解释:
S中出现了字符 “a”, “b”, “c”, 所以 “a”, “b”, “c” 的顺序应该是 “c”, “b”, “a”.
由于 “d” 没有在S中出现, 它可以放在T的任意位置. “dcba”, “cdba”, “cbda” 都是合法的输出。

算法：排序

S 串只含字母 a-z(最长26)，我们要找到的是这26个字母的大小关系。26个字母的大小关系可以通过权重表示，权重越小，该字母在字符串排序后的位置约靠前。而 S 串通过字母的位置告诉了我们一些字母的权重，即：把出现过的字母在S中的下标视为该字母的权重。所以可以用一个长度 26 的 vector 保存 26 个字母的权重，值初始化为 -1，遍历 S，对 S 中的每一个字母将其下标赋值给 vector 的相应位置，这样就得到了从 S 串可以得到的部分字母的权重，权重关系就对应了字母的大小关系。

代码 (C++)

C++ 中通过给 sort 函数传入自定义的比较函数，可以实现自定义的排序。但是这里的排序需要查遍历 S 串得到的 vector，常用的直接写比较函数的方法不好实现。

还有一种方法是写一个结构体，结构体内部可以持有一个 vector 成员变量，通过初始化的方式将遍历 S 串得到的 vector 传给结构体的对象。重载该结构体的 ()，该结构体创建的对象可以当做函数使用，且内部已经持有了遍历 S 得到的 vector。

这种在结构体中重载()思想在《STL源码剖析》中也有明确的描述：

class Solution {
public:
    string customSortString(string S, string T) {
        int n = S.size();
        if(n <= 1) return T;
        vector<int> char_idx(26, -1);
        for(int i = 0; i < n; ++i)
            char_idx[S[i] - 'a'] = i;
        Dictionary_less dictionary_less(char_idx);
        sort(T.begin(), T.end(), dictionary_less);
        return T;
    }

private:
    struct Dictionary_less
    {
        vector<int> char_idx;
        Dictionary_less(vector<int> mapping):char_idx(mapping) {}
        bool operator() (const char& c1, const char& c2)
        {
            return char_idx[c1 - 'a'] < char_idx[c2 - 'a'];
        }
    };
};

---