liste imbriquée dans une liste

Version imprimable

11/01/2010, 22h03
ba1boun2

liste imbriquée dans une liste

Bonjour... ou plutôt bonsoir!

Je voudrai savoir si c'est possible de créer une liste dans laquelle j'ai des éléments de type classe mais aussi un élément de type liste. Si oui merci de me donner quelques indications sur la procédure a suivre.

Merci
11/01/2010, 22h44
Klaim

Citation:

Je voudrai savoir si c'est possible de créer une liste dans laquelle j'ai des éléments de type classe mais aussi un élément de type liste.

Je pense que tu n'utilises pas les bons termes parceque ta phrase n'a pas beaucoup de sens. Est-ce que tu peux nous montrer ce que tu appelles "une liste"?

En fait j'ai fait comme ça :
Code:

1 2 3 4 5 typedef struct L_dossier { dossier dossier_n; }un_dossier; typedef list<un_dossier> Tdossier;
où dossier est une classe.

Ok, alors dans ce cas ce que tu veux n'est pas directement possible, puisqu'une liste (std::list) ne peut contenir qu'un type. En revanche, tu peux faire quelque chose comme

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
// pas besoin de typedef en C++
struct un_dossier
{
	dossier dossier_n;
};
 
typedef std::list<un_dossier> Tdossier;
 
class node
{
public:
 
    // ces constructeurs vont rendre impossible d'avoir les deux pointeurs qui pointent sur quelque chose, c'est soit l'un, soit l'autre, soit aucun 
    node() : m_d( NULL ) , m_ld( NULL ) {}
    node( un_dossier* pd ) : m_d( pd ) , m_ld( NULL ) {}
    node( Tdossier* pld ) : m_d( NULL ) , m_ld( pld ) {}
    node( const node& other ) : m_d( other.m_d ) , m_ld( other.m_ld ) {}
 
    // helper
    bool isList() const { return ld != NULL; }
 
    //les accesseurs, on expose pas les membres pour  éviter que l'utilisateur ne change les pointeurs lui même
    un_dossier* d() const { return m_d; }
    Tdossier* ld() const { return m_ld; }
 
 
private:
    un_dossier* m_d;
    Tdossier* m_ld;
 
};
 
typedef std::list< node > special_list; // une liste qui peut "contenir" les deux
 
// utilisation
 
un_dossier* pd = new un_dossier();
Tdossier* pl = new Tdossier();
special_list.push_back( pd ); // pour ajouter un dossier
special_list.push_back( pl ); // pour ajouter une liste
 
const node& first_node = special_list.front();
if( first_node.isList() )
{
    Tdossier* first_list = first_node.ld();
}
else
{
    un_dossier* first_dossier = first_node.d();
}

Ou encore utiliser std::pair pour aller plus vite.

Mais de base clairement si tu te poses cette question c'est qu'il y a un problème dans ta conception. Quel est le problème que tu tentes de résoudre à l'origine?

12/01/2010, 01h57
Invité

Citation:

Envoyé par ba1boun2

Je voudrai savoir si c'est possible de créer une liste dans laquelle j'ai des éléments de type classe mais aussi un élément de type liste. Si oui merci de me donner quelques indications sur la procédure a suivre.

Dans la littérature, tu peux regarder le pattern "composite", qui correspond grosso modo à ce que tu veux faire. Il y en a plusieurs implémentations en C++, notamment pour traiter des problèmes de répertoires et de fichiers...

Francois
12/01/2010, 07h40
3DArchi

Bonjour,
Boost.Variant te propose une union et tu peux alors le mettre dans une liste de façon sûre.
16/01/2010, 01h18
ba1boun2
Klaim -> j'ai suivit tes indications, j'ai essayé ça :
Code:

1 2 3 4 5 6 7 8 9 const node& first_node = special_list.front(); if( first_node.isList() ) { Tdossier* first_list = first_node.ld(); } else { un_dossier* first_dossier = first_node.d(); }
Mais à la compilation, à la première ligne, il me dit :

Citation:

expected primary-expression before ‘.’ token
16/01/2010, 01h22
Klaim

A quelle ligne?
16/01/2010, 11h45
ba1boun2

Citation:

const node& first_node = special_list.front();
16/01/2010, 13h24
Klaim

Je ne vois pas le problème... vérifie qu'il n'y a pas une erreur de syntaxe dans les lignes au dessus de celle ci?
22/01/2010, 12h11
eyquem

Bonjour,

J'aimerais savoir si ce problème a été résolu.

Le problème posé me paraît simple et légitime.
C++ offre-t-il un moyen d’y répondre ou pas ?

En Python, les éléments d’une liste peuvent être de types quelconques et hétérogènes.
22/01/2010, 12h26
3DArchi

Salut,

Citation:

Envoyé par eyquem

J'aimerais savoir si ce problème a été résolu.

Le problème posé me paraît simple et légitime.
C++ offre-t-il un moyen d’y répondre ou pas ?

Le C++ est un langage statiquement typé, il faut donc s'organiser un peu pour parvenir à une solution.
Il y a plusieurs moyens de résoudre ce problème :
-> 1/ Le pattern composite s'il y a un sens et donc avec un mécanisme d'héritage ;
-> 2/ Boost.Variant pour une union générique mais dont les types possibles sont limités ;
-> 3/ Boost.Any pour une union générique avec n'importe quel type ;
-> 4/ Une solution ad-hoc comme proposée par Klaim.

C++0x :
On aurait envie de faire une union (union {TYPE_1 t1; TYPE_2 t2;};)et de la mettre dans le conteneur. Or, aujourd'hui les types pouvant être mis dans une union sont assez restreints. C++0x étend les unions et permet à terme d'y placer n'importe quel type d'objet (or, bien sûr, des références). Cela devrait permettre de créer des conteneurs d'union moyennant certainement du code supplémentaire dans l'union (constructeur par défaut, de copie, opérateur=, destructeur).
22/01/2010, 19h35
eyquem

Merci pour la réponse.

Citation:

1/ Le pattern composite s'il y a un sens et donc avec un mécanisme d'héritage ;

Que signifie «s'il y a un sens» svp ?

J’ai lu la doc sur le pattern composite, mais comme je ne connais pas C++, je n’ai rien compris.

Citation:

2/ Boost.Variant pour une union générique mais dont les types possibles sont limités ;
3/ Boost.Any pour une union générique avec n'importe quel type ;

Que signifie «une union générique» svp ?

Comme ba1boun2 parle d’une liste dont les éléments sont des classes et une liste, il me semble que Boost.Variant est ce qui lui convient mieux que Boost.Any, n’est ce pas ?

Je note que Boost est un ensemble de librairies qui ne fait pas à proprement parler partie du langage C++,
et que Variant est une extension qui ne fait partie de Boost que depuis la version 1.31 publiée en Janvier 2004.

Citation:

4/ Une solution ad-hoc comme proposée par Klaim.

Dans la mesure où le code proposé par Klaim produit à la compilation une erreur dont je n’ai pas vu de résolution, on ne peut pas encore appeler la proposition de Klaim une solution.

La question que je me pose est celle-ci: je suppose qu’en C++ (que je ne connais pas) comme en n’importe quel autre langage, une liste est un conteneur possédant certaines caractéristiques.
Le pattern composite, Boost.Variant ou la “solution“ de Klaim apportent-elles les mêmes caractéristiques qu’une liste, ou du moins celles dont ba1boun2 a besoin (ce à quoi il est seul à pouvoir répondre).
22/01/2010, 20h47
koala01
Salut,

Citation:

Envoyé par eyquem

Citation:

1/ Le pattern composite s'il y a un sens et donc avec un mécanisme d'héritage ;

Que signifie «s'il y a un sens» svp ?

J’ai lu la doc sur le pattern composite, mais comme je ne connais pas C++, je n’ai rien compris.

