Получение дампа сегментации и потока 1: EXC_BAD_ACCESS (code = 2, address = 0x7ffeef3ffff8) при попытке выполнить быструю сортировку для вектора строк

Question

Итак, у меня есть функция, которая читает строки из файла и помещает их в вектор строк, называемый словами. У меня есть функция Quicksort, которая, по сути, сортирует весь вектор, но когда я вызываю функцию Quicksort, она выдает мне эту ошибку «Thread 1: EXC_BAD_ACCESS (code = 2, address = 0x7ffeef3ffff8)», и в Виртуальной коробке я использую Debian 9, он дает мне ошибку сегментации.

  int main()
  {
    int time[5];
    vector<string> words;
    words=ReadFromFile();
    auto start = std::chrono::system_clock::now();
         quicksort(words, 0, words.size()-1);
         auto end = std::chrono::system_clock::now();
         std::chrono::duration<double> elapsed_seconds = end-start;
         cout<<endl;
         time[2]=elapsed_seconds.count();
         cout<<" Elapsed time: " << elapsed_seconds.count() <<"\n ";
         cout<<endl;
   }

Я хочу получить время, необходимое для сортировки всех слов функцией.

 void quicksort(vector<string> words, long int from, long int to) //goes into infinite loop
   {
     if (from > to)
       {
         return;
       } 
     long int p = partition(words, from, to);
     quicksort(words, from, p);
     quicksort(words, p + 1, to);

      }

   long int partition(vector<string> words, long int from, long int to)
   {
      string pivot = words[from];
      long int i = from - 1;
      long int j = to + 1;
      while (i < j)
      {
    i++;while (words[i] > pivot){i++;}
    j--;while (words[j] < pivot){j--;}
    if (i < j){std::swap(words[i],words[j]);}
       }
     return j;
    }

Моя функция чтения из файла выглядит так:

vector<string> ReadFromFile(){
 vector<string> words;
 ifstream read;
 read.open("macbeth.txt");
 if(!read.is_open())
 {
     cout<<"Error Opening file"<<endl;
 }
 else
 {
     while(!read.eof())
     {
         string line;
         getline(read,line);
         stringstream Curstr(line);
         while(Curstr>>line)
         {
             words.push_back(line);
         }
     }
 read.close();
 }
 return words; 
}

Итак, я получаю EXE_bad_access, и рекурсия будет выполняться около 50000 раз.

@ EDIT Использование отладчик, я обнаружил, что pivot не получает значение от words[from]. Это показывает, что string pivot = "" вместо этого должно иметь значение, подобное string pivot = words[from] //MACBETH, которое является значением words[from], где from = 0, когда функция вызывается в первый раз. Теперь, как мне получить значение в сводную, чтобы он мог разделить вектор и выполнить сортировку.

Answer 1

Боже ... Не делай этого. Вы передаете вектор путем копирования при вызове этих функций. Попробуйте профилировать его и проверьте, не исчерпана ли у вас память ... (вероятно, у вас есть ...)

void f(vector<string> words){
  // here only local words are modified, the vector that you passed from caller function is NOT affected
} 

^ КОПИЯ вектора пройдена. То, что вы хотите сделать, это передать его по ссылке.

void f(vector<string> &words) {
// here you operate on original words vector
}

Попробуйте сначала исправить это и посмотреть, поможет ли это (должно быть, ma c может выбросить эту ошибку в ограничение памяти, насколько я правильно помню)

вот объяснение, как это работает

@ EDIT Попробуйте запустить его по умолчанию sort() из stl. Также проверьте, не превышаете ли вы границы вектора при вычислении i / j - добавьте некоторые утверждения к i и j: assert(0 <= i && i < words.size()), чтобы проверить правильность.

@ EDIT2 Это не похоже на Стек - это место для отладки вашего кода для вас ... Но я провел небольшое небольшое исследование некоторых крайних случаев, поэтому послушайте:

1. используйте vector<string>& words в качестве аргументов функции
2. чтение файлы не так просто, как кажется. Даже если ваш SOMEHOW работает, не используйте eof(). Здесь: .eof () l oop не работает
3. i++;while (words[i] > pivot){i++;} необходимо do{i++;}while(words[i] > pivot)
4. ^ и не работает, потому что условие никогда не выполняется встретился (первые слова [i] IS pivot), поэтому я всегда остаюсь неизменным
5. он зацикливается бесконечно для массива размера 1, например ["a"] (возвращаемый pivot всегда равен 0)
6. вы, вероятно, знаю концепцию быстрой сортировки, но ваша реализация неверна. Go отметьте https://www.geeksforgeeks.org/quick-sort/, чтобы узнать, как это сделать.
7. Не используйте long, если вы не знаете, что делаете. Либо вы хотите int или long long.
8. Это ... basi c отладка / анализ кода ... Похоже, вы не приложили никаких усилий для анализа кода. Стек - не место, где другие могут решать ваши проблемы, потому что вы слишком ленивы.
9. Go и читаете некоторые учебники по C ++, потому что у вас пока нет сильных основ.