C++ stack overflow

0

Witam mam problem ze swoim programem. Program ma wykonywać sortowanie wielu tablic dla dużych rozmiarów (max 1 milion). Dla rozmiarów mniejszych niż 100 tys. działa normalnie, natomiast dla rozmiaru rzędu 1 milion jest błąd Unhandled exception at 0x00C17329 in pa.exe: 0xC00000FD: Stack overflow (parameters: 0x00000000, 0x00B02000). Proszę o pomoc.

#include <iostream>
#include <cstdlib>
#include <time.h>
#include <vector>

using namespace std;

template<typename Typ, int Rozmiar>
class tablica
{
public:
    Typ tab[Rozmiar];  //tablica główna     
    Typ pom[Rozmiar];  //tablica pomocnicza
    void merge( int lewy, int srodek, int prawy)
    {
        for (int i = lewy; i <= prawy; i++)
            pom[i] = tab[i];

        int i = lewy, j = srodek + 1, k = lewy;

        while (i <= srodek && j <= prawy)
        {
            if (pom[i] < pom[j])
                tab[k++] = pom[i++];
            else
                tab[k++] = pom[j++];
        }
        while (i <= srodek)
            tab[k++] = pom[i++];
    }

    void mergeSort(int pocz, int kon)
    {
        int srodek;
        if (pocz < kon)
        {
            srodek = (pocz + kon) / 2;
            mergeSort(pocz, srodek);
            mergeSort(srodek + 1, kon);
            merge(pocz, srodek, kon);
        }
    }

    tablica()
    {
        for (int i = 0; i < Rozmiar; i++)
            tab[i] = rand() % 100000;
    }

};

int main()
{
    const int Rozmiar = 1000000;

    vector <tablica <int, Rozmiar >> lista;
    for (int i = 0; i < 100; i++)
    {   
        tablica <int, Rozmiar> a; 
        lista.push_back(a);
    }

    double start = clock();
    for (int i = 0; i < lista.size(); i++)
    {
        lista[i].mergeSort(0, Rozmiar - 1);
    }
        double czas = (clock() - start) / 1000;

    cout << "\n" << "Czas sortowania: " << czas << endl;

}
0

Kończy się miejsce na stosie.
Zastosuj vector wewnątrz klasy, aby pamięć była alokowania na stercie, a nie na stosie.

albo próbuj zwiększyć rozmiar stosu.

5

YooSy ma rację i nie ma racji ;​)

Zgodnie z komunikatem błędu kończy się miejsce na stosie. Jest tak ponieważ obiekt tablica staje się większy od rozmiaru stosu, zakładając 4-bajtowy int, dla Rozmiar = 10000000 jest to 10000000·4·2, czyli 80000000 bajtów (80MB).

Powodem błędu nie jest jednak std::vector, a następująca zmienna pomocnicza:

tablica <int, Rozmiar> a;

Gdy wywołanie w pętli zamienię na

    for (int i = 0; i < 100; i++)
    {
        lista.emplace_back();
    }

problem znika. Ale dla domyślnej inicjalizacji można to zrobić jeszcze prościej:

vector <tablica <int, Rozmiar >> lista(100);

PS: w C++ masz <chrono>, używaj wygodnych narzędzi do mierzenia czasu.

0

Dzięki za rady i pomoc ;)

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0