Memory Management for List

[Swiftle]

I've made a Circular List and I need help implementing a simple memory management. It's the first time I'm doing this so I really have no idea where to start. What I want to do is pre-allocate X amount of Nodes that I can use for my list. Only when the stock of Nodes is depleted, I will allocated new ones. My list has roughly the following structure:

class List
{
   class Elem
   {
      int info;
      Elem *next;
      static Elem* freeElems;
   };
public:
   class Node
   {
   private:
      Elem *elem;
   };
   static void init();
};

What I want to do is create 10 Elem's in the init() function which will be used throughout the List. When I've used all the available Elem's I will allocate new ones. In the mean time when I need to add a Node/Elem to my List I would first take an Elem from the preallocated ones. What I'm thinking is to allocate 10 elements int void init() and use them for my list, but then I also have to overload the new operator so it would use an existing Elem instead of of creating a new one. So far I got this:

void List::init(){
	Elem::freeElems = new Elem(0,NULL);
	for(int i = 0; i < 10; i ++)
		Elem::freeElems->next = new Elem(0,Elem::freeElems->next);
}

Now if someone can tell me how to overload new to use these Elem's instead of allocating, and if this is the right way to do it in the first place.

[Banfa]

Have you heard of the placement new syntax? Placement new constructs a new object without allocating memory for it. You have to provide the buffer yourself.

char *buf = <allocate data in you onw method>;

Elem* normal = new Elem(0 NULL); // Normal new call allocates data from heap
Elem* placement = new (buf) Elem(0 NULL); // Placement new call uses data pointed to by buf to construct Elem in

However I would use a separate class to handle the memory allocation (you could make it a template if you need to handle many different types).

The public interface would include allocate and free methods.

The advantage of this is that you encapsulate your allocation code from your functional code. The initial implementation of your allocator can use new and delete for simplicity and to get everything working. You can then replace that with whatever algorithm you want at a later time, including having a pre-allocated list of available entries and allocating more when you run out.

[Swiftle]

Nope I've never heard of the placement. As I said I just started overloading operators and for the most part I'm clueless. So, for the if I must create a separate class that handles the allocation, it would be something like this?