Le pattern composite va se baser sur l'existence de trois classes (ou plus):
- une classe de base qui présente l'ensemble des comportements et propriétés commune aux deux autres
- une classe dérivée de la classe de base qui représente les objets qui n'ont pas d'enfants (on parle de "feuille")
- une classe dérivée de la classe de base qui représente les objet qui peuvent avoir des enfants (on parle de "noeud").
S'il s'agit de représsenter une arborescence de dossiers et de fichiers, nous pourrions dire que les fichiers seront d'office des feuille (un fichier ne pouvant contenir ni dossier ni fichier), et qu'un dossier sera d'office un noeud (pouvant contenir des dossiers, des fichiers, mais pouvant aussi être vide).

Seulement le fait que les feuilles et les noeuds dérivent d'une classe de base implique qu'il faut, avant tout, vérifier s'il est effectivement possible de trouver un ensemble de propriétés commun aux noeuds et au feuille, de manière à respecter le principe de substitution de Liskov.

Cela revient à se poser une question proche de

Citation:

Puis-je, réellement, dire que toute feuille (ou que tout noeud) EST UN objet du type de (la classe de base) :question:

Si tu peux décemment répondre par oui à cette question pour les feuilles ET pour les noeuds, c'est qu'il " y a du sens" à utiliser le pattern composite, autrement, il faut... envisager une autre solution ;)
22/01/2010, 21h02
Klaim

Citation:

Dans la mesure où le code proposé par Klaim produit à la compilation une erreur dont je n’ai pas vu de résolution, on ne peut pas encore appeler la proposition de Klaim une solution.

Comme dit précédemment, le problème viens surement avant la ligne que tu as indiqué. Je n'ai pas ton code donc je ne peux pas t'aider plus là dessus. L'exemple que je t'ai donné marche chez moi.
23/01/2010, 10h05
3DArchi
Citation:

Envoyé par eyquem

La question que je me pose est celle-ci: je suppose qu’en C++ (que je ne connais pas) comme en n’importe quel autre langage, une liste est un conteneur possédant certaines caractéristiques.
Le pattern composite, Boost.Variant ou la “solution“ de Klaim apportent-elles les mêmes caractéristiques qu’une liste, ou du moins celles dont ba1boun2 a besoin (ce à quoi il est seul à pouvoir répondre).

Le type std::list de la STL (la bibliothèque définie par la norme du C++) implémente une liste dont chaque élément a le même type statique. Pour contourner cette contrainte, on a 2 solutions :

-> Utiliser l'héritage pour obtenir une hétérogénéité du type dynamique des éléments de la liste. C'est la solution de l'héritage. Le DP Composite est un cas particulier d'héritage. Quand j'ai dit 'si ça un sens', c'est parce qu'il ne faut pas mettre en place un héritage juste pour pouvoir insérer des éléments hétérogènes dans une liste. L'héritage est une relation forte entre 2 classes et doit être mise en oeuvre parce qu'une conception le justifie.

-> L'union présente un type statique commun mais peut être accéder selon un autre type statique particulier :
Code:

1 2 3 4 union type_union{ type_element_1 el1; type_element_2 el2; }
La liste contient que des noeuds de type statique type_union. Cependant chaque noeud sera soit un type_element_1 soit un type_element_2. Les unions du langage, telles que présentées ci-dessus, présentent un certain nombre de limites sur les types qu'elles peuvent encapsuler. Boost.Variant est une bibliothèque qui propose les mêmes attendus d'une union en supprimant beaucoup de ces contraintes sur les types. La solution ad-hoc, comme la propose Klaim, (et l'important ici, c'est ad-hoc, pas Klaim ;) ) est aussi une forme d'union particulière qui répond donc à un seul problème bien identifié. C++0x en supprimant beaucoup des contraintes d'une union va probablement rendre les cas d'utilisation de Boost.Variant ou de solutions ad-hoc moins nombreux.

-> Troisième solution : l'effaçage de type : c'est la solution de Boost.Any. On ne sait vraiment plus quel type exactement contient un élément de la liste.

Chacune de ces 3 solutions a un une utilisation particulière selon le niveau d'hétérogénéité que l'on souhaite dans la liste. Et on la choisie en fonction de ça.