我不明白为什么我对字符串的排序会破坏一切

Question

我有以下代码：

#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()); // <= This line break everything

    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;
}

此代码检测给定单词列表中的所有字谜。

正如我的评论所说，当我wordSorted使用排序时std::sort，它会破坏所有内容，并且我的代码以 bad_alloc 结尾。就好像std::sort操纵了外部的记忆一样wordSorted。如果我删除此特定行，则代码“有效”（结果显然是错误的，但它做了它应该做的事情）。

怎么可能呢？我缺少什么？

Answer 1

我猜这些行是您问题的主要原因：

{
    vector<string> vec = { word };
    result.push_back(vec);
    indexes[wordSorted] = &vec;
}

这里你存储了一个指向映射中局部变量的指针。当block的生命周期结束的时候也结束了，你刚才存储的指针就会失效。vecindexes}vec

任何对该指针的使用都会导致未定义的行为。

在我看来，解决方案就是简单地不存储指向向量的指针（指向容器的指针很少需要），而是存储一个副本。