Discussion :

[DarKaa]

Bonjour à tous,

Je vais essayer de vous poser le contexte :
Dans le cas d'un projet visant à calculer le chemin critique d'une liste de taches, j'en suis ramené à ça :

j'ai créé une classe tache :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
class	Task
{
private:
	std::string					_name;
	unsigned int				_duration;
	std::vector<std::string>		_next;
	std::vector<std::string>		_prev;
 
public : get/set
}

Avec _next et _prev qui contiennent le nom des taches successeurs et prédécesseurs correspondantes.
Puis je me suis dis que se serait plus simple pour la suite du projet de passer à ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
class	Task
{
private:
	std::string					_name;
	unsigned int				_duration;
	std::vector<Task*>		        _next;
	std::vector<Task*>		        _prev;
 
public : get/set
}

Avec _next et _prev qui contiennent des pointeurs vers les taches successeurs et prédécesseurs correspondantes.

J'ai créé : std::list<Task> project qui correspond à l'ensemble des taches.

Voila j'ai résumé et je pense avoir perdu personne; on en vient au problème :
Une fois qu'une tache est terminée je cherche à présent à la supprimer de l'ensemble du projet (dans la liste de taches "project" et dans des prédécesseurs des autres taches)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
void	deleteTask(std::string TaskNameToDelete, std::list<Task>& project)
{
 
}

Comment je pourrai faire dans cette fonction pour supprimer la tache nommée TaskNameToDelete en tant que Task dans la liste mais aussi en temps que prédécesseur dans _prev?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
void	deleteTask(std::string TaskName, std::list<Task>& project)
{
	std::list<Task>::iterator it = project.begin();
	std::vector<Task*>::iterator Predecessor;
 
	it = project.erase(it); // la première tache de la liste est bien celle à supprimer
	it = project.begin();
	while (it != project.end())
	{
		Predecessor = it->getPrev().begin();
		while (Predecessor != it->getPrev().end())
			{
				if ((*Predecessor) == NULL)
				{
					it->getPrev().erase(Predecessor);
				}
				Predecessor++;
			}
		it++;
	}
}

