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:

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:

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.

Lu, std::map prend un Compare en paramètre template.

Code:

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;

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:

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:

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.

Citation:

Envoyé par jo_link_noir

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

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 :P) 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++.