Discussion :

[valefor]

Bonjour.

Je stocke des (cléf/valeur)s dans une std::map. J'ai un traitement qui s'intéresse à une clef et à ses voisines.

Je cherche le meilleur moyen de récupérer un itérateur sur des clefs voisines sans avoir à faire un map->find() pour chaque voisine.

Je pensais pouvoir faire une recherche en spécifiant une plage, par exemple :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
int clef_triees[7] = {4, 6, 13, 16, 18, 24, 40};
 
// je dispose d'un iterateur initial sur la clef 16 : it_init
 
it_13 = map->find(13, map->begin(), it_init - 1);
it_6 = map->find(6, map->begin(), it_13 - 1);
it_4 = map->find(4, map->begin(), it_6 - 1);
 
it_18 = map->find(18, it_init + 1, map->end());
it_24 = map->find(24,it_18 + 1, map->end());
it_40 = map->find(40, it_24 + 1, map->end());

Si la recherche est dochotomique cela peut faire gagner un peu de temps. Mais je ne trouve pas de fonction qui permette de faire ça.

Je me demande si c'est utile de vouloir optimiser cela, et si oui comment le faire ?

[Nogane]

Bonjour.
Je pense que pour cela, il faudrait utiliser un std::vector trié, plutôt qu'une map.
(Tien, il me semble avoir vu ça dans Folly)

[Arzar]

J'ai un traitement qui s'intéresse à une clef et à ses voisines.

Bonjour,
Je ne suis pas bien sur de comprendre exactement ce que désigne les "voisines d'une clé". Est-ce que le code suivant correspond ?

Code :

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

1
2
3
4
5
std::map<int, int>::iterator it_init = m.find(16);
std::map<int, int>::iterator it_18 = std::next(it_init, 1);
std::map<int, int>::iterator it_13 = std::prev(it_init, 1);
std::map<int, int>::iterator it_24 = std::next(it_init, 2);
std::map<int, int>::iterator it_6  = std::prev(it_init, 2);

Remarque : le code ci-dessus nécessite un compilateur relativement récent (C++11). Sur des compilateurs plus vieux il faut faire :

Code :

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

1
2
std::map<int, int>::iterator it_6 = it_init;
std::advance(it_6, -2);

[valefor]

Bonjour,
Est-ce que le code suivant correspond ?

Code :

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

1
2
3
4
5
std::map<int, int>::iterator it_init = m.find(16);
std::map<int, int>::iterator it_18 = std::next(it_init, 1);
std::map<int, int>::iterator it_13 = std::prev(it_init, 1);
std::map<int, int>::iterator it_24 = std::next(it_init, 2);
std::map<int, int>::iterator it_6  = std::prev(it_init, 2);

Non, cela ne convient pas car je ne sais pas combien de paires ont été insérées entre la clef 16 et 13 par exemple. Ce sont des voisines au sens géographiques car ces cléf représentent des lieux voisins sur une carte...

En fait c'était sous mes yeux : lower_bound fait aussi l'affaire pour ça

Désolé pour le bruit

[Bousk]

Bonjour,

Il va te falloir faire en sorte que les voisines géographiques se retrouvent voisines au sens représentation en mémoire.
Sinon, je ne vois pas par quel miracle tu peux réaliser ce genre d'opérations.

[jblecanard]

Bonjour,

Il va te falloir faire en sorte que les voisines géographiques se retrouvent voisines au sens représentation en mémoire.
Sinon, je ne vois pas par quel miracle tu peux réaliser ce genre d'opérations.

Je pense qu'il s'agit de voisines au sens de la relation d'ordre utilisée sur les clés, et pas en mémoire.

[Bousk]

Je pense qu'il s'agit de voisines au sens de la relation d'ordre utilisée sur les clés, et pas en mémoire.

Tu joues sur les mots, mais oui c'est l'idée et c'est exactement ce que j'ai dit.

Si dans ta map tes voisins géographiques ne sont pas voisins de clé, tu ne t'en sortiras jamais.