J'ai essayé ça, le problème c'est que en supprimant la tache (ligne 7) les pointeurs vers cette tache dans les prédécesseurs prennent une valeur "<Ptr> Invalid" (moi je pensais qu'il allait prendre la valeur NULL ou encore mieux etre supprimer des vectors !)

J'espère avoir été clair, si quelqu'un peut m'éclairer par une idée je suis preneur.
Merci encore.

[cob59]

Est-ce que _next et _prev ne feraient pas double emploi avec la std::list<Task> ?

[DarKaa]

Comment ca?

[cob59]

Que peux-tu faire avec _next et _prev qui ne soit pas nativement présent dans std::list<Task> ?

[DarKaa]

Rien je suis d'accord mais le principe c'est que apres je crée une td::list<Task> executing qui contient les taches en cours (celles qui nont pas de predecesseurs) j'exécute ces taches, je supprime leurs traces du projet en temps que tache mais aussi comme predecesseurs d'autre taches (d'ou le problème), je remplis executing avec les taches sans predecesseurs, je les execute, etc.. jusqu'à qu'il n'y ait plus de taches à executer.

_prev me sert a savoir quelle tache n'a pas de successeur

_next me sert a avoir les successeurs d'une tache qui est terminé pour l'enlever des predecesseurs

[3DArchi]

Quelques soupçons de STL et une décomposition du problème devrait pouvoir aider :

Une petite fonction de comparaison des tâches :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
bool same_task(std::string name_, Task const*t_)
{
    return name_==t_->name;
}

Un foncteur pour faire le déréfencement :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct derefenceTask
{
    std::string const name;
    derefenceTask(std::string name_):name(name_){}
 
    void operator()(Task&t_)const
    {
        filter_vect(t_.next);
        filter_vect(t_.prev);
    }
 
    void filter_vect(std::vector<Task*> &vect)const
    {
        vect.erase(
            std::remove_if(vect.begin(),vect.end(),std::bind1st(std::ptr_fun(same_task),name))
            ,vect.end()
        );
    }
};

Et la fonction devient simplement :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
void deleteTask(std::string TaskNameToDelete, std::list<Task>& project)
{
    std::for_each(project.begin(),project.end(),derefenceTask(TaskNameToDelete));
}

ou si tu as C++11, à coup de lambda :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void deleteTask(std::string TaskNameToDelete, std::list<Task>& project)
{
    std::for_each(project.begin(),project.end(),
        [&TaskNameToDelete](Task &t_){
            auto filter_vect = [&TaskNameToDelete](std::vector<Task*> &vect)
            {
                vect.erase(
                    std::remove_if(vect.begin(),vect.end(),[&TaskNameToDelete](Task *t2)
                    {
                        return TaskNameToDelete == t2-> name;
                    })
                ,vect.end()
                );
            };
            filter_vect(t_.next);
            filter_vect(t_.prev);
        }
    );
}

Ceci dit, comme cob59, je ne suis pas sûr de bien comprendre ton design

[jblecanard]

Salut !

J'ai essayé ça, le problème c'est que en supprimant la tache (ligne 7) les pointeurs vers cette tache dans les prédécesseurs prennent une valeur "<Ptr> Invalid" (moi je pensais qu'il allait prendre la valeur NULL ou encore mieux etre supprimer des vectors !)

Là, tu crois un peu au père Noël . La proposition de 3DArchi est très bien et fonctionnera.

J'en ai une autre à proposer qui est similaire et plus performante, mais qui demande un léger changement de structure de donnée.

Plutôt que de stocker des Task dans une liste et des pointeurs de Task dans m_prev et m_next, tu peux stocker des shared_ptr<Task> dans la liste du projet et des weak_ptr<Task> dans les vectors des Task. De cette manière, lorsque tu détruiras tous les shared_ptr qui tiennent une Task, les weak_ptr deviendront invalides et seront capables de détecter cet état invalide. Du coup, tu peux filtrer les vecteurs comme le fait 3DArchi, mais au lieu de le faire sur le nom de la tâche, tu le fait sur la validité des pointeurs contenus dans les vectors. Cette vérification coûte un déréférencement de pointeur et la lecture d'un int, ce qui nettement plus efficace qu'une comparaison de chaîne.

En échange, il y a un coût d'apprentissage des smart pointers, et il faut voir comment ça se goupille avec le reste de ton code (en général ça se passe quand même bien, c'est bien fait les smart pointers).

Je suis aussi dubitatif sur ton design de départ mais puisque ce n'est pas le sujet, je vais pas rentrer là dedans.

[DarKaa]

Lol oui j'exagérai un peu quand je disais que tout allait se faire tout seul

Sinon pour en revenir au problème c'est clair que nous n'avons pas le même niveau en C++ car je ne comprends pas trop la solution de 3DArchi et quand a celle de jblecanard, je n'ai jamais utilisé des shared_ptr<Task> et des weak_ptr<Task>

J'ai donc deux solutions, soit je copie celle de 3DArchi soit je me renseigne sur ces fameux pointeurs (le pense faire la 2e solution car j'ai une sainte horreur de copier quelque chose que je ne comprends pas)

ps : Sinon je comprends pas pourquoi vous comprenez pas mon disign,
Pour calculer le chemin critique d'un projet, je trouve les taches sans prédécesseurs, je stock la durée max de celles ci, je les supprime du projet, et je fais ceci jusqu'à qu'il n'y ait plus de tache sans prédécesseur. Si il n'y a plus de tache sans prédécesseur et que le projet est vide alors le programme est fini sinon c'est qu'il y a une boucle entre les taches ou qu'il y a discontinuité entre les taches dans le projet. 3 types de boucle infinie :
- une tache a pour successeurs elle même
- la dernière tache a pour successeur la première
- un quelconque tache dans le projet a pour successeur une tache déja terminée.

[Bousk]

Bonjour,

je rejoinds les commentaires précédents : je ne comprends pas ce que tu entends par tes vector.
Une tâche précédente ou suivante, reste une tâche, et non un vector de tâches.

As-tu regardé std::list ? Ca ressemble mot pour mot à ce que tu sembles souhaiter.
Ou bien un vector de tâches initiales qui sont les têtes de list.
Une tâche qui aurait une liste de tâche en "prédécesseur" serait une tâche qui devrait démarrer une fois que toutes ces tâches sont terminées. Dans ce cas on parle de dépendance plutôt.

[jblecanard]

J'ai donc deux solutions, soit je copie celle de 3DArchi soit je me renseigne sur ces fameux pointeurs (le pense faire la 2e solution car j'ai une sainte horreur de copier quelque chose que je ne comprends pas)

Alors d'une part tu peux la comprendre avec un peu de travail en te renseignant sur la STL, ses fonctions et ses collections. Et puisque tu utilises std::list et std::vector, ce serait la moindre des choses de bosser un peu les itérateurs et les algorithmes STL.

D'autre part, ma proposition consiste en prendre celle de 3DArchi et à ne remplacer que la partie du test. 3DArchi teste sur le nom, moi je propose de tester plutôt sur la validité d'un weak_ptr. C'est vrai, avec des smart pointers tu peux ne pas filtrer et laisser des weak_ptr invalides traîner. Mais ce n'est pas ce que je propose.

Point de vue design, à mon avis ton problème peut être résolu avec la théorie des graphes si on le pose correctement.

[DarKaa]

Je suis d'accord que la théorie des graphes correspond à mon problème mais j'ai un algorithme imposé..
Les vectors _prev et _next contiennent des pointeurs sur les taches qui précèdent et succèdent à la tache. Project n'est qu'une liste de tache, elles ne sont pas obligatoirement dans l'ordre d'execution, je ne vois pas qu'est ce qui a de dur à comprendre Mais tu as raison j'aurai pu utiliser deux list à la place des vector mais je vois pas l'interet..

Quand à la STL, je ne suis pas ignorant quand même, j'ai déja rodé l'utilisation des principaux conterner (string, liste, vector, map (que j'ai du recoder)) ainsi que leur méthodes, les streams, etc.. Mais il est vrai que j'ai jamais entendu parler de "smart pointeur"

[DarKaa]

Bon alors si j'ai bien compris le concept, les shared_ptr se partage l'accès a une donnée ainsi qu'une responsabilité (d'ou leur nom). Si par exemple 3 shared_ptr pointent sur un objet, ce n'est qu'au delete du troisième que l'objet sera détruit.
Les weak_ptr complète ce concept en leur donnant aucune responsabilité. Si par exemple un shared_ptr et un week_ptr pointent sur un même objet. Si on delete le weak_ptr en premier rien de special (a par que l'on a perdu un accès a l'objet) et si ensuite on delete le shared, l'objet est détruit.
Par contre si on delete en premier le shared_ptr, l'objet est détruit mais alors qu'elle sera la valeur du weak_ptr?

[Arzar]

Bonjour,
AHMA, utiliser des shared_ptr/weak_ptr compliquerait la situation.
Je ne comprends pas très bien ce qui bloque au final, j'ai l'impression que le code du premier post résout déjà quasiment le pb ? (qui n'est pas sorcier)

J'ai essayé ça, le problème c'est que en supprimant la tache (ligne 7) les pointeurs vers cette tache dans les prédécesseurs prennent une valeur "<Ptr> Invalid" (moi je pensais qu'il allait prendre la valeur NULL ou encore mieux etre supprimer des vectors !)

Si tu supprimes en premier la tache à détruire dans le liste project, alors qu'y a-t-il de surprenant à ce que tous les pointeurs vers cette tache deviennent invalides !?
pointeur invalide == pointeur pointant vers une zone mémoire invalide == pointeur pointant vers un objet ayant été détruit par exemple.

Donc il faut simplement d'abord supprimer les pointeurs vers la tache à détruire dans les vector _prev de toutes les autres taches et ensuite supprimer la tache en question dans la liste project

En pseudo code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
pour chaque Task t dans projet
  pour chaque Task* tptr dans t._prev
    Si tptr->_name == nom_de_la_tache_a_detruire alors
      retirer tptr de t._prev
  fin pour
fin pour
 
Chercher Task t dont t._name ==  nom_de_la_tache_a_detruire  dans projet
   Retirer t de projet

Edit : Le code de 3D archi fait exactement ce qu'il y a dans la première boucle du pseudo code. (sauf qu'il supprime aussi dans les vecteurs _next). L'avantage c'est que le code est très concis, vu qu'il tire parti d'algo de la STL, mais si ça te perturbe trop rien n'interdit de le faire à la main avec une bonne vieille double boucle

[DarKaa]

Je sais qu'il n'y a rien de surprenant merci mais le truc que je saisissais pas c'était le fait que lorsque je détruisais l'objet le pointeur sur lui dans les _next devenaient invalides mais pas NULL (je comprends pas pourquoi les pointeurs invalides, donc ceux qui servent à rien, ne sont pas NULL)
Et ta méthode qui consiste à d'abord supprimer les pointeurs dans _next de la tache à supprimer avant la tache elle même dans project, j'y avais pensé mais cela me semblait plus logique de faire l'inverse (d'où le problème)

[3DArchi]

le truc que je saisissais pas c'était le fait que lorsque je détruisais l'objet le pointeur sur lui dans les _next devenaient invalides mais pas NULL

Il faut distinguer deux choses :

• la donnée pointée qui possède une adresse et une taille ;
• un pointeur qui n'est qu'une variable d'un type particulier destiné à contenir une adresse.

L'allocation (dynamique ou pas) d'un objet consiste à lui réserver une zone mémoire (adresse+taille) et à construire cet objet. La libération (delete ou automatique) consiste à détruire l'objet et rendre cette zone mémoire.
Un pointeur contient une adresse mémoire typée. Cette adresse peut être copiée vers un autre pointeur de même type. Le pointeur peut changer de valeur, c'est à dire contenir une nouvelle adresse lui permettant de pointer différents objets au cours du temps.
En C++, aucune cohérence n'est à priori assurée entre les variables contenant des adresses, i.e. les pointeurs, et les zones désignées par ces pointeurs. C'est au développeur de garantir que les pointeurs contiennent bien des adresses valides et sinon de les mettre à NULL.

[DarKaa]

Merci pour ce cours sur les pointeurs mais cela ne répond pas trop a ma question C'est donc à moi de mettre à NULL un pointeur qui pointe sur un objet détruit :S
Que fais je alors, j'utilise les smart pointeur ou bien la solution de facilité qui consiste à supprimer d'abord les pointeurs vers les prédécesseurs et ensuite la tache elle même?

[3DArchi]

C'est donc à moi de mettre à NULL un pointeur qui pointe sur un objet détruit :S

En C++, aucune cohérence n'est à priori assurée entre les variables contenant des adresses, i.e. les pointeurs, et les zones désignées par ces pointeurs. C'est au développeur de garantir que les pointeurs contiennent bien des adresses valides et sinon de les mettre à NULL.

Que fais je alors, j'utilise les smart pointeur ou bien la solution de facilité qui consiste à supprimer d'abord les pointeurs vers les prédécesseurs et ensuite la tache elle même?

Donc il faut simplement d'abord supprimer les pointeurs vers la tache à détruire dans les vector _prev de toutes les autres taches et ensuite supprimer la tache en question dans la liste project

[Arzar]

je comprends pas pourquoi les pointeurs invalides, donc ceux qui servent à rien, ne sont pas NULL

Parce que tu es en C++, pas en Java.
You don't pay for what you don't use.

Tu imagines le bazar que ça serait si tous les pointeurs pointant vers un objet devrait être mis à NULL lors de la destruction ? Il faudrait une sorte de Garbage Collector tournant en arrière plan et tenant la listes de toutes les associations objet-pointeur existant, liste qui serait parcouru à chaque destruction d'objet pour aller mettre chacun de ces pointeurs à NULL !!

Le C++ est transparent. Si tu vois :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Truc* t = &toto;

Ce bout de code fait exactement ce qu'il y a écrit et pas plus. Il crée sur la pile un pointeur contenant l'adresse de toto. Le compilateur génèrera 2/3 instructions d'assembleur au maximum. Jamais un programmeur C++ ne s'attendrait à ce que le compilateur lui mente et génère des dizaines et des dizaines d'instruction pour qu'un garbage collector invisible mette à jours le fait qu'il y a un nouveau pointeur "t" pointant vers l'objet "toto".

Donc au final lorsqu'un objet est détruit il ne se passe... RIEN. Car c'est le plus économique.
Aucun des pointeurs n'est modifié. On dit qu'ils sont "invalides" mais c'est purement sémantique, au niveau de la machine il pointe toujours vers le même bloc de mémoire.

[koala01]

Salut!

J'avoue ne pas avoir lu toutes les interventions, mais il y a une question qui m'interpelle...

Je comprend qu'il soit nécessaire de maintenir une trace des taches précédentes et des taches suivantes, mais je me demande pourquoi il faudrait garder en mémoire l'ensemble de celles-ci

Je m'explique :

Sauf erreur, les différentes tâches doivent être effectuées de manière séquentielle, l'une après l'autre, et dans un ordre donné.

Même dans un contexte multi threadé, on peut considérer que chaque thread ne fait qu'effectuer une tache à la fois, de manière séquentielle, l'une après l'autre et dans un ordre donné.

Il n'y a donc, a priori, aucune raison de garder en mémoire l'ensemble des taches précédentes / suivantes : seule celle qui précède / suit effectivement une tache donnée est suffisante et devrait suffir, non

[DarKaa]

Sauf erreur, les différentes tâches doivent être effectuées de manière séquentielle, l'une après l'autre, et dans un ordre donné.

Si la tache A a pour successeurs la tache B et la tache C, une fois la tache A terminée, les taches B et C s'executeront en même temps hein?
Si cela répond à ta question
ps : Je n'ai pas le droit de travailler uniquement sur les prédécesseurs, c'est bete mais c'est comme ca (sujet imposé)