Bonjour à tous 

Si j'aurais à faire une classe qui gère une liste chainée dois-je là déclarer dans le .h ou dans le constructeur ?

comme variable privée aurais-je besoin de juste le pointeur suivant et précédant ?

j'ai suivi le tuto sur les listes chainées mais je n'ai pas compris grand chose lol 

voila tout ce que j'ai réussi à faire jusqu'à maintenant :

le .h :

public:
	LinkedListStack();
	~LinkedListStack();
	void push(int& element);
	void pop();
	int& top() const;
	bool isEmpty() const;
	int size() const;

private:
	typedef struct element element;
	struct element
	{
		int val;
		struct element *next;
	};
	typedef element* llist;

	int *_next;
	int *_prev;
	int _nbElement;
};

et le .cpp :

#include "LinkedListStack.h"

LinkedListStack::LinkedListStack()
{
	llist llistStack = NULL;

}


LinkedListStack::~LinkedListStack()
{
}

void LinkedListStack::push(int& value)
{
	element* newElement = malloc(sizeof(element));
	newElement->val = value;
	newElement->nxt = liste;
}

Tout aide est la bien venue

-
Edité par Qac88 15 octobre 2017 à 21:01:14

Salut,

Là, ce que tu nous présente, c'est un code C.  Il fonctionnera avec un compilateur C++, mais bon, quelques adaptations permettront déjà de le faire ressembler d'avantage à du code C++ :

• la ligne typedef struct element element; est totalement inutile en C++ : lorsque tu crées un type de donnée personnalisé (qu'il s'agisse d'une structure, d'une classe, d'une énumération ou d'une union), le fait de le définir permet automatiquement au compilateur que le type existe.
• L'utilisation de NULL a été dépréciée en 2011, et on préfère depuis utiliser nullptr.
• malloc est une fonctionnalité issue de C, à laquelle on préférera l'utilisation de new.
• on préférera, depuis 2011, utiliser la directive using nouveau_type = type_connu; à la directive typedef type_connu nouveau_type;

Ensuite, il y a quelques problèmes à corriger:

• tu définis le typedef elment * llist; mais tu ne l'utilise pas
• tes pointeurs previous et next devraient
  • être renommé en first et last pour représenter d'avantage l'usage qui en est fait
  • être des pointeurs vers des éléments de ta liste, et non des pointeurs vers des entiers
• ta fonction push n'a aucune raison de modifier la valeur qu'elle reçoit en paramètre.  Tu devrais donc la fournir sous une forme constante
• il n'y a aucun intérêt, quand une fonction ne modifie pas un paramètre, de transmettre un type primitif sous forme de référence: le transmettre sous forme de valeur est au moins aussi efficace
• Ta fonction top() s'engage à ne pas modifier la liste (à cause du const final), or elle renvoie une référence sur un entier, ce qui rompt cet engagement
• Ta liste occasionne des fuites mémoire, car tu ne libère jamais la mémoire allouée par malloc (il manque un free équivalent "quelque part")
• Ta liste correspond d'avantage au concept de pile qu'au concept de liste...  Tu devrait "simplement" la nommer Stack, la manière dont les éléments sont reliés entre eux n'étant qu'un "détail d'implémentation"

Enfin, depuis 2011 et l'arrivée de C++11, on dispose (enfin!) d'outils destinés à nous faciliter la tâche, comme celui de std::unique_ptr qui nous permet de définir clairement quand les ressources allouées de manière dynamique doivent être libérées.  Tu serais peu-être bien inspiré de les utiliser

NOTA: Je pars du principe que tu veux t'amuser à mettre le concept de pile en place par toi-même, et que c'est une expérience sympa à faire bien qu'elle soit totalement inutile (*). 

Mais, l'un dans l'autre, garde toujours en-tête que la bibliothèque standard fournit un tas de collections adaptées aux différentes situations, et que tu devrais les utiliser "par défaut".

(*) oui, totalement inutile, car ce n'est pas le genre de problème auquel il faudrait confronter le débutant pour lui apprendre la gestion dynamique de la mémoire

Salut.

Ton code va faire en moins bien ce que std::liste fait en bien. C'est très bien dans un intérêt didactique si tu veux apprendre les rouages d'une liste chainée, mais c'est pas bien, si tu as vraiment besoin de ce container.

Comme expliqué par koala, tu mélanges un peu le C et le C++. Si c'est parce que tu viens du C, fais attention, si c'est ton cours qui fait ça, il a été écrit par un dinausore, et faut que tu en change parce que tu vas apprendre de mauvaises habitudes.

Ta liste devrait prendre un paramètre template : le type des données à contenir.

//--- LinkedListStack.hpp ---

#include <cstddef>   //size_t
#include <stdexcept> //runtime_error
#include <ostream>


template<typename T>
struct LinkedListStack{

	LinkedListStack();
	~LinkedListStack();