class List
{
   class Elem
   {
      class Alloc
      {
         static Elem *freeElems;
      }
   //rest of the code;
}

So if I allocate 10 Elem's and then want to add a Node/Elem to my list, it will look like this?

List.head() = new (freeElems) Elem(0, NULL);

;

But what happens when I have 10 chained preallocated Elem's? How to handle which freeElems are already used and which aren't?

[Narue]

Oddly enough, I posted a very basic memory pool just the other day that does exactly what you're trying to accomplish. You might find it helpful.

[nbaztec]

Why dont you try adding to your list(class) 2 components:

unsigned int maxItems;
unsigned int currItems;

And everytime you add items increment currItems, and if it nears maxItems(=10) you increment maxItems(allocate space) to 20.

[Swiftle]

Thanks Narue, I'm having a bit of trouble understanding the code=/ I found something in my slides: a canvas for memory management class:

class reserve {
        public:
            static void constructReserve(int);
            static void destructReserve();
            static bool empty();
            static Elem* get();
            static void add(void *);
            static void printReserve();
            static Elem* headReserve;
        };

I managed to get some of the definitions but I'm still missing 2-3 of them. Here's what I have so far:

void List::Elem::reserve::constructReserve(int j) {
    if (j != 0) {
        Elem* tmp = (Elem *) malloc(sizeof (Elem));
        teteReserve = tmp;
        for (int i = 0; i < j; i++) {
            tmp->suiv = (Elem *) malloc(sizeof (Elem));
            tmp = tmp->suiv;
        }
        tmp = NULL;
    }
}

void List::Elem::reserve::detructReserve(){
	Elem* tmp;
	for(Elem *p = teteReserve; p != NULL; ){
		tmp = p->suiv;
		void free(void *p);
		p = tmp;
	}	
	void free(void *tmp);
}

bool List::Elem::reserve::empty(){
	return (headReserve == NULL);
}

I'm not sure if the last one is correct. I'm also having trouble figuring the code for add(void *p) and get(). I'm thinking about something like this:

retrieving an element from the reserve:

List::Elem* List::Elem::reserve::get(){
	Elem *p = headReserve;
	headReserve = headReserve->next;
	return p;	
}

placing an element in the reserve:

void List::Elem::reserve::add(void *p){
	Elem *tmp = headReserve->next;
	headReserve = (Elem *) malloc(sizeof (p));
	headReserve->next = tmp;
}

This is how I think it should look. Tell me if somethings wrong.

[nbaztec]

IMO you're using more than the required class.
You need the main Elem class and the List class to Wrap it.
This should make more sense.

List Obj;
Obj.Add(3);

// Definition for Add
void List:: Add(int Val)
{
Elem *temp = new Elem;
temp->val=Val;
temp->next=first->next; //first can be any list element
first->next=temp;
}

void List::Destroy()
{
Elem *actual = first;
Elem *temp = first->next;
//Delete every Node except first Node
while(actual!=temp)
{
   first=first->next;
   delete temp;
   temp = first;
}
//Delete even the first Node;
delete temp;
}

This way you don't need to worry about reserve.

[Swiftle]

I know but my assignment says otherwise :P Which means I have to implement the memory management.

Ok, when I compile my main.cpp and List.cpp I get undefined references for Elem* headReserve, I guess it has something to do with the fact that it's declared as static. I tried adding List::Elem::reserve:: but I still get an undefined ref =/

[nbaztec]

I know but my assignment says otherwise Which means I have to implement the memory management.

You can try with a simpler Stack/Queue or the Ancestor of all - Linked List. And my above example also exhibits Memory management. Memory is allocated only in Add() and can be free-ed in Destroy() or even Removed:

Obj.Remove(Elem *thisElem)
{
Elem *temp2 = NULL;
Elem *temp = first;
//Loop to find Node
while(temp!=thisElem)
{
   temp2=temp;
   temp=temp->next;
}
temp2->next=thisElem->next;
delete thisElem;
}

Ok, when I compile my main.cpp and List.cpp I get undefined references for Elem* headReserve, I guess it has something to do with the fact that it's declared as static. I tried adding List::Elem::reserve:: but I still get an undefined ref =/

Don't declare functions as static, this is pure madness. A function defined static isn't available to this pointer of a class.
Ex:

class foo
{
public:
  static void func1();
  void func2();
}Obj;

Obj.func2(); //All Fine
Obj.func1(); //Error

/* Static funcs can be used as follows */
foo.func1(); //Now it's fine

[Swiftle]

I think the problem comes from the static member Elem *headReserve and not from the static functions.

EDIT: declaring List:Elem *List::Elem::reserve::headReserve solved the problem.

[Banfa]

Looking at the slide code you found I have these comments

class reserve {
        public:
            static void constructReserve(int);
            static void destructReserve();
            static bool empty();
            static Elem* get();
            static void add(void *);
            static void printReserve();
            static Elem* headReserve;
        };

• It's all static (as someone else mentioned) while you could do it that way it doesn't lend itself to reuse. If you really only want on of them then use the single design pattern (which you can Google).
• 
  
• empty and printReserve are utilities and not part of the main function of the class.
• get is the equivalent of new but doesn't do a full job, when you call new you can provide the parameter with which to construct the object. Get provides no way to do this. If returning an object what has been constructed using the default constructor is fine then get can work but given that you might be re-using blocks get wil then have to make sure it initialises every block it returns.
• add is the equivalent of delete but takes the wrong pointer type. Most of the time void * should be unnecessary in C++.
• headReserve is public, this is a disaster, letting code outside the class have access to the internal management data removes most of the point of having a class to do this which is encapsulation of the functionality.

I would use a class with a public interface something like this (with no utility frills added)

class reserve {
public:
    explicit reserve(int size = 10);  // Construct the data reserve with a hint on the initial size to use
    void ~reserve();      // Destruct the reserve release all allocated memory
    Elem* get();          // Return a pointer to a new Elem object
    void dispose(Elem *); // Dispose of an Elem object back to the reserve
};

Like I said this could be made into a template but you sound like you may not be ready for that.

You can then declare one in your list class as reserve elemReserve; That public interface will need private data and possibly methods added to implement the memory manager but as long as you keep the interface constant you can change the manager code without having to alter the code that uses it.

Internally the class needs 2 lists, 1 list of all allocated Elems and 1 list of available Elems, that is Elems that have been allocated but are not currently in use. The pseudo code for get would look something like

reserve::get()
{
    IF THE AVAILABLE LIST IS EMPTY
        ALLOCATE MORE ELEMS
        ADD NEW ELEMS TO AVAILABLE LIST
        ADD NEW ELEMS TO ALL ELEMS LIST
    ENDIF

    IF THE AVAILABLE LIST IS EMPTY
       RETURN NULL // Let calling code handle out of memory failure
    ELSE
       GET FIRST ELEM FROM AVAILABLE LIST
       RETURN ELEM
    ENDIF
}

I don't claim this pseudo code does all the require error checking / catching but what it does do is allow the calling code to just call get without worrying about how get finds the memory for it to use.

dispose would look something like

reserve::dispose(Elem* elem)
{
    IF elem IS IN ALL ELEMS LIST    // Check it's one this class allocted
       ADD elem TO AVAILABLE LIST
    ENDIF
}

The constructor would allocate the initial number of Elems for the reserve class to hold and the destructor would delete all the Elems on the ALL ELEMS LIST.

[nbaztec]

@Swiftle
Still don't get it why are you going for this approach instead of a simpler one. In future if you ever needed to inherit this class List, it's gonna create hell lotta problems and the individual List Items wont have any methods to themselves.
static functions are reserved for something very specific, say deleting the very instance of List Object (though it can still be avoided here).

[Swiftle]

I'm still looking for the right way to implement reserve::add() with my current code I get a Seg Fault

void MultiEns::Elem::reserve::add(void *p){
	Elem *tmp = teteReserve->suiv;
	teteReserve->suiv = (Elem *) malloc(sizeof (p));
	teteReserve->suiv->suiv = tmp;
}

[Swiftle]

@nbaztec

I'm doing this because it's what they asked us to do. The whole point of the memory management was to do some exercises on overloading new and delete, that's the whole point of reserve class. I'm not saying it's a good thing to do but that's what I'm supposed to do. Also, I have almost 0 experience with this kind of stuff, for example all I know is that the reserve is supposed to be common for the whole List, that's why all the functions are static. Again this probably isn't the smartest thing to do but I don't have the time to go back and think on a different solution. The only thing left for me to do is to get add(void *p) right. Currently

Elem *tmp = headReserve->suiv

gives a Seg Fault

Elem *tmp = headReservr

however works right... Is this caused by headReserve being static?

@Bafta

get() only returns Elems from the reserve, which is created at the start of my program.

[nbaztec]

What is this suiv?

Elem *tmp = headReserve->suiv

I'm kinda lost your entire class structure.

[Swiftle]

What is this suiv?

Elem *tmp = headReserve->suiv

I'm kinda lost your entire class structure.

I'm sorry it's next. Forgot to translate ^^

Elem *tmp = headReserve->next

As for my structure...(I think I lost track too ...)

At the core we have an Element or Elem which contains some kind of information and points to another Elem. Each element is encapsulated in a Node. This is for convenience only. And finally a bunch of nodes create a List. Now the sole purpose of the class reserve is to maintain a bunch of preallocated Elems. These elements are preallocated at the begging of the program, thus the static. Now I know it's not the best way to do it but I don't have the time to go back and change the entire structure especially when I'm only a function away from being done. So even if there's a way to make it better don't bother :P

[Banfa]

I'm still looking for the right way to implement reserve::add() with my current code I get a Seg Fault

void MultiEns::Elem::reserve::add(void *p){
	Elem *tmp = teteReserve->suiv;
	teteReserve->suiv = (Elem *) malloc(sizeof (p));
	teteReserve->suiv->suiv = tmp;
}

This is C++ generally don't use malloc use new.

Line 3 malloc(sizeof (p));

What is p? A void pointer.
How big is p? Depends on your system but probably 32bit system 4 bytes 64 bit system 8 bytes.
You cast the return to Elem *, how big is Elem? Probably 8 with next in the last 4 bytes.

On a 32 bit system you allocate 4 bytes on line 3 and on line 4 write to the 4 bytes following it.

New would solve the problem because it is type safe, that is a very important feature of C++ over C which is why it is best to do things the C++ way. teteReserve->suiv = new Elem; Also the whole use of teteReserve->suiv in this function suggests that you actual head pointer is teteReserve->suiv, that is you have allocated a Elem node to hold the head pointer in suiv . Except that I do not see anywhere where you do actually allocate an Elem and assign it to teteReserve.

Personally I don't like this Using a node as the head pointer technique though I see a lot of people doing it to me it confuses the meaning of the head pointer.

[nbaztec]

I'm sorry it's next. Forgot to translate ^^

Elem *tmp = headReserve->next

As for my structure...(I think I lost track too ...)

At the core we have an Element or Elem which contains some kind of information and points to another Elem. Each element is encapsulated in a Node. This is for convenience only. And finally a bunch of nodes create a List. Now the sole purpose of the class reserve is to maintain a bunch of preallocated Elems. These elements are preallocated at the begging of the program, thus the static. Now I know it's not the best way to do it but I don't have the time to go back and change the entire structure especially when I'm only a function away from being done. So even if there's a way to make it better don't bother :P

If you don't mind showing me your code I'd be happy to help you. And don't worry about the translations, I'm used to seeing some atrocious code where axlrystrdanthrvar symbolized some auxiliary stored another variable :P

Just post back your code and the erroneous function.

[Swiftle]

Back again :o Anyway this solved my problem:

Elem* e = (Elem *) p;
    e->next = teteReserve;
    teteReserve = e;

Here's the full thing (it's mostly in french)

