Discussion :

[Arnaud F.]

Bonjour,

je suis actuellement sur l'implentations de matrices creuses, j'ai donc trois tableaux, le premier correspondant aux valeurs non nulles de la matrice, le second correspondant au numéro des lignes sur lesquelles ce trouvent les valeurs et un tableau de colonnes où se trouvent les valeurs.

Pour être plus clair, voici un exemple (pour une Matrice(3, 3)):

Code :

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

1
2
3
4
 
double val[2]= {1, 0.5};
int lig[2]= {0, 1};
int col[2]= {1, 0};

Ce qui représente la matrice :
0 1
0.5 0

Bref, ça fonctionne par couple de valeur en fonction de l'indice du tableau.

Et j'aimerais savoir comment trier ces tableaux en fonction de lig, puis de col. Tout en laissant les couples de valeurs intacts...

Exemple:

double val[4]= {2, 3, 1, 4};
int lig[4]= {0, 1, 0, 1};
int col[4]= {1, 0, 0, 1};

l'état des tableaux après le tri devra donc être le suivant :
double val[4]= {1, 2, 3, 4};
int lig[4]= {0, 0, 1, 1};
int col[4]= {0, 1, 0, 1};

Je ne sais pas trop comment faire (je peux passer par des structures, j'aurai donc un tableau de structures).

[loufoque]

Ce serait pas plus simple si tu faisais

Code :

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

1
2
3
4
5
6
7
8
struct point
{
   int ligne;
   int colonne;
   double valeur;
};
 
point val[2] = { {0, 1, 1.0}, {1, 0, 0.5} };

?

[Arnaud F.]

Ce serait pas plus simple si tu faisais

Code :

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

1
2
3
4
5
6
7
8
struct point
{
   int ligne;
   int colonne;
   double valeur;
};
 
point val[2] = { {0, 1, 1.0}, {1, 0, 0.5} };

?

Si et c'est que j'avais commencé à faire

Par contre, je ne sais pas comment trier cette structure après. (Je suis en train de regarder du côté de sort et je pense avoir trouvé mon bonheur).

Seulement, je trouve la conversion de tableau-> vecteur<struct> -> tableau lourde... Y a pas moyen d'optimiser la chose?

[yan]

avec une multi map peut etre:

Code :

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

1
2
 
std::multimap<double ,std::pair<int,int> >

ainsi ta map sera trié en fonction de la valeur et la valeur sera associé à une position
Ce ne serait pas le même exo que http://www.developpez.net/forums/sho...d.php?t=447046 ???

[Arnaud F.]

avec une multi map peut etre:

Code :

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

1
2
 
std::multimap<double ,std::pair<int,int> >

ainsi ta map sera trié en fonction de la valeur et la valeur sera associé à une position
Ce ne serait pas le même exo que http://www.developpez.net/forums/sho...d.php?t=447046 ???

Du tout , je suis en stage

Vais regarder du côté de multimap



[edit] T'aurai pas un tutoriel sur les map et multimap?

[yan]

T'aurai pas un tutoriel sur les map et multimap?

Google
La multimap est une map où il peut y avoir une clef associé a plusieurs éléments.
tu peut te baser sur la faq pour commencer.
http://cpp.developpez.com/faq/cpp/?page=STL
et ce site
http://www.cplusplus.com/reference/stl/multimap/

Comprend tu le concept de map? je pense que oui mais on ne sait jamais

[Arnaud F.]

J'ai quelques recherches complémentaires sur les map (tout court) et c'est vrai que ça peut être intéressant de procéder de la sorte (ça me fait juste réorganiser tout le code existant ).

Donc si je fais une map avec une paire d'entier pour la clé (les coord.) et un double pour la valeur (la valeur de mon élément ds la matrice), ça allegerait pas mal le code .

Si je passe par cette méthode, j'aurai pas besoin d'écrire de foncteur, ou bien? (il triera en fonction du premier élément, puis du second, non?).

Troisièmement, comment utilise t'on se genre de map? (pour insérer une valeur, la supprimer, etc.)

beaucoup

[edit]

Google
La multimap est une map où il peut y avoir une clef associé a plusieurs éléments.
tu peut te baser sur la faq pour commencer.
http://cpp.developpez.com/faq/cpp/?page=STL
et ce site
http://www.cplusplus.com/reference/stl/multimap/

Comprend tu le concept de map? je pense que oui mais on ne sait jamais

Oui je connais le principe de map (tri auto et tout).

Par contre, pourquoi une multimap et pas une simple map?

[Arnaud F.]

Mon choix se porte donc sur une map et non une multimap (normalement, les clés sont unique puisqu'on ne peux avoir qu'une valeur par coordonnées ).

Je commence donc à coder, mais je bloque sur l'insertion d'une valeur dans la matrice
Dans mon .h : map<pair<int, int>, double> valeurs;
Je fais :

Code :

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

valeurs.insert(make_pair(0, 0), 1.0);

Mais ça ne compile pas

J'en déduis que c'est pas comme ça que l'on insère

Z'avez des suggestions?

[yan]

Mon choix se porte donc sur une map et non une multimap (normalement, les clés sont unique puisqu'on ne peux avoir qu'une valeur par coordonnées ).

Si se sont les coordonné, oui c'ets plustôt une map

ommence donc à coder, mais je bloque sur l'insertion d'une valeur dans la matrice
Dans mon .h : map<pair<int, int>, double> valeurs;
Je fais :

Code :

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

valeurs.insert(make_pair(0, 0), 1.0);

Mais ça ne compile pas

J'en déduis que c'est pas comme ça que l'on insère

Z'avez des suggestions?

en faite une map c'est un ensemble de pair.
Donc ici ce qui est stocké est une pair constituer de :
- pair<int,int>
- double
voici deux façon d'ajouter un élément a la map

Code C++ :

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

1
2
3
std::map<std::pair<int, int>, double>  mymap;
mymap[std::make_pair(10,10)]=10;
mymap.insert(std::make_pair( std::make_pair(11,10),20) );

[Arnaud F.]

Si se sont les coordonné, oui c'ets plustôt une map

Je c
en faite une map c'est un ensemble de pair.
Donc ici ce qui est stocké est une pair constituer de :
- pair<int,int>
- double
voici deux façon d'ajouter un élément a la map

Code C++ :
std::map<std::pair<int, int>, double> mymap;
mymap[std::make_pair(10,10)]=10;
mymap.insert(std::make_pair( std::make_pair(11,10),20) );

[Arnaud F.]

Bon, je me permets juste de poster à la suite car j'ai un léger souci d'itérateur... (dans une fonction amie)

Prototype :

Code :

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

1
2
 
ostream & operator<<(ostream & o, const MatriceCreuse & mc);

Code :

Code :

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

1
2
    map<pair<int, int>, double>::iterator it;
    /*it=*/ mc.valeurs.find(make_pair(0, 0));

En commentant l'affectation, le programme compile, en décommentant, ça ne compile pas. J'ai copié ce bout de code dans une fonction de la classe et ça passe sans souci

D'où peut provenir l'erreur?

[yan]

si c'est dans la fonction

Code :

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

ostream & operator<<(ostream & o, const MatriceCreuse & mc);

je pense que c'est du au fait que mc est const. Il faut donc un const_iterator

Code :

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

1
2
map<pair<int, int>, double>::const_iterator it;
it= mc.valeurs.find(make_pair(0, 0));

Juste pour savoir pourquoi fait tu un find(make_pair(0, 0))??
si c'est pour parcourir la map faut plustôt utiliser les iterators fournie par les méthodes begin() et end()