	bool    empty() const;
	size_t  size()  const; //les tailles sont des size_t

	//construire un nouvel élément
	template<typename ... Args>
	void emplace_front(Args...);

	//effacer le permier élément.
	void pop();

	//lire le premier élément
	const T& top()const;

	//modifier le premier élément
	T& top();


	void debug(std::ostream &out);


	private:
	struct Element{
		template<typename ... Args>
		Element(Args... a):val(std::forward<Args>(a)...),next(nullptr){}

		//Pas de copie par défaut
		Element(const Element&)            =delete;
		Element& operator=(const Element &)=delete;

		T val;
		Element* next=nullptr;
	};

	Element * front=nullptr;
	size_t size_v=0;

};

#include "LinkedListStack.tpp"


//--- LinkedListStack.tpp ---
template<typename T>
LinkedListStack<T>::LinkedListStack(){}


//Effacer les élément de la liste. Tu verras souvent sur le net du code qui
//utilises une fonction récursive pour faire ca, c'est élégant mais ca ne marche
//pas dès que tu utilises des grandes listes, parce que ca va saturer la pile
//et faire stack overflow.
//Tu as le même problème si tu utilises le destructeur de Element pour détruire
//L'élément suivant : les destructeurs vont s'appeler en cascade, et ca va
//remplir la pile.
//Donc ne fais pas ça, et utilises plutot un while
template<typename T>
LinkedListStack<T>::~LinkedListStack(){
	Element*ptr=this->front;
	while(ptr!=nullptr){
		Element*tmp = ptr;
		ptr=ptr->next;
		delete tmp;

	}
}



template<typename T>
bool LinkedListStack<T>::empty()const{
	return this->size_v==0;
}

template<typename T>
size_t  LinkedListStack<T>::size()const{
	return size_v;
}


//construire un nouvel élément
template<typename T>
template<typename ... Args>
void LinkedListStack<T>::emplace_front(Args... a){
	Element * new_element = new Element(std::forward<Args>(a)...);
	new_element->next = this->front;
	this->front=new_element;
	++size_v;
}



//effacer le permier élément.
template<typename T>
void LinkedListStack<T>::pop(){
	if(size_v==0){throw std::runtime_error("Cannot pop from empty list");}
	Element* delete_me = front;
	front=front->next;
	--size_v;
	delete delete_me;
}


//lire le premier élément
template<typename T>
const T& LinkedListStack<T>::top()const{
	if(size_v==0){throw std::runtime_error("Cannot call const top on empty list");}
	return front->val;
}

//modifier le premier élément
template<typename T>
T& LinkedListStack<T>::top(){
	if(size_v==0){throw std::runtime_error("Cannot call top on empty list");}
	return front->val;
}




//modifier le premier élément
template<typename T>
void LinkedListStack<T>::debug(std::ostream &out){
    out << size() <<":";
    Element* ptr=this->front;
    while(ptr!=nullptr){
    	out << ptr<<" ";
    	ptr=ptr->next;
    }
    out << std::endl;
}


//--- main.cpp ---
#include <iostream>
#include <cassert>

struct Test_count{
	static size_t count;
	Test_count() {++count; std::cout << "+Test(cstr):" << count <<std::endl; }
	Test_count(const Test_count &t) {++count; std::cout << "+Test(copy):" << count <<std::endl; }
	~Test_count(){--count; std::cout << "-Test:" << count <<std::endl; }
};
size_t Test_count::count = 0;




int main(){
	LinkedListStack<Test_count> t;

	std::cout << "--- 1 ---"<<std::endl;
	assert(t.empty());
	assert(t.size()==0);
	t.debug(std::cout);

	std::cout << "--- 2 ---"<<std::endl;
	Test_count a;
	t.emplace_front(a);
	assert(!t.empty());
	assert(t.size()==1);
	t.debug(std::cout);

	//top doit marcher
	      Test_count & t_ref  = t.top();
	const Test_count & t_cref = t.top();


	std::cout << "--- 3 ---"<<std::endl;
	t.emplace_front();
	assert(!t.empty());
	assert(t.size()==2);
	t.debug(std::cout);

	std::cout << "--- 4 ---"<<std::endl;
	t.pop();
	assert(!t.empty());
	assert(t.size()==1);
	t.debug(std::cout);


	std::cout << "--- 5 ---"<<std::endl;
	t.pop();
	assert(t.empty());
	assert(t.size()==0);
	t.debug(std::cout);


	std::cout << "--- 6 ---"<<std::endl;
	//top doit lancer une exception
	bool ok=false;
	try{t.top();}
	catch(std::exception &e){ok=true;}
	assert(ok);
	t.debug(std::cout);




	//on vérifie que la destruction détruise bien 3 objets
	std::cout << "--- 7 ---"<<std::endl;
	t.emplace_front();
	t.emplace_front();
	t.emplace_front();
	t.debug(std::cout);

}