Main.cpp

#include <iostream>
#include "MultiEns.h"

using namespace std;

int main(){
	MultiEns M, A, B;
	MultiEns::init();
	
	M += 5;
	M += 5;
	M += 2;
	M += 6;
	M += 5;
	B += 5;
	
	A = M + B;
	M = A;
	
	cout<<M<<endl;
}

MultiEns.cpp

#include <math.h>
#include <iostream> 
#include "MultiEns.h"

using namespace std;

MultiEns::Elem *MultiEns::Elem::reserve::teteReserve;

MultiEns::Elem::Elem(int nombre, int reps, Elem *suiv) 
{
  this->nombre = nombre;
  this->reps = reps;
  this->suiv = suiv;
}


void* MultiEns::Elem::operator new(size_t size)
{
	void * p ;
	if(! reserve::estVide()) {
		p = reserve::get() ;
	} else {
		p = malloc(size) ;
	}
	return p;
}

void MultiEns::Elem::operator delete(void * p)
{
	reserve::add(p);
}


MultiEns::Place MultiEns::Place::suivant() const
{
	return Place(elem->suiv);
}

int MultiEns::Place::nombre() const
{
	return elem->nombre;
}

int MultiEns::Place::reps() const
{
	return elem->reps;
}

bool MultiEns::Place::valide() const
{
	return (elem->reps != -1);
}

MultiEns::Place::Place()
{
	this->elem = NULL;
}

MultiEns::Place::Place(Elem *elem)
{
	this->elem = elem;
}

MultiEns::Place MultiEns::tete() const
{
	return Place(tetePtr);
}

int MultiEns::longueur() const
{
  int res = 0;
  for (Place p = tete(); p.valide(); p = p.suivant())
    ++res;
  return res;
}

int MultiEns::max() const 
{
	int max = 0;
	for(Place p = tete(); p.valide(); p = p.suivant()){
		if(p.nombre() > max)
				max = p.nombre();
	}
	return max;			
}

int MultiEns::min() const 
{
	int min = 0;
	for(Place p = tete(); p.valide(); p = p.suivant()){
		if(p.nombre() < min)
				min = p.nombre();
	}
	return min;			
}

bool MultiEns::estVide() const
{
  return (tete().suivant().reps() == -1);
}

void MultiEns::init(){
	Elem::reserve::construireReserve(10);
}



void MultiEns::Elem::reserve::construireReserve(int j) {
    if (j != 0) {
        Elem* tmp = (Elem *) malloc(sizeof (Elem));
        teteReserve = tmp;
        for (int i = 0; i < j; i++) {
            tmp->suiv = (Elem *) malloc(sizeof (Elem));
            tmp = tmp->suiv;
        }
        tmp = NULL;
    }
}

void MultiEns::Elem::reserve::add(void *p){
    Elem* e = (Elem *) p;
    e->suiv = teteReserve;
    teteReserve = e;
}

void MultiEns::Elem::reserve::detruireReserve(){
	Elem* tmp;
	for(Elem *p = reserve::teteReserve; p != NULL; ){
		tmp = p->suiv;
		void free(void *p);
		p = tmp;
	}	
	void free(void *tmp);
}

int MultiEns::Elem::reserve::taille(){
	int res = 0;
	for(Elem *i = teteReserve; i != NULL; i = i->suiv)
		res++;
	return res;
}

