3. speicherzugriffsfehler bei mehr als 262091 elementen in einer liste

speicherzugriffsfehler bei mehr als 262091 elementen in einer liste

  • A

    Hallo,

    volgendes:
    ich habe mir eine classe fuer eine dyn. liste geschrieben.
    diese funktioniert auch soweit ganz gut.

    wenn ich aber in einer liste mehr als 262091 elemente hab, dann kommt bei der zerstoerung (also am ende vom programm) ein Segmentation fault (=speicherzugriffsfehler).

    wenn ich eine zweite liste deffiniere, kann ich aber ohne probleme 2*262091 elemente haben.

    Die groeße der elemente in der liste ist auch ohne bedeutung (ich hab ein "int" und eine klasse mit 11 "long long" probiert, die liste arbeitet mit templates)

    kann mir das jemand erklaeren?
    (bei bedarf kann ich auch den code zur verfuegung stellen, ich glaube aber, dass das nicht noetig ist..)

    danke im voraus..

    mfg aman..

    0
  • M

    aMan schrieb:

    kann mir das jemand erklaeren?

    Nein.

    aMan schrieb:

    (bei bedarf kann ich auch den code zur verfuegung stellen, ich glaube aber, dass das nicht noetig ist..)

    doch. 😉

    0
  • A

    ok, np:

    main.cpp

    #ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <iostream>
#include <cstdlib>
#include "mylist.h"
#include "mylistelement.h"

class blub
{
	private:
		long long a, b, c, d, e, f, g, h, i, j, k;
	public:
		blub()
		{
			a=b=c=d=e=f=g=h=i=j=k=1202901209;
		}
};

using namespace std;

int main(int argc, char *argv[])
{
	cout << "Hello, world!" << endl;

	MyList<blub> liste;
	blub* bluber = new blub();
	liste.append(bluber);

	int t;
	cout << "start 1" << endl;
	cin >> t;

	for (int i=0; i<t; i++)
	{
		bluber = new blub();
		liste.append(bluber);
	}

	cout << "ende 1" << endl;
	cout << "start 2" << endl;

	cin>>t;
	MyList<int> liste2;
	int* integer = new int(3);

	for(int i=0; i<t; i++)
	{
		integer = new int(i);
		liste2.append(integer);
	}

	cout << "ende 2" << endl;
	cin >> t;

	return EXIT_SUCCESS;
}

    mylist.h

    #ifndef MYLIST_H
#define MYLIST_H

#include "mylistelement.h"

#include <iostream>
using namespace std;

/**
@author Adam Celarek
*/

template <class T>
class MyList
{
	public:
		MyList();
		~MyList();
		void append(T* element);            // element anhaengen und current_element auf first_element setzen.
		void deleteCurrentElement();        // current_element loeschen, und zum naechsten springen
		int size();                         // return list_size;
		T* next();                          // return current_element und zum naechsten springen
		T* current();                       // return current_element
		T* first();                         // returns first elem, and sets current_element to first
	private:
		MyListElement<T>* first_element;
		MyListElement<T>* current_element;
		MyListElement<T>* last_element;
		int list_size;
};

///########################################################################################///
///########################################################################################///
///########################################################################################///

///####    con/de-tructors    ####
template <class T>
MyList<T>::MyList()
{
	first_element=NULL;
	current_element=first_element;
	list_size=0;
}
template <class T>
MyList<T>::~MyList()
{
	current_element=NULL;
	last_element=NULL;
	delete first_element;
}

///####    acces    ####

/*!
    \fn MyList::append()
 */
template <class T>
void MyList<T>::append(T* element)
{
	MyListElement<T>* new_element;
	new_element = new MyListElement<T>(element);
	                                       // neues element

	// 2 faelle:
	// 1. noch keine elemente in d liste
	// 2. elemente in der liste
	if (list_size == 0)                    // fall 1 noch kein elem i d liste
	{
		first_element=new_element;
		last_element=new_element;
		current_element=new_element;
	}
	else                                   // fall 2 new_element kommt a d ende d liste
	{
		last_element->next = new_element;   // das letzte elem verlinken
		new_element->prev = last_element;   // neus letzte verlinken
		last_element = new_element;         // neues letztes das current

		current_element = first_element;    // current auf das erste setzen,
                                          // damit spaeter beim durchlaufen keine probs auftreten
	}

	list_size++;
}

/*!
    \fn MyList::deleteCurrentElement()
 */
