c++ - 运行时错误:基数为0x000000000000的指针索引表达式溢出到0xffffffffffffffff以进行频率排序

问题是要按照给定字符串的字母的频率降序对它们进行排序。

例如:如果string =“tree”输出=“eert”或“eetr”
我使用了unordered_map并计算了每个字母的频率，并将其以频率降序添加到结果字符串中。

这是我尝试过的:

string frequencySort(string s1) {
    unordered_map<char,int> temp;
    for(char& c: s1)
        temp[c]++;
    string s = "";
    while(!temp.empty()) {
        int max = 0;
        char c='a';
        for(auto it:temp) {
            if(it.second > max) {
                c = it.first;
                max = it.second;
            }
        }
        for(int j=0;j<max;j++)
            s = s + c;
        temp.erase(temp.find(c));
    }
    return s;
}

我的代码不适用于大量输入。而将int更改为long long并不能使其工作。因此，最大频率在INT_MAX以内。我收到此错误:

Runtime error: pointer index expression with base 0x000000000000 overflowed to 0xffffffffffffffff

我无法在此处粘贴特定的测试用例，因为它超出了问题允许的大小。

任何帮助表示赞赏。

最佳答案

代码在逻辑上没有错，但是许多低效率的操作可能会使您在低内存计算机上耗尽内存。

首先，您按值传递字符串:



这样，每次调用都会产生一个新的字符串副本，浪费的内存是必要的两倍。

相反，请选择:

string frequencySort(const string & s1) {

字符串所需的重复重新分配可能导致内存管理器中出现碎片，并导致更快的内存不足问题:



为了最大程度地减少重新分配问题，请使用reserve

string s = "";
s.reserve(s1.length());

以及最大的性能问题:



上面的代码一次又一次地复制相同的字符串。在O(N2)中运行，并在堆上破坏巨大的碎片。

代码中还有一些简单的效率低下的问题，尽管它们不会影响复杂性，但它们可能会对大型输入的运行时产生重大影响。在如此小的集合(26个英文字母)中使用unordered_map会花费大量时间。在这种情况下，使用std::map可能会更有效。对于大输入，保存数组更有效

int map[256] = {0};

不幸的是，对于少量输入，它可能会更慢。同样，这对于宽字符(超过216个可能的宽字符)也不是很好。但是对于ASCII，这应该可以很好地工作。

作为基准，我运行了以下命令生成的字符串:

 perl -e 'print "abcdefghijklmnopqrstuvwxyza" x 1000000; print "y\n"'

生成一个大小为2600万个字符的字符串。
在我的笔记本电脑上，带有int map[256]的代码在不到4秒的时间内完成了。

关于c++ - 运行时错误:基数为0x000000000000的指针索引表达式溢出到0xffffffffffffffff以进行频率排序，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/55259287/