使用std::sort排序字符串后C++字谜检测代码触发bad_alloc错误求解析

你的C++代码用于检测字谜，但执行std::sort时触发bad_alloc崩溃，核心问题不是std::sort本身，而是代码中存在悬垂指针导致的未定义行为，sort只是让内存非法访问的问题更早暴露出来。

原代码 #

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

vector<vector<string>> findAnagrams(vector<string> wordlist) {
  vector<vector<string>> result;
  unordered_map<string, vector<string>*> indexes;

  for (const string& word : wordlist) {
    string wordSorted = word;
    sort(wordSorted.begin(), wordSorted.end()); // <= 此行触发崩溃

    auto index = indexes.find(wordSorted);
    if (index == indexes.end()) {
      vector<string> vec = { word };
      result.push_back(vec);
      indexes[wordSorted] = &vec;
    } else {
      index->second->push_back(word);
    }
  }

  return result;
}

int main()
{
    vector<string> wordlist = {"eat", "tea", "tan", "ate", "nat", "bat", "test", "estt"};
    auto result = findAnagrams(wordlist);

    for (const auto& vec : result) {
      for (const auto& word : vec) {
        cout << word << " ";
      }
      cout << endl;
    }

    return 0;
}

崩溃原因分析 #

在if (index == indexes.end())分支中，你创建了栈上的局部变量vector<string> vec，然后将&vec（该局部vector的地址）存入indexes字典。但局部变量的生命周期仅限于当前代码块，当if块执行结束后，vec会被立即销毁，对应的内存会被系统回收。

此时indexes中存储的指针就变成了悬垂指针（指向已释放的无效内存）。后续当其他单词匹配到同一个wordSorted键时，通过这个悬垂指针调用push_back，属于非法访问已释放内存，触发未定义行为——有时可能看似“正常”，有时直接崩溃，而std::sort的执行改变了内存布局，让这个非法访问更快触发bad_alloc或直接崩溃。

修复后的代码 #

方案一：让指针指向result中管理的有效vector

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

vector<vector<string>> findAnagrams(vector<string> wordlist) {
  vector<vector<string>> result;
  unordered_map<string, vector<string>*> indexes;

  for (const string& word : wordlist) {
    string wordSorted = word;
    sort(wordSorted.begin(), wordSorted.end());

    auto index = indexes.find(wordSorted);
    if (index == indexes.end()) {
      // 直接在result中构造vector，生命周期由result管理
      result.emplace_back(vector<string>{word});
      // 存储result中最后一个元素的有效地址
      indexes[wordSorted] = &result.back();
    } else {
      index->second->push_back(word);
    }
  }

  return result;
}

int main()
{
    vector<string> wordlist = {"eat", "tea", "tan", "ate", "nat", "bat", "test", "estt"};
    auto result = findAnagrams(wordlist);

    for (const auto& vec : result) {
      for (const auto& word : vec) {
        cout << word << " ";
      }
      cout << endl;
    }

    return 0;
}

方案二：用map直接存储vector，避免指针操作

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

vector<vector<string>> findAnagrams(vector<string> wordlist) {
  vector<vector<string>> result;
  unordered_map<string, vector<string>> indexes;

  for (const string& word : wordlist) {
    string wordSorted = word;
    sort(wordSorted.begin(), wordSorted.end());
    indexes[wordSorted].push_back(word);
  }

  // 将map中的所有vector转移到result中
  for (auto& pair : indexes) {
    result.push_back(move(pair.second));
  }

  return result;
}

int main()
{
    vector<string> wordlist = {"eat", "tea", "tan", "ate", "nat", "bat", "test", "estt"};
    auto result = findAnagrams(wordlist);

    for (const auto& vec : result) {
      for (const auto& word : vec) {
        cout << word << " ";
      }
      cout << endl;
    }

    return 0;
}

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