自定义长度比较器引发std::map计数异常问题求助

问题原因 #

你写的自定义比较器只比较字符串长度，违反了std::map要求的严格弱序规则。std::map判断两个键是否等价的逻辑是：!comp(a,b) && !comp(b,a)，如果这个条件成立，map就认为a和b是同一个键。

比如插入"b"时，它和已有的"a"长度相同，comp("a","b")返回false（长度相等），comp("b","a")也返回false，map就判定这两个键等价，直接把"b"的计数加到"a"的条目上，而非创建新条目。这就是"a"计数变成6的原因——所有长度为1的字符串（a、b、c、d、e、f）都被当成同一个键统计，同理长度为2的"ab""bc""cd""de""ef"也被归为同一键，最终导致计数完全异常。

解决方法 #

有两种可行的修复方式：

方式一：修复比较器，满足严格弱序 #

当字符串长度相同时，补充字典序比较，确保不同字符串即使长度相同也会被识别为不同键：

// 修改后的比较器：长度优先，长度相同则按字典序排序
auto comp = [](const string& s1, const string& s2) {
    if (s1.length() != s2.length()) {
        return s1.length() < s2.length();
    }
    return s1 < s2; // 长度相同时用字典序区分
};
map<string, int, decltype(comp)> msi(comp);

方式二：分开统计与排序 #

先用默认的std::map或std::unordered_map完成计数（默认比较器保证键的唯一性），之后再提取键值对按长度排序：

int maximumLength(string s) {
    int n = (int)s.length();        
    unordered_map<string, int> msi; // 也可用map<string, int>
    for (auto i = 0; i < n; i++)    {
        for (auto j = 1; j < n - i + 1; j++)    {
            string tmp = s.substr(i, j);
            msi[tmp] += 1;
        }
    }
    // 将键值对转为vector，按字符串长度降序排序
    vector<pair<string, int>> vec(msi.begin(), msi.end());
    sort(vec.begin(), vec.end(), [](const auto& a, const auto& b) {
        return a.first.length() > b.first.length();
    });
    int res = -1;
    for (const auto& p : vec)  {
        cout << p.first << " " << p.second << endl;
        // if (p.second >= 3)    {
        //     res = (int)p.first.length();
        //     break;
        // }
    }
    return res;
}

原问题代码与输出 #

原代码 #

int maximumLength(string s) {
    int n = (int)s.length();        
    auto comp = [&](const string& s1, const string& s2)  { return (int)s1.length() < (int)s2.length(); };
    map<string, int, decltype(comp)> msi(comp);
    // map<string, int, LengthComparator> msi;
    for (auto i = 0; i < n; i++)    {
        for (auto j = 1; j < n - i + 1; j++)    {
            string tmp = s.substr(i, j);
            cout << tmp << endl;
            msi[tmp] += 1;
        }
        debug(msi);
    }
    int res = -1;
    for (auto it = rbegin(msi); it != rend(msi); it++)  {
        cout << it->first << " " << it->second << endl;
        // if (it->second >= 3)    {
        //     res = (int)it->first.length();
        //     break;
        // }
    }
    return res;
}

int32_t main() {
    
    string input{"abcdef"};
    cout << maximumLength(input) << endl;

    return 0;
}

原输出 #

a
ab
abc
abcd
abcde
abcdef
[msi] = {("a",1),("ab",1),("abc",1),("abcd",1),("abcde",1),("abcdef",1)}
b
bc
bcd
bcde
bcdef
[msi] = {("a",2),("ab",2),("abc",2),("abcd",2),("abcde",2),("abcdef",1)}
c
cd
cde
cdef
[msi] = {("a",3),("ab",3),("abc",3),("abcd",3),("abcde",2),("abcdef",1)}
d
de
def
[msi] = {("a",4),("ab",4),("abc",4),("abcd",3),("abcde",2),("abcdef",1)}
e
ef
[msi] = {("a",5),("ab",5),("abc",4),("abcd",3),("abcde",2),("abcdef",1)}
f
[msi] = {("a",6),("ab",5),("abc",4),("abcd",3),("abcde",2),("abcdef",1)}
abcdef 1
abcde 2
abcd 3
abc 4
ab 5
a 6
-1

内容的提问来源于stack exchange，提问作者kudos3110