I don't understand why my sort on a string breaks everything

user_1814888 0
Viewed 48

I have the following code:

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

This code detects all anagrams in a list of given words.

As my comment says, when I sort wordSorted using std::sort, it breaks everything and my code ends with a bad_alloc. As if the std::sort manipulates the memory outside of wordSorted. If I remove this specific line, the code "works" (the result is obviously wrong, but it does what it should do).

How it is possible? What am I missing?

sorting c++ string
1 Answers

I'm guessing these lines are the main cause of your problem:

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

Here you store a pointer to the local variable vec in the indexes map. When the block ends at } the life-time of vec also ends, and the pointer you just stored will become invalid.

Any use of this pointer will lead to undefined behavior.

It seems to me that the solution is to simply not store pointers to the vector (pointers to containers are seldom, if ever, needed), and instead store a copy.

user_4405580
Related