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