bool MultiEns::Elem::reserve::estVide(){
	return (reserve::teteReserve == NULL);
}

MultiEns::Elem* MultiEns::Elem::reserve::get(){
	Elem *p = teteReserve;
	teteReserve = teteReserve->suiv;
	return p;	
}

void MultiEns::supprimer(Place p)
{
	Elem *i = p.elem, *j = p.elem->suiv;
	tetePtr->suiv = j;
	delete i;
}

MultiEns::Place MultiEns::trouver(int i) const
{
	Place p;
	for (p = tete().suivant(); p.reps() != -1 && p.nombre() != i; p = p.suivant())
		;
	return p;
}
////////////////////Union////////////////////
MultiEns& MultiEns::operator+=(const MultiEns &M){
	Place p, temp;
	if(tetePtr->suiv->reps == -1)
		copier(M.tete().suivant());
	else {	
		for(p = M.tete().suivant(); p.valide(); p = p.suivant())
		{
			temp = trouver(p.nombre());
			//l'element est present dans l'ensemble
			if(temp.valide())
				temp.elem->reps += p.reps();
			//l'element n'est pas present
			else {
				Place i;
				if(tetePtr->suiv->nombre > p.nombre())
					tetePtr->suiv = new Elem(p.nombre(), 1, tetePtr->suiv);
				else {
					for(i = tete().suivant(); i.valide() && p.nombre() > i.suivant().nombre(); i = i.suivant())
						;
					i.elem->suiv = new Elem(p.nombre(), p.reps(), i.elem->suiv);
				}
			}
		}
	}
	return *this;
}

MultiEns& MultiEns::operator+=(const int e){
	//l'ensemble est vide
	if(tete().suivant().reps() == -1){
		tetePtr->suiv = new Elem(e, 1, tetePtr);		
	}	
	else {
		Place temp = trouver(e);
		//l'element est deja present
		if(temp.valide()) 
			temp.elem->reps++;
		//l'element n'est pas present
		else {
			if(tetePtr->suiv->nombre > e)
				tetePtr->suiv = new Elem(e, 1, tetePtr->suiv);
			else {
				for(temp = tete().suivant(); temp.suivant().valide() && e > temp.nombre(); temp = temp.suivant())
					;
				temp.elem->suiv = new Elem(e, 1 , temp.elem->suiv);
			}
		}
	}
	return *this;
}

////////////////////Intersection////////////////////
MultiEns& MultiEns::operator*=(const MultiEns &M){
	Place p, temp;
	for(p = tete().suivant(); p.valide(); p = p.suivant())
	{
		temp = M.trouver(p.nombre());
		if(temp.valide()){
			if(p.elem->reps > temp.elem->reps)
				p.elem->reps = temp.elem->reps;
		}
		else
			supprimer(p);
	}
	return *this;
}

MultiEns& MultiEns::operator*=(const int e){
	Place p = tete().suivant();
	if(trouver(e).valide()){
		p.elem->nombre = e;
		p.elem->reps = 1;
		p.elem->suiv = tetePtr;
	}
	else
		cerr<<"Il n'existe pas d'intersection";
	return *this;
}

////////////////////Difference////////////////////
MultiEns& MultiEns::operator-=(const MultiEns &M){
	Place p, temp;
	for(p = tete().suivant(); p.valide(); p = p.suivant())
	{
		
		temp = M.trouver(p.nombre());
		if(temp.valide())
			p.elem->reps = fabs(p.reps() - temp.reps());
		else
			supprimer(p);
	}
	return *this;
}

MultiEns& MultiEns::operator-=(const int e){
	Place p = tete().suivant();
	if(trouver(e).valide()){
		p.elem->reps = trouver(e).elem->reps - 1;
		p.elem->nombre = e;
		p.elem->suiv = tetePtr;
	}
	else
		cerr<<"Il n'existe pas de difference";
	return *this;
}

//////////////////Autres Operateurs/////////////////
MultiEns operator+(int e, const MultiEns &M){
	MultiEns Ens;
	Ens += M;
	Ens += e;	
	return Ens;
}

MultiEns operator-(int e, const MultiEns &M){
	MultiEns Ens;
	Ens += M;
	Ens -= e;	
	return Ens;
}

MultiEns operator*(int e, const MultiEns &M){
	MultiEns Ens;
	Ens += M;
	Ens *= e;	
	return Ens;
}

