Extraire tous les k de tous les éléments <i,j,k> d'une std::map

Version imprimable

Bonjour,

Voici le problème! J'ai un std::map dont je souhaiterais extraire certaines valeurs. Sa clé principale est de la forme <i,j,k> tandis que la valeur qui lui est associée est de type booléenne.
Je souhaiterais extraire de ce std::map, tous les triplets <i,j, * > avec i,j constant.
Code:

1 2 3 4 5 6 7 8 Exemple: ... <1,2,4>, true <1,3,2>, true <1,3,5>, false <1,3,12>, true <2,5,0>,true ...
Je souhaiterias extraire les triplets <1,3,*>. Je devrais donc obtenir la liste:
2 (true), 5(false), 12(true). Pour simplifier le problème, je ne suis pas intéressé par les valeurs booléennes pour le moment.

Voici le code que j'ai tenté d'écrire!
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 struct triple_type{ int i; int j; int k;}; int i=1; int j=3; bool continue=true; std::vector<I> list; do { std::map<triple_type, bool, ...>::const_iterator iter = data_->find(triple_type(i,j,???); //incomplet!!! if(iter != data_->end()) list.push_back(iter->first.k); // we found it else continue = false; ///if (iter->first.i == i && iter->first.j == k) } while(continue);
Soit ça marche pas, je patauge complètement :)

Je vous remercie par avance.
Cordialement,
Rodrigue

10/10/2006, 18h25
JolyLoic

Citation:

Envoyé par Rodrigue

std::map<triple_type, bool, ...>::const_iterator iter = data_->find(triple_type(i,j,???); //incomplet!!!
[/CODE]

find te retourne un élément dont tu connais la clef. Ce n'est pas le cas ici. Il ne te reste qu'à itérer sur les tous éléments de ta map pour trouver les bons (éventuellement avec l'aide de std::find_if).

Par contre, tu perds tous les avantages d'organisation de stockage de ta map. Si c'est une opération que u vas réaliser souvent, il vaudrait mieux utiliser une autre structure de données, comme par exemple boost::multi_index (bon courage, c'est un peu moins intuitif que std::map à utiliser).
10/10/2006, 19h49
Rodrigue

En fait j'utilise, stxxl au lieu de la librairie std... stxxl::map et std::map s'utilise de la même manière. La solution de boost n'est pas possible car mes structures de données sont trop grandes. Je n'ai accès qu'à des deque, queue, map et vector. La solution serait d'avoir un multimap :)
ou alors que j'arrive à comprendre comment écrire un nouveau manageur de mémoire pour la std, je sais que c'est possible de le passer en paramètre lors de la construction... Il faudrait pour bien faire que tout soit stocker sur le disque dur au lieu de la RAM (pour simplifier, sinon il faut jouer avec de la mémoire cache, j'avais commencé, j'ai déjà créer des classes pour me servir de la mémoire virtuelle, mais je ne suis jamais arrivé à créer le manageur de mémoire -> si qqun connaît la solution, ça m'intéresse énormément! <-).

Enfin je suppose qu'il est possible d'écrire un algorithme assez rapide pour extraire les données de ma map. Je le vois comme ça:
//tous les éléments d'une map sont classés du plus petit au plus grand (dans stxxl, on passe dans le constructeur de la map, une fonction de comparaison sur les clés donc je suis sûr et certain que c'est comme ça).

- trouver le premier élément <1,3,firstindex>
- ensuite on passe à l'élément suivant TANT QU'on se trouve toujours sur un triplet de type <1,3,*>

La seconde étape, doit sûrement se coder comme une incrémentation d'un pointeur sur la structure, certainement sur un itérateur. La première par contre, je ne vois vraiment pas comment faire!

Lancez des idées svp!
10/10/2006, 20h26
JolyLoic

Si c'est toujours k qui est inconnue, ça simplifie effectivement les choses.

Un truc genre maMap.lower_bound(triple_type(i, j, numeric_limits<int>::min()); doit te retourner le premier élément que tu veux, et temps logarithmique, ensuite, il ne te reste plus qu'à itérer jusqu'à avoir des [i, j] différents.

voila si ca te vas ;)

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
 
 
class triple_type
{
	public:
	int i;
	int j;
	int k;
	triple_type():i(0),j(0),k(0){};
	triple_type(int _i,int _j, int _k):i(_i),j(_j),k(_k){};
 
};
 
struct lttriplet
{
  bool operator()(const triple_type & s1, const triple_type& s2) const
  {
  	if(s1.i<s2.i) return true;
  	if(s1.j<s2.j) return true;
  	if(s1.k<s2.k) return true;
  	return false;
  }
};
 
 
int main()
{
 
	map<triple_type, bool,lttriplet> m;
	map<triple_type, bool,lttriplet>::iterator it;
	list<triple_type> l;
 
	triple_type test(1,3,-1);
 
 
	m[triple_type(1,2,4)]=true;
	m[triple_type(1,3,2)]=true;
	m[triple_type(1,3,5)]=false;
	m[triple_type(1,3,12)]=true;
	m[triple_type(2,5,0)]=true;
 
 
	for(it=m.begin();it!=m.end();++it)
	{
		if(((*it).first.i==test.i)&&((*it).first.j==test.j))cout<<(*it).first.k<<endl;
	}
 
	std::cout << "Hello world!" << std::endl;
	return 0;
}

10/10/2006, 23h55
JolyLoic

La solution que tu proposes n'est pas très efficace, elle est en O(N) (N nombre total d'éléments insérs), alors que la mienne est en O(ln(N)*K) (K nombre d'éléments à trouver). Vu qu'il a des jeux de donnée suffisemment grands pour ne pas pouvoir tenir en mémoire, je pense que la différence est cruciale.
11/10/2006, 19h46
Rodrigue

Super! Merci beaucoup, ça fonctionne :D
Mille fois merci...
15/10/2006, 21h06
epsilon68

quoi qui fonctionne ? lequel algo ?
16/10/2006, 09h54
Rodrigue

La solution proposée par JolyLoic (O(n l(n)).
16/10/2006, 16h35
epsilon68

c'est clair ;)