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?