Beurk, le traitement de contrats avec des exceptions.

En plus, donner une sémantique d'entité à l'élément de la liste, c'est moyen moyen... car dans de nombreux cas, les valeurs que nous voudrons introduire dans la liste devraient avoir sémantique de valeur et non sémantique d'entité.

Tu devrais donc retomber sur la forme canonique orthodoxe de Coplien et sur la grande règle de trois

EDIT: Mais attention, il y a une astuce avec les différents pointeurs

-
Edité par koala01 16 octobre 2017 à 13:40:53

@Ksass Peuk, comment fais tu pour te passer des exceptions, par exemple si on appelle top() sur une liste vide?

C'est un contrat. C'est une assertion qu'on attend ici.

@lemondeboiteux Au pire une std::logic_error est plus présentable. Sinon, assert c'est bien. UB, c'est ce que fait le standard. Et `[[requires: ! empty()]]` est l'avenir probable.

Cf mes 3 billets sur la PpC, et je vais présenter rapidement le sujet lors des prochains Capitole du Libre à Toulouse.

-
Edité par lmghs 18 octobre 2017 à 2:08:23

@lmghs Il y a des choses intéressantes au CLT. Sais tu s'il y aura des vidéos des présentation publiées ? (HS : tu es deja venu sur le discord ? As tu vu le club de lecture ?)

<HS>

Je ne sais pas s'il y aura des vidéos filmées. J'ai envie de dire qu'à priori: oui -> cf.  https://2016.capitoledulibre.org/videos.html

Pour discord, je suis passé une fois, mais guère le temps de venir et de m'y attarder sérieusement. Donc je suis vos comptes rendus (du club de lecture) de loin -- j'ai déjà tous les derniers CppCon à rattraper.

</HS>

HS : avec 50h de vidéos publiées tous les jours, je ne vois pas où est le problème à suivre CppCon

Ces 3 billets?
http://luc-hermitte.developpez.com/tutoriels/c++/programmation-par-contrat/partie-1-un-peu-theorie/


@Ksass`Peu, Imhs
Merci, j'avais pas pensé a voir les choses comme ça, et c'était toujours confus dans ma tête (exception ou assert).
Si j'ai bien compris : contra => assert, comportement inattendu => exception

-
Edité par ledemonboiteux 24 octobre 2017 à 10:00:34

ledemonboiteux a écrit:

Merci, j'avais pas pensé a voir les choses comme ça, et c'était toujours confus dans ma tête (exception ou assert).
Si j'ai bien compris : contra => assert, comportement inattendu => exception

Wala. Basiquement, si le développeur ne peut rien y faire, c'est vache de lui balancer un assert dans la bouche. Pour tout le reste : pas de pitié.

ledemonboiteux a écrit:

Ces 3 billets?
http://luc-hermitte.developpez.com/tutoriels/c++/programmation-par-contrat/partie-1-un-peu-theorie/


@Ksass`Peu, Imhs
Merci, j'avais pas pensé a voir les choses comme ça, et c'était toujours confus dans ma tête (exception ou assert).
Si j'ai bien compris : contra => assert, comportement inattendu => exception

-
Edité par ledemonboiteux il y a 21 minutes

Oui, c'est à peu près ca...

A vrai dire, la première partie (contrat => assert), c'est tout à fait cela, même si on dispose désormais -- pour certains types de contrats -- des static_assert qui "plantent encore plus tôt" (au moment de la compilation), et qui sont encore mieux quand on peut s'en servir (au plus tôt l'erreur est signalée, au mieux c'est :D)

Les exceptions, c'est destiné aux situations... exceptionnelles.  A ce genre de situations dont on espère secrètement qu'elles ne se produiront jamais mais dont on sait -- parce qu'on ne vit pas dans le monde des bisounours -- qu'elles risquent malgré tout de survenir à un moment ou à un autre, et que l'on ne pourra rien faire pour les éviter, à part "en prendre acte":

Le serveur qui plante à l'autre bout de la planète, tu ne sais rien y faire, à part... attendre qui soit relancé.

Si un imbécile s'amuse à effacer ou à modifier n'importe comment le fichier dont tu as besoin et qui est sensé être structuré d'une certaine manière tu ne sais rien y faire non plus.  Mais ca te tout quand même dans la merde.

Pas plus que si un fou furieux décide de couper le fil qui relie ton modem à l'internet ou que, de manière générale, tu as besoin d'une ressource qui est "indisponible / inadéquate pour l'instant" pour une raison ou une autre.

Ca, ce sont des situations que tu vas traiter à coup d'exceptions.

Merci pour vos commentaires et vos infos,

En+ de la page sur la programmation par contra, j'ai trouvé l'article suivant (en anglais) très intéressant sur les exceptions (et notament ce qu'est/n'est pas une exception).

http://www.drdobbs.com/when-and-how-to-use-exceptions/184401836

@Luc Comment se sont passe tes confs ?