Ошибка переполнения при заполнении вектора C++

Question

Мне нужно прочитать 3 текстовых файла, заполненных целыми числами, выполнить 3 разных метода сортировки (вставка, оболочка и быстрая сортировка), а затем поместить отсортированный список в новый файл.

Мой метод для этого состоял в том, чтобы хранить целые числа в 3 векторах, выполняя один тип сортировки для каждого вектора, а затем записывая векторы в новые файлы. Я столкнулся с ошибкой переполнения стека во втором файле, пока моя программа его читает, и я начинаю пересматривать этот метод. Моя программа проходит через первый файл просто отлично (это около 10 строк), но второй файл составляет 66 КБ, а третий - еще больше (1,038 КБ).

Есть ли лучший способ обойти это или есть какой-то способ исправить ошибку переполнения?

Вот код проблема:

/* read through second file and add to vectors */ 
file2.open("data2.txt"); 
file2 >> data; 
while (!file2.eof()) 
{ 
    v1.push_back(data); 
    v2.push_back(data); 
    v3.push_back(data); 
    file2 >> data; 
} 
file2.close(); 

Вот мой полный код так далеко: (я не совсем понял, записи файлов еще так, что часть закомментирована)

#include "stdafx.h" 
#include <time.h> 
#include <stdio.h> 
#include <dos.h> 
#include <iostream> 
#include <algorithm> 
#include <utility> 
#include <fstream> 
#include <string> 
#include <vector> 
#include <iomanip> 

/* member function declarations */ 
using namespace std; 
void insertion_sort(vector<int> & v, int length); 
void shellsort(vector<int> & v, int n); 
int quickSort(vector<int> &, int start, int end); 
int partition(vector<int> &, int start, int end, int& swaps); 
void swap(int &val1, int &val2); 

int main() 
{ 
    /* file stream and clock declarations */ 
    ifstream file1, file2, file3; 
    ofstream I1, I2, I3, S1, S2, S3, Q1, Q2, Q3; 

    /* read through first file and add to vectors */ 
    file1.open("data1.txt"); 
    vector<int> v1, v2, v3; 
    int data; 
    file1 >> data; 
    while (!file1.eof()) 
    { 
     v1.push_back(data); 
     v2.push_back(data); 
     v3.push_back(data); 
     file1 >> data; 
    } 
    file1.close(); // end file reading 

    /* sort each vector using different methods */ 
    insertion_sort(v1, v1.size()); 
    shellsort(v2, v2.size()); 
    quickSort(v3, 0, v3.size() - 1); 

    // write vectors to new files 

    /* read through second file and add to vectors */ 
    file2.open("data2.txt"); 
    file2 >> data; 
    while (!file2.eof()) 
    { 
     v1.push_back(data); 
     v2.push_back(data); 
     v3.push_back(data); 
     file2 >> data; 
    } 
    file2.close(); 

    /* sort each vector using different methods */ 
    insertion_sort(v1, v1.size()); 
    shellsort(v2, v2.size()); 
    quickSort(v3, 0, v3.size() - 1); 

    // write to file 

    /* read through third file and add to vectors */ 
    file3.open("data3.txt"); 
    file3 >> data; 
    while (!file3.eof()) 
    { 
     v1.push_back(data); 
     v2.push_back(data); 
     v3.push_back(data); 
     file3 >> data; 
    } 
    file3.close(); 

    /* sort each vector using different methods */ 
    insertion_sort(v1, v1.size()); 
    shellsort(v2, v2.size()); 
    quickSort(v3, 0, v3.size() - 1); 

    // write to file 

    cout << endl; 
    system("PAUSE"); 
    return 0; 
} 

/*insertion sort*/ 
void insertion_sort(vector<int> &v, int n) { 
    int x, y, temp; 
    for (x = 1; x < n; x++) { 
    y = x; 
    while (y > 0 && v[y - 1] > v[y]) { 
     temp = v[y]; 
     v[y] = v[y - 1]; 
     v[y - 1] = temp; 
     y--; 
    }//end of while loop 
}//end of for loop 
}//end of insertion_sort. 

/* shellsort */ 
void shellsort(vector<int> & v, int n) 

{ 
int k, x, y, temp; 
for (k = n/2; k > 0; k /= 2) 
    for (x = k; x < n; x++) 
     for (y = x - k; y >= 0 && v[y]>v[y + k]; y -= k) 
     { 
      temp = v[y]; 
      v[y] = v[y + k]; 
      v[y + k] = temp; 
     } 
} 

/* quicksort function */ 
int quicksort(vector<int> & v, int s, int last) 
{ 
int swaps = 0; 
if (s < last) 
{ 
    int i = partition(v, s, last, swaps); 
    swaps += quicksort(v, s, i - 1); 
    swaps += quicksort(v, i + 1, last); 
} 
return swaps; 
} 

/* partition function for quicksorting */ 
int partition(vector<int> & v, int start, int end, int& swaps) 
{ 
int pivot = v[end]; 
int index= start; 

for (int i = start; i < end; i++) 
{ 
    if (v[i] <= pivot) 
    { 

     if (index != i) 
     { 
      std::swap(v[i], v[index]); 
      swaps++; 
     } 
     index++; 
    } 
} 
if (index != end) 
{ 
    std::swap(v[index], v[end]); 
    swaps++; 
} 
return index; 
} 

Answer 1

Хорошо, поэтому я предполагаю, что это домашнее задание; поэтому, вот попытка привести вас к ответу, не давая его вам.

Обратите внимание, что стек используется для хранения локальных переменных. При вызове новой функции необходимо выделить дополнительные переменные (пространство стека). Если функция вызывает себя (называемую рекурсией), которая может привести к быстрому росту стека (и вызвать переполнение стека).

Ищите любые функции, которые вызывают себя. Насколько глубоко может возникнуть вложенность (звонки внутри звонков)? Ваша информация об отладке может помочь вам в этом или просто подумать о том, как работает код. Также посмотрите, сколько переменных требуется вашей функции (которые должны быть выделены в стеке). Умножьте эти два (глубину вызова и локальную память), и вы поймете, сколько стека вам понадобится.

Поскольку вы говорите, что проблема увеличивается с размером файла, посмотрите, как размер файла влияет на код. Это влияет на глубину вызова или объем используемой памяти?

Как только вы знаете причину, вы можете перейти к решению.