template <class T>
void MyList<T>::deleteCurrentElement()
{
	//faelle:
	// 1. erstes elem
	// 2. in der mitte
	// 3. am ende
	MyListElement<T>* new_current;

	// 1. fall: elem am anfang
	if (current_element == first_element)
	{
		new_current = first_element->next;  // 2tes elem wird erstes
		new_current->prev = NULL;           // referenz aufs erste killen
		first_element->next = NULL;         // damit das 2. nicht mitkillt wird.
		delete first_element;               // killen
		first_element = new_current;        // neues 1. setzen
		list_size--;                        // liste wird kleiner
	}
	else if (current_element->next == NULL)
                                          // 3. fall, man ist am ende
	{
		current_element->prev->next = NULL; // zeiger vom vorletzten elem auf null setzen..
                                           // letztes element ist vorheriges,
                                           // damit neue elemente richtig verlinkt werden koennnen.
		last_element = current_element->prev;
		delete current_element;             // elem. killen
		current_element = NULL;             // neues current ist NULL, damit ein next()
                                                // null zurueckgibt => es die ganze liste nicht nochmal durchlaeuft.

		list_size--;                        // liste wird kleiner
	}
	else                                   // 2. fall, in der mitte
	{
                                          // zeiger von vorherigem elem, und naechsten aendern
		current_element->next->prev = current_element->prev;
		current_element->prev->next = current_element->next;

                                          // neues current ist das naechste elem
		new_current = current_element->next;  // edit: korrektur

		current_element->next = NULL;       // zeiger von diesem elem  nullen
		current_element->prev = NULL;

		delete current_element;
		current_element = new_current;      // altes current killen, und neues setzen
		list_size--;                        // liste wird kleiner
	}
}

/*!
    \fn MyList::first()
 */
template <class T>
T* MyList<T>::first()
{
	current_element = first_element;
	return first_element->element;
}

/*!
    \fn MyList::next()
 */
template <class T>
T* MyList<T>::next()
{
	if(current_element!=NULL)
	{
		MyListElement<T>* element_to_return;
		element_to_return = current_element;
		current_element =  current_element->next;
		return element_to_return->element;
	}
	else
	{
		current_element = first_element;
		return NULL;
	}
}

/*!
    \fn MyList::current()
 */
template <class T>
T* MyList<T>::current()
{
	if(current_element!=NULL)
		return current_element->element;
	else
		return NULL;
}

///####   properties    ####
/*!
    \fn MyList::size()
 */
template <class T>
int MyList<T>::size()
{
    return list_size;
}

#endif

    und mylistelement.h

    #ifndef MYLISTELEMENT_H
#define MYLISTELEMENT_H

// #include "mylist.h"
template <class T>
class MyList;

/**
@author Adam Celarek
*/

template <class T>
class MyListElement
{
// 	private:
	public:
		MyListElement(T* el);
		~MyListElement();

		MyListElement* next;
		MyListElement* prev;
		T* element;

		friend class MyList<T>;
};

///########################################################################################///
///########################################################################################///
///########################################################################################///

///#### con- / destructor
template <class T>
MyListElement<T>::MyListElement(T* element)
{
	this->element=element;
	this->next = NULL;
	this->prev = NULL;
}

template <class T>
MyListElement<T>::~MyListElement()
{
	delete element;
	delete next;
}