MultiEns operator+(const MultiEns &M1, const MultiEns &M2){
	MultiEns Ens;
	Ens += M1;
	Ens += M2;	
	return Ens;
}

MultiEns operator-(const MultiEns &M1, const MultiEns &M2){
	MultiEns Ens;
	Ens += M1;
	Ens -= M2;	
	return Ens;
}

MultiEns operator*(const MultiEns &M1, const MultiEns &M2){
	MultiEns Ens;
	Ens += M1;
	Ens *= M2;	
	return Ens;
}

MultiEns& MultiEns::operator=(const MultiEns &M){
	if(&M != this){
		effacer();
		copier(M.tete().suivant());
	}
	return *this;
}

bool MultiEns::operator==(const MultiEns &M) const{
	bool egaux = true;
	if(longueur() == M.longueur()){
		Place p1, p2;
		for(p1 = tete().suivant(), p2 = M.tete().suivant(); p1.valide() && p2.valide(); p1 = p1.suivant(), p2 = p2.suivant()){
			if(p1.nombre() != p2.nombre() or p1.reps() != p2.reps())
				egaux = false;
		}
	}
	else
		egaux = false;
	return egaux;	
}

bool MultiEns::operator!=(const MultiEns &M) const{
	return !(*this == M);
}

bool MultiEns::operator<=(const MultiEns &M) const{
	bool inclus = true;
	if(longueur() >= M.longueur()){
		Place p, temp;
		for(p = M.tete(); p.valide(); p = p.suivant()){
			temp = trouver(p.nombre());
			if(temp.valide()){
				if(temp.reps() < p.reps())
					inclus = false;	
			}		
		}	
	}
	else
		inclus = false;
	return inclus;	
}

bool MultiEns::operator>=(const MultiEns &M) const{
	bool inclus = true;
	if(longueur() <= M.longueur()){
		Place p, temp;
		for(p = tete(); p.valide(); p = p.suivant()){
			temp = M.trouver(p.nombre());
			if(temp.valide()){
				if(temp.reps() < p.reps())
					inclus = false;	
			}		
		}	
	}
	else
		inclus = false;
	return inclus;	
}

bool MultiEns::operator<(const MultiEns &M) const{
	return(*this >= M && *this != M);
}

bool MultiEns::operator>(const MultiEns &M) const{
	return(*this <= M && *this != M);
}

int MultiEns::operator()(int e) const{
	return trouver(e).reps();
}

ostream &operator<<(ostream &out, const MultiEns &M){
	MultiEns::Place p;
	if(M.tete().suivant().valide()){
		out << "{" ;
		for(p = M.tete().suivant(); p.valide(); p = p.suivant()){
			if(p.reps() > 0)
				out << p.nombre() << ":" << p.reps();
			if(p.suivant().valide())
				out << ",";	
		}
		out << "}";
	}
	return out;
}



MultiEns::MultiEns()
{
	tetePtr = new Elem(99, -1 , NULL);
	tetePtr->suiv = tetePtr;
}

MultiEns::~MultiEns()
{
	effacer();
}

void MultiEns::effacer()
{
	while (!estVide()) 
		supprimer(tete().suivant());

}

MultiEns::Place MultiEns::insererEnTete(int i,int j)
{
	tetePtr->suiv = new Elem(i, j, tetePtr->suiv);
 	return tete();
}

MultiEns::Place MultiEns::insererApres(Place p, int i, int j)
{
	p.elem->suiv = new Elem(i, j, p.elem->suiv);
	return p.suivant();
}

void MultiEns::copier(Place p)
{
	if (p.valide()) 
	{
		insererEnTete(p.nombre(), p.reps());
		p = p.suivant();
	}
	Place q = tete().suivant();
	while(p.valide())
	{
		q = insererApres(q,p.nombre(), p.reps());
		p = p.suivant();
	}
}

MultiEns.h

#include <iostream>

using namespace std;

class MultiEns
{ 
public:
	class Elem 
	{
	public:
		Elem(int, int, Elem *);
		int nombre, reps;
		Elem *suiv;
	class reserve {
        public:
            static void construireReserve(int);
            static void detruireReserve();
            static bool estVide();
            static Elem* get();
            static void add(void *);
            static int taille();
            static void printReserve();
            static Elem* teteReserve;
        };
        void* operator new(size_t );
        void operator delete(void *p);
	};


	class Place 
	{
	public:
		friend class MultiEns;
		Place suivant() const;
		int nombre() const;
		int reps() const;
		bool valide() const;
		Place();
		Elem *elem;
	private:
		Place(Elem *);
		
	};
 
	Place trouver(int) const;
	Place tete() const;
	int longueur() const;
	int min() const;
	int max() const;
	bool estVide() const;

	void supprimer(Place);
	static void init();
	Place insererEnTete(int ,int);
	Place insererApres(Place, int, int);

	int operator()(int e) const;
	bool operator<=(const MultiEns &) const;
	bool operator>=(const MultiEns &) const;
	bool operator<(const MultiEns &) const;
	bool operator>(const MultiEns &) const;
	bool operator==(const MultiEns &) const;
	bool operator!=(const MultiEns &) const;
	MultiEns& operator=(const MultiEns &);
	//operations entre 2 enembles
	MultiEns& operator+=(const MultiEns &);
	MultiEns& operator-=(const MultiEns &);
	MultiEns& operator*=(const MultiEns &);
	//operations entre ensmble et entier
	MultiEns& operator+=(const int);
	MultiEns& operator-=(const int);
	MultiEns& operator*=(const int);
	
	MultiEns();
	//MultiEns(const MultiEns &);
	~MultiEns();
	
private:
	void effacer();
	void copier(Place);
	Elem *tetePtr;
};

std::ostream& operator<<(ostream &out, const MultiEns &M);
MultiEns operator+(int e, const MultiEns &M);
MultiEns operator-(int e, const MultiEns &M);
MultiEns operator*(int e, const MultiEns &M);
MultiEns operator+(const MultiEns &M1, const MultiEns &M2);
MultiEns operator-(const MultiEns &M1, const MultiEns &M2);
MultiEns operator*(const MultiEns &M1, const MultiEns &M2);

A little background: I'm implementing a MultiSet, this is a type of set where any given number can have multiple appearences in a contrast to a normal Set. A MultiSet is a Circular List with the sentinel having -1 repetitions in the Set. The whole idea of this assignment was to show us how to overload operators, so most of the operations you would expect from Sets are done with overloaded operators (+ for union, - difference, * intersection etc.)

[nbaztec]

Glad for ya, looks neat, though I don't understand a word of French. :P

P.S. Do mark as solved

[Swiftle]

Before I do that I have one more question. Altough I changed the method in order to solve the problem I want to know what was causing it. When I want to do a difference or intersection of 2 sets I'm deleting the element which isn't part of both of the sets. In the code its the supprimer(p). Now here's what happens in supprimmer: all the linking and deleting is done properly however once I exit the function it's pointing towards the sentinel. Here's an exemple I tesed:

Let's say I have my set M that looks like this: M = {2,1:5,3:6:1} and B: {2,1}

Now let's say I want to do and intersection of M and B; that means that M should look like this M = {2,1}. And here's what happens in the code: It checks for 2 in B but it's not there so it attempts to remove 2 from M. Now it goes on to delete the node which contains 2. So from sentinel->2->NEXT_ELEM I want to go to sentinel->NEXT_ELEM. Once inside the supprimer() function all is well and in the end of the function the sentinel is pointing to NEXT_ELEM instead of 2. However once I'm back in my calling function (the operator *=) the Node which contained 2 now points to the sentinel and it bugs from there.

[nbaztec]

Not clear.

[Swiftle]

Not clear.

Which part exactly?

[nbaztec]

Now let's say I want to do and intersection of M and B; that means that M should look like this M = {2,1}. And here's what happens in the code: It checks for 2 in B but it's not there so it attempts to remove 2 from M. Now it goes on to delete the node which contains 2. So from sentinel->2->NEXT_ELEM I want to go to sentinel->NEXT_ELEM. Once inside the supprimer() function all is well and in the end of the function the sentinel is pointing to NEXT_ELEM instead of 2. However once I'm back in my calling function (the operator *=) the Node which contained 2 now points to the sentinel and it bugs from there.

This part.

[Swiftle]

I think the problem has something to do with the for cycle. To move in the List I create a node. The for look something like this:

for(Node N = list.start(); N.valid(); N = N.next())

So for is using the current Node, but when that note gets deleted in another function something happens that knocks the for off the rails.

[nbaztec]

Can provide with a Sample Data.