Implémentation d'une table de hachage à référence faible avec Qt

Version imprimable

07/03/2012, 09h51
dourouc05

Implémentation d'une table de hachage à référence faible avec Qt
Une table de hachage à référence faible contient des paires clé-valeur sans que l'on puisse les atteindre. On en recense quatre types :
- la clé est une référence faible ;
- la valeur est une référence faible ;
- la clé ou la valeur est une référence faible ;
- la clé et la valeur sont des références faibles.
Dans cet article, on propose une implémentation basée sur Qt pour le second type : une table de hachage où la valeur est une référence faible. Ceci signifie qu'une paire clé-valeur sera automatiquement enlevées de la table dès que la valeur ne sera plus utilisée dans le programme.

Ce type de structure est utile pour réduire l'utilisation mémoire en partageant les structures de données sans fuite de mémoire.

Implémentation d'une table de hachage à référence faible avec Qt

Rigolo.

Pour comparaison, voici une version 100% standard (2011), qui n'exige rien de particulier sur les valeurs (i.e. elles peuvent aussi être des entiers)

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
// (c) Luc Hermitte, 2012, licence: BSL
#include <cassert>
#include <unordered_map>
#include <vector>
#include <functional>
#include <memory>
#include <string>
#include <iostream>
 
#if defined(__GNUC__) && __GNUC__ >= 4 && __GNUC_MINOR__ >= 6
#   define HAS_RANGE_BASED_FOR
#endif
 
struct DeleterNotifier {
    typedef std::function<void()> Listener_t;
    typedef std::vector<Listener_t> ListenerList_t;
 
    DeleterNotifier() {}
    template <typename Holded_>
    void operator()(Holded_ const* p) {
#if defined(HAS_RANGE_BASED_FOR)
        for ( auto l : m_listeners) l();
#else
        for (ListenerList_t::const_iterator b = m_listeners.begin(), e = m_listeners.end()
                ; b != e
                ; ++b
            )
        {
            (*b)();
        }
#endif
        std::cout << "deleting " << *p << " present in " << m_listeners.size() << " maps\n";
        delete p;
    }
    template <typename Listener_> void add_listener(Listener_ l_) {
        m_listeners.push_back(l_);
    }
private:
    ListenerList_t  m_listeners;
};
 
template <typename Key_, typename Holded_, typename PKey_>
void insert(
        std::unordered_map<Key_, std::weak_ptr<Holded_>> & map_,
        PKey_ const& key_,
        std::shared_ptr<Holded_> & value_) 
{
    assert(value_);
    const auto wh = map_.insert(std::make_pair(key_, value_));
    DeleterNotifier * deleter = std::get_deleter<DeleterNotifier>(value_);
    if (deleter) {
        assert(deleter);
        deleter->add_listener( [&]{ 
                map_.erase(key_);
                // map_.erase(wh.first); // insert invalidates unordered_map::iterator s 
                });
    }
}
 
typedef std::unordered_map<std::string, std::weak_ptr<int>> Map;
typedef std::shared_ptr<int> sptr_t;
 
template <typename T, class... Args> std::shared_ptr<T> make_shared(Args&& ... args) {
    return std::shared_ptr<T>(new T(args...), DeleterNotifier());
}
 
int main()
{
    Map map1;
    Map map2;
 
    {
        sptr_t sp0;
        {
            sptr_t sp1 = make_shared<int>(42);
            sp0 = sp1;
            insert(map1, ("toto"), sp1);
            // Q: will this always impact sp0 deleter ?
            // A: it seems so: §20.7.2.2.10/9,13,18,...
 
            sptr_t sp2 = make_shared<int>(22);
            insert(map1, ("titi"), sp2);
            insert(map2, ("titi"), sp2);
 
            std::cout << map1.size() << "\n";
            std::cout << map2.size() << "\n";
        }
        std::cout << map1.size() << "\n";
        std::cout << map2.size() << "\n";
    }
    std::cout << map1.size() << "\n";
    std::cout << map2.size() << "\n";
 
    return 0;
}

NB: C'est facile à étendre aux autres conteneurs en spécialisant la callback positionnée dans fonction insert().

17/03/2012, 01h00
Troudhyl

En réponse à votre "rigolo", l'avantage c'est que le code Qt reste lisible (se lit presque aussi bien que de l'algorithmie), en écartant notamment l'usage des templates. C'est un avis personnel car je n'ai pas appris le C++ standard, à la base je viens du Java.

En utilisant une "key" QVariant à la place de QString le résultat aurait été le même pour ce qui est du support des types de base. Après en interne Qt utilise une implémentation à base de templates forcément donc rien n'empêche de créer une classe dans son style en utilisant votre code, c'est sûrement ce qui serait fait si une classe QWeakHash officielle voyait le jour.
17/03/2012, 03h43
Luc Hermitte

Pour la lisibilité, c'est une question de goût. Je ne cache pas ma préférence pour le C++ standard au style Qt, ou plus exactement aux choix de design.

Ce n'est pas la clé qui doit être variant pour supporter les types de base, mais la value/element associé à la clé. Mais j'imagine qu'un QVariant est de nouveau la réponse, la table a besoin de cela pour pouvoir écouter la notification de destruction de l'objet stocké (et non de la clé).

C'est là que la différence de philosophie s'opère. Mon approche, qui requiert le standard 2011 du C++, détourne la destruction de l'objet référencé par les shared_ptr (smart pointer à comptage de référence) pour en plus réagir à ce moment là et retirer le weak_ptr de la table. En procédant de la sorte, on n'impose aucune contrainte sur le type des éléments, on a ainsi un bien meilleur typage que dans le cas où l'on manipule des QVariant.

Autres aspects très importants, on n'a pas besoin de redéfinir une nouvelle série de tables WeakOrderedMap, WeakHashMap, WeakOrderedMultimap, etc. La différence à chaque fois c'est une fonction et une seule pour chaque table.
NB: il y a toutefois une faille : en cas de copie/transformation de la table, il faut dupliquer les callbacks. J'étais parti, à tord, de l’hypothèse que la table a une durée de vie maximale.
17/03/2012, 13h10
Troudhyl

Oui pardon je me suis embrouillé, c'est la value qui nous intéresse pas la clé, QVariant n'est pas une réponse convenable et il faudrait recourir aux templates pour accepter de tout, c'est sûr. Pour une implémentation de classe officielle Qt c'est inévitable, mais pour une utilisation plus spécifique on pourra l'éviter et traiter des QObject* ou QVariant.

Peut-être un article qui peut vous intéresser : http://qt.developpez.com/doc/latest/templates/
23/03/2012, 23h24
Matthieu Brucher

Ce qui m'embête un peu, c'est le côté non thread-safe, il me semble ? Sinon, c'est un bel exercice de style Qt.
08/08/2018, 12h49
ramislebob

Pour ceux que ça intéresse, m'étant inspiré du post initial j'ai implémenté l'équivalent java d'une WeakHashMap<SharedObject, WeakReference<SharedObject>>
La clef et la valeur de ma map sont une weak référence sur l'objet à partager. En fait la clef est un wrapper sur la weak référence permettant de définir la fonction de hachage et l'opérateur d'égalité qui utiliseront la valeur réelle de l'objet (si celui ci existe encore)

Vous pouvez trouver cette implémentation ici (j'ai appelé ça CentralizingWeakCache). Il y a un cas simple d'utilisation dans le main. Le but étant de pouvoir customiser le SharedObject qui dans l'exemple ne contient qu'un QString.

(cela fait aussi suite à ce thread sur le forum QT.