#endif

    soda..

    ps:
    ist noch nicht die final..
    ich muss noch alle funktionen testen, und alle komentare ins englische uebersetzen..
    vorerst..

    mfg aman..

    edit:
    mylist.h neufarmatiert, damit es aufm board besser ausschaut..
    aber die komentare sind immer noch nicht richtig, da aufm board ein tab 4 zeichen hat, und bei mir nur 3..

    0
  • N

    Ähm, Dein Destructor von MyListElement sieht sehr nett aus.
    Könnte es sein, dass Dir der Stack ausgeht?
    Der Stackframe dürfte 262091 Aufrufe gross sein.
    Ausserdem ist es so ziemlich gefährlich. Irgendwo ein MyListElement zerstören ohne vorher next auf NULL gesetzt zu haben, zerschiesst Dir Deine Liste (CopyConstructor, temporäre Objekte)

    0
  • A

    niemand schrieb:

    Ähm, Dein Destructor von MyListElement sieht sehr nett aus.

    meinst du das positiv, oder negativ?
    wie sollte man es denn machen? / was ist daran falsch?
    (war nicht meine idee, stand so im scriptum der uni marburg http://www.mathematik.uni-marburg.de/~cpp/pointer/listedef.html

    niemand schrieb:

    Könnte es sein, dass Dir der Stack ausgeht?
    Der Stackframe dürfte 262091 Aufrufe gross sein.

    kann sein..
    von was haengt das ab, und kann man das umgehen?
    und warum kann ich dann eine 2. liste mit nochmal 200k elementen machen?

    niemand schrieb:

    Ausserdem ist es so ziemlich gefährlich. Irgendwo ein MyListElement zerstören ohne vorher next auf NULL gesetzt zu haben, zerschiesst Dir Deine Liste (CopyConstructor, temporäre Objekte)

    das hab ich glaub ich beachtet (oder?)

    0
  • O

    die Sache mit dem destructor war negativ gemeint 😉

    Veränder den destructor deiner liste besser so, dass du zuerst das letzte element löscht, dann das vorletzte, usw, bis kein element mehr da ist. Das problem deines destructors, bzw des destructors deiner elemente ist, dass sie sich rekursiv aufrufen. Und jeder aufruf kostet etwas speicherplatz auf dem Stack. Der Stack hat aber eine Beschränkung der größe, die man zwar verändern kann, aber die trotzdem nicht so groß ist.

    oder machs dir ganz einfach, und benutz std::list<T> statt deiner Liste 😃

    0
  • N

    Definitiv negativ.

    Grundsätzlich erscheint es mir keine gute Idee Objekte zu zerstören über die ich nichts weiss. Gewöhnlich sollte ein Objekt nur die Resourcen wieder freigeben, die es besitzt.
    In Deinem Fall wäre der Besitzer wohl am ehesten MyList<T>. Also sollte die auch über alle Listenelemente iterieren und diese zerstören.
    Das Verhalten ist übrigens anders als es bei der erwähnten std::list<T> ist:
    std::list<T> erwartet keine Pointer, sondern kopierbare Objekte, während std::list<T*> Pointer erwartet, die Objekte dahinter aber nicht zerstört (beim Zerstören der Liste).

    Zum Thema Kopien:
    Du machst in Deinem Code vermutlich alles richtig, Du verhinderst aber mögliche Fehler nicht.
    Du hast keinen CopyConstructor überschrieben. Würdest Du (oder jemand anders, der Deinem Code erweitert), also beispielsweise:

    {
  MyListElemet<T> x = *first_element;
  // damit etwas machen
}

    wäre am Ende des Blocks die Liste komplett gelöscht. (x enthält Kopien auf die Zeiger von first_element, beim Verlassen des Blocks wird der Destruktor von x aufgerufen und die Liste gelöscht).
    Um das zu verhindern, kann man z.B. den CopyConstructor und Assignment Operator private machen, dann kann niemand eine solche Zeile hinschreiben.

    0
  • M

    aMan schrieb:

    niemand schrieb:

    Könnte es sein, dass Dir der Stack ausgeht?
    Der Stackframe dürfte 262091 Aufrufe gross sein.

    kann sein..
    von was haengt das ab, und kann man das umgehen?
    und warum kann ich dann eine 2. liste mit nochmal 200k elementen machen?

    Weil die Destruktoren beider Listen separat aufgerufen werden. Somit verlängert sich nicht die Rekursionskette, die du bei deinem jetzigen rekursiven Desktruktor erzeugst.

    Ich würde die Destruktion der Listenelemente rein iterativ in deiner Listenklasse durchführen. Also eine Schleife, die so lange das nächste Element löscht, bis keins mehr da ist (next NULL ist).

    0
  • A

    danke leuds, jetzt verstehe ich, was ihr meint..

    ich werde das aendern..

    gibts vielleicht eine seite, die den stack usw genauer erklaert?

    0
  • M

    hm.
    , kA, aber soviel gibts da auch nicht zu wissen...
    alle variablen, die du nicht mit new allokierst liege auf dem Stack->mit jeder variablen wird der stackpointer größer (der zeigt auf das ende, also die Spitze vom Stack), außerdem wird, wenn du eine funktion aufrufst die Rücksprungaddressefür diese funktion auf dme Stack abgelegt, und es werden auch die Parameter für die funktionen auf dem Stack abgelegt. Bei häufigem rekursiven aufruf von funktionen wird der stackpinter also immer größer und irgendwann ist kein Platz mehr auf dem Stack und du bekommst so einen schönen Ausnahmefehler 😉

    0
  • ?

    volgendes:

    Volkard - aber
    Folgendes

    0
  • A

    @maxi
    danke..

    liegt der stack denn im prozi, oder im ram?

    @rechtschreibtroll
    vogel V fehler mach ich oft..
    ich muss mich auch jedes mal ne runde schaemen..

    0
  • M

    der stack liegt m RAM, so wie der Heap auch, is nur eben "räumlich", also von der Größe auf eine ziemlich kleine Menge begrenzt

    0
  • A

    ok, thx..

    0
Anmelden zum Antworten