IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C++ Discussion :

stocker dans une map avec une clé de type non primitif


Sujet :

C++

  1. #1
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2014
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2014
    Messages : 126
    Points : 48
    Points
    48
    Par défaut stocker dans une map avec une clé de type non primitif
    Bonjour,

    Voici mon problème, j'ai une structure définie comme suit :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    typedef struct 
    {
    	int index;
    	long int capacity;
    } Couple;
    et je voudrais me servir de la map suivante mais je n'y arrive pas :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    std::map<Couple, long int> myMap;
    Le but pour moi est ensuite de faire des find sur les couples pour savoir si j'ai stocké telle ou telle valeur correspondant au couple en question.

    Je remercie ceux qui s'intéresseront à mon problème et proposeraient éventuellement une solution.

  2. #2
    Membre expert
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2011
    Messages
    739
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Juin 2011
    Messages : 739
    Points : 3 627
    Points
    3 627
    Par défaut
    Lu, std::map prend un Compare en paramètre template.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
     
    struct CoupleCompare {
      bool operator()(const Couple & a, const Couple & b) const noexcept
      { return a.index < b.index || (a.index == b.index && a.capacity < b.capacity); }
    };
     
    std::map<Couple, long int, CoupleCompare> myMap;

  3. #3
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2014
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2014
    Messages : 126
    Points : 48
    Points
    48
    Par défaut
    Merci beaucoup de ta réponse, cette partie du code fonctionne. J'ai maintenant un autre problème : j'implémente un algorithme pour résoudre le "knapsack problem".

    J'ai un problème dans la fonction principale :

    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
    long int compute(long int n, long int w, Items& items, std::map<Couple, long int, CoupleCompare>& myMap){
     
    	Couple c =  {n, w};
    	Couple c2 = {n-1, w};
    	Couple c3 = {n-1, w-items[n-1].weight};
     
    	if(myMap.find(c) != myMap.end())
    		return myMap.find(c) -> second;
     
    	if(myMap.find(c2) != myMap.end() and myMap.find(c3) != myMap.end()) {
    		myMap[c] = std::max(myMap.find(c2)->second, myMap.find(c3)->second + items[n-1].value);
    	}
     
     
    	if(w-items[n-1].weight >= 0)
    		return std::max(compute(n-1, w, items, myMap), compute(n-1, w-items[n-1].weight, items, myMap));
     
    	return compute(n-1, w, items, myMap);
    }
    Voici ce que je cherche à faire :

    - si la valeur que je cherche est dans la map alors on la retourne

    -sinon on rajoute dans la map le couple (clé, valeur) suivant : Couple(n, w), max(myMap.find(c2)->second, myMap.find(c3)->second + items[n-1].value)

    -si le poids de mon item est inférieur à la capacité on fait un appel récursif de la fonction sur (n-1, w-items[n-1].weight, items, myMap) et sur (n-1, w, items, myMap)

    sinon seulement sur le deuxieme cas.

    Je poste la totalité du code au cas où, encore merci de votre aide.

    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
    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
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    #include <iostream>
    #include <array>
    #include <string>
    #include <fstream>
    #include <map>
     
    typedef struct 
    {
    	long int value;
    	long int weight;
    } Item;
     
    typedef struct 
    {
    	long int index;
    	long int capacity;
    } Couple;
     
    struct CoupleCompare {
    	bool operator()(const Couple & a, const Couple & b) const noexcept {
    		return (a.index < b.index) || (a.index == b.index && a.capacity < b.capacity);
    	}
    };
     
    typedef std::array<Item, 2000> Items;
     
     
    long int compute(long int n, long int w, std::map<Couple, long int>& myMap, Items& items);
     
     
    Items get_items() {
     
    	Items items;
    	std::string ligne("");
     
    	std::ifstream fichier("knapsack_big.txt");
     
    	if(fichier){
    		getline(fichier, ligne);
    		size_t i(0);
    		while(getline(fichier, ligne)){
    			items[i].value = stoi(ligne.substr(0, ligne.find(' ', 0)));
    			items[i].weight = stoi(ligne.substr(ligne.find(' ', 0), ligne.find(' ', ligne.find(' ', 0) + 1)));
    			i++;
    		}
    	}
     
    	else 
    		std::cerr << "Impossible d'ouvrir le fichier" << std::endl;
     
    	return items;
     
    }
     
    std::map<Couple, long int, CoupleCompare> initialize(){
     
    	std::map<Couple, long int, CoupleCompare> myMap;
     
    	for(long int i(0); i < 2000; i++){
    		Couple c = {0, i};
    		myMap[c] = 0;
    	}
     
    	return myMap;
    }
     
    long int compute(long int n, long int w, Items& items, std::map<Couple, long int, CoupleCompare>& myMap){
     
    	Couple c =  {n, w};
    	Couple c2 = {n-1, w};
    	Couple c3 = {n-1, w-items[n-1].weight};
     
    	if(myMap.find(c) != myMap.end())
    		return myMap.find(c) -> second;
     
    	if(myMap.find(c2) != myMap.end() and myMap.find(c3) != myMap.end()) {
    		myMap[c] = std::max(myMap.find(c2)->second, myMap.find(c3)->second + items[n-1].value);
    	}
     
     
    	if(w-items[n-1].weight >= 0)
    		return std::max(compute(n-1, w, items, myMap), compute(n-1, w-items[n-1].weight, items, myMap));
     
    	return compute(n-1, w, items, myMap);
    }
     
    int main(int argc, char* argv[]){
     
    	Items items(get_items());
     
    	std::map<Couple, long int, CoupleCompare> myMap(initialize());
     
    	std::cout << compute(1999, 2000000, items, myMap);
     
    	return 0;
     
    }

    Pour l'instant j'ai un segmentation fault à l'execution.

  4. #4
    Rédacteur/Modérateur
    Avatar de JolyLoic
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Août 2004
    Messages
    5 463
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Août 2004
    Messages : 5 463
    Points : 16 213
    Points
    16 213
    Par défaut
    Citation Envoyé par jo_link_noir Voir le message
    Lu, std::map prend un Compare en paramètre template.
    Ou bien, si la classe servant de clef possède un ordre naturel, on peut lui définir un operator<, qui sera pris en compte par défaut dans toutes les maps et autres structures pour lesquelles la comparaison a du sens.

    Citation Envoyé par ImmoTPA Voir le message

    Pour l'instant j'ai un segmentation fault à l'execution.
    Tu as une fonction qui s'appelle elle-même 2000 fois. Même si en théorie, ça n'a rien de gênant (et qu'en théorie, il n'y au aucune différence entre la théorie et la pratique ) l'espace mémoire réservé à l'empilement des paramètres de fonction et des variables locales est généralement assez réduit. Il vaudrait mieux que tu réécrives l'algorithme en le dé-récursivant pour voir.

    Sinon, on notera plus souvent :
    class A {...}; ou struct S { ... }; que typedef struct {...} S;, c'est une notation héritée du C est très très rarement utilisée en C++.
    Ma session aux Microsoft TechDays 2013 : Développer en natif avec C++11.
    Celle des Microsoft TechDays 2014 : Bonnes pratiques pour apprivoiser le C++11 avec Visual C++
    Et celle des Microsoft TechDays 2015 : Visual C++ 2015 : voyage à la découverte d'un nouveau monde
    Je donne des formations au C++ en entreprise, n'hésitez pas à me contacter.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Réponses: 1
    Dernier message: 13/04/2015, 12h17
  2. [XL-2002] Macro de comparaison d'une cellule d'une feuille avec une cellule d'une autre feuille.
    Par steelydan dans le forum Macros et VBA Excel
    Réponses: 6
    Dernier message: 08/09/2010, 13h59
  3. Réponses: 8
    Dernier message: 27/08/2008, 19h36
  4. Réponses: 3
    Dernier message: 06/11/2007, 12h18
  5. [html] non reconnaisance d'une Map d'une image avec IE
    Par mathieu dans le forum Balisage (X)HTML et validation W3C
    Réponses: 2
    Dernier message: 30/08/2005, 11h42

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo