[Tri] Tableau de structures

Version imprimable

27/11/2007, 10h21
Arnaud F.

[Tri] Tableau de structures
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:

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).

:merci:

Ce serait pas plus simple si tu faisais

Code:

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} };

27/11/2007, 13h40
Arnaud F.
Citation:
Envoyé par loufoque

Ce serait pas plus simple si tu faisais

Code:

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?
27/11/2007, 14h06
yan
avec une multi map peut etre:
Code:

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 ???
27/11/2007, 14h12
Arnaud F.
Citation:
Envoyé par Mongaulois

avec une multi map peut etre:

Code:

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 :lol:, je suis en stage ;)

Vais regarder du côté de multimap :)

:merci:

[edit] T'aurai pas un tutoriel sur les map et multimap?
27/11/2007, 14h24
yan

Citation:

Envoyé par buchs

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

Google :aie:
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
27/11/2007, 14h26
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.)

:merci: beaucoup :)

[edit]

Citation:

Envoyé par Mongaulois

Google :aie:
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?
27/11/2007, 14h32
yan

Citation:

Envoyé par buchs

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?).

C'est ce qui me semble aussi

Citation:

Envoyé par buchs

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

regarde les fonctions sur ce site
http://www.cplusplus.com/reference/stl/multimap/

Sinon si c'est juste pour les ajouter et les trier une seul fois, la map n'est sûrement pas adapté a ton problème. Dans ce cas il serait mieux d'avoir une structure, une vector sur cette structure et un foncteur pour le trie

[edit]
http://cpp.developpez.com/faq/cpp/?p...hoix_conteneur
http://cpp.developpez.com/faq/cpp/?p...TL_custom_sort
27/11/2007, 14h38
Arnaud F.

Citation:

Envoyé par Mongaulois

Sinon si c'est juste pour les ajouter et les trier une seul fois, la map n'est sûrement pas adapté a ton problème. Dans ce cas il serait mieux d'avoir une structure, une vector sur cette structure et un foncteur pour le trie

Non, ça sera trié constamment, suffit de faire une opération sur la matrice (genre +) pour que de nouvelles valeurs apparaissent dedans et d'autres supprimées. Donc je pense que la map me m'économisera pas mal de ressources de ce côté :)

Concernant le site sur les multimap, j'en viens justement.

Et nos posts se sont croisés, donc je sais pas si t'as vu, mais je demandais quelle était la différence entre une map et une multimap?

:merci: beaucoup en tout cas :)

[edit] J'ai déjà épluché la FAQ :)
27/11/2007, 15h34
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:

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 :aie:

Z'avez des suggestions?
27/11/2007, 15h49
yan
Citation:

Envoyé par buchs

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

Citation:

Envoyé par buchs

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:

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 :aie:

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:

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) );
27/11/2007, 16h05
Arnaud F.

Citation:

Envoyé par Mongaulois

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) );

:merci: :hola:
27/11/2007, 16h24
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:

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

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 :aie:

D'où peut provenir l'erreur?
27/11/2007, 16h37
yan
si c'est dans la fonction

Code:

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:

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()
27/11/2007, 16h38
Arnaud F.
Citation:
Envoyé par Mongaulois

si c'est dans la fonction

Code:

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:

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()
T'es un chef, ça fonctionne :hola: