Discussion :

[CptPingu]

Bonjour.

Je galère depuis un moment sur comment effacer un élément spécifique d'un std::unordered_multimap. Je n'ai malheureusement trouvé ma réponse ni dans la documentation, ni sur le net. Je précise que je travaille en C++0x.

Je m'explique: Dans un std::unordered_multimap, lorsque l'on a des collisions sur un index, celles-ci sont mises dans une liste associée à l'index (le bucket). Or j'ai bien trouvé une méthode "erase" qui efface un index et le premier élément du bucket, mais impossible de trouver comment supprimer un élément choisi au sein de ce bucket.

J'ai écrit un exemple minimaliste, qui montre le problème auquel je suis confronté:

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
#include <iostream>
#include <unordered_map>
 
typedef std::unordered_multimap<uint32_t, std::string> hash_type;
 
namespace
{
  void
  eraseFromBucket(int key, hash_type& hash, const std::string& element)
  {
    auto bucket = hash.bucket(key);
    auto end = hash.cend(bucket);
    for (auto it = hash.cbegin(bucket); it != end; ++it)
    {
      if (it->second == element)
      {
	//hash.erase(it); // Je recherche une méthode qui supprime un élement d'un bucket !
	std::cout << "Dans le bucket " << it->first << ", supprimer l'element " << it->second << std::endl;
	return; // Return, iterators are now invalidated.
      }
    }
  }
 
  void
  display(const hash_type& hash)
  {
    auto end = hash.cend();
    for (auto it = hash.cbegin(); it != end; ++it)
      std::cout << it->first << " => " << it->second << std::endl;
  }
} // namespace
 
int main()
{
  hash_type hash;
 
  hash.insert(hash_type::value_type(1, "toto"));
  hash.insert(hash_type::value_type(2, "tutu"));
  hash.insert(hash_type::value_type(2, "tata"));
  hash.insert(hash_type::value_type(2, "titi"));
 
  std::cout << "Before" << std::endl;
  display(hash);
 
  eraseFromBucket(2, hash, "titi");
 
  std::cout << "After" << std::endl;
  display(hash);
 
  // auto it = hash.find(2);
  // hash.erase(it);
  // Supprimera le premier élément du bucket 2, "tutu"
 
  return 0;
}

Merci.

[CptPingu]

J'ai trouvé une solution, mais je doute fortement de sa propreté.
- Je recherche le premier élément du bucket.
- Je recherche mon élément au sein du bucket.
- Je prend la distance entre le début du bucket et l'élément trouvé.
- J'avance l'iterator principal pour l'ajuster sur l'élément trouvé.
- Je supprime l'élément.

Ce qui donne:

auto find_iter = hash.find(key);
std::advance(find_iter, std::distance(hash.cbegin(bucket), it));

N'y aurait-il pas une meilleure solution ? Cette solution est-elle fiable ?

Le code modifié:

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
#include <iostream>
#include <unordered_map>
#include <cassert>
 
typedef std::unordered_multimap<uint32_t, std::string> hash_type;
 
namespace
{
  void
  eraseFromBucket(int key, hash_type& hash, const std::string& element)
  {
    auto find_iter = hash.find(key);
    assert(find_iter != hash.end());
 
    auto bucket = hash.bucket(key);
    auto end = hash.cend(bucket);
    for (auto it = hash.cbegin(bucket); it != end; ++it)
    {
      if (it->second == element)
      {
	std::advance(find_iter, std::distance(hash.cbegin(bucket), it));
	std::cout << "Dans le bucket " << it->first << ", supprimer l'element " << it->second << std::endl;
	hash.erase(find_iter);
	return;
      }
    }
 
    assert(false);
  }
 
  void
  display(const hash_type& hash)
  {
    auto end = hash.cend();
    for (auto it = hash.cbegin(); it != end; ++it)
      std::cout << it->first << " => " << it->second << std::endl;
  }
} // namespace
 
int main()
{
  hash_type hash;
 
  hash.insert(hash_type::value_type(1, "toto"));
  hash.insert(hash_type::value_type(2, "tutu"));
  hash.insert(hash_type::value_type(2, "tata"));
  hash.insert(hash_type::value_type(2, "titi"));
 
  std::cout << "Before" << std::endl;
  display(hash);
 
  eraseFromBucket(2, hash, "titi");
 
  std::cout << "After" << std::endl;
  display(hash);
 
  return 0;
}

[dyslesia]

Bonjour,

ce qui me viendrais a l'esprit serait de parcourir le bucket en question, et de sauvegarder une copie de chaque élément de ce bucket, excepté l'élément recherché, et ensuite remplacer le bucket par le nouveau.
C'est certainement fiable mais pas très propre

[CptPingu]

Merci dyslesia pour ta réponse.

Néanmoins, je préfére tout de même utiliser la seconde méthode que j'ai décrite, puisqu'elle n'implique pas de copie, juste un iterateur supplémentaire.
Je reste intéressé, par une méthode permettant de supprimer directement un élément d'un bucket, sans utiliser de hack.

[JolyLoic]

Je ne comprends pas ton problème... unordered_multimap possède une fonction erase prenant en paramètre un itérateur.

[Arzar]

Bonjour,

CptPingu, je crois que tu fais une grosse confusion sur ce qu'est un "bucket" dans la terminologie des tables de hashage.

Un "bucket" ne contient pas du tout l'ensemble des éléments qui ont la même clé.

Comme le dit Loïc, pour effacer un élément de la multimap il suffit d'utiliser la fonction membre erase() qui prendra en paramètre un iterateur pointant sur la paire clé-valeur que tu veux supprimer.

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
 
#include <iostream>
#include <unordered_map>
#include <cassert>
#include <tuple>
#include <string>
 
 
typedef std::unordered_multimap<int, std::string> hash_type;
 
void eraseFromBucket(hash_type& hash, int key, const std::string& element)
{
  // equal_range permet de récupérer une paire d'itérateur représentant 
  // un intervalle des paires clé-élément ayant la même clé.
   hash_type::iterator firstSameKey, lastSameKey;
   std::tie(firstSameKey, lastSameKey) = hash.equal_range(key);
 
   // Puis on cherche dans cet intervalle la paire 
   // contenant l'élément voulu
   for(auto itFound = firstSameKey; itFound != lastSameKey; ++itFound )
   {
      if (itFound ->second == element)
      {
         // si on trouve la bonne paire, on l'efface
         hash.erase(itFound );
         return;
      }
   }
}
 
 
void display(const hash_type& hash)
{
   auto end = hash.cend();
   for (auto it = hash.cbegin(); it != end; ++it)
      std::cout << it->first << " => " << it->second << std::endl;
}
 
 
int main()
{
  hash_type hash;
 
  hash.insert(hash_type::value_type(1, "toto"));
  hash.insert(hash_type::value_type(2, "tutu"));
  hash.insert(hash_type::value_type(2, "tata"));
  hash.insert(hash_type::value_type(2, "titi"));
 
  std::cout << "Before" << std::endl;
  display(hash);
 
  eraseFromBucket(hash, 2, "titi");
 
  std::cout << "After" << std::endl;
  display(hash);
 
  return 0;
}

[CptPingu]

Je ne comprends pas ton problème... unordered_multimap possède une fonction erase prenant en paramètre un itérateur.

Je pense avoir mal saisie l'utilisation de ce conteneur. Néanmoins, lorsque j'ai itéré sur un sous ensemble, je me suis retrouvé avec un iterator incompatible avec erase (un const_local_iterator). D'où mon interrogation (et mon hack bancal).

CptPingu, je crois que tu fais une grosse confusion sur ce qu'est un "bucket" dans la terminologie des tables de hashage.
Un "bucket" ne contient pas du tout l'ensemble des éléments qui ont la même clé.

Je pense effectivement n'avoir pas compris la notion de bucket. Pourrais-tu m'expliquer cette notion, ou m'orienter vers une bonne documentation qui explique ce concept ? Comme dit dans mon premier post, je n'ai pas réussi à trouver une documentation explicative suffisante.

Si un bucket ne représente pas la table de collision d'une clé, alors à quoi servent:
- size_type bucket(const key_type& k) const;
- local_iterator begin(size_type n);

En tout cas, je te remercie pour la solution. J'avais l'intuition que ma solution n'était pas la bonne, mais je ne savais pas comment résoudre mon problème.