+ Répondre à la discussion Actualité déjà publiée
  1. #1
    Responsable Qt


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherches
    Inscrit en
    août 2008
    Messages
    22 140
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : Ingénieur de recherches
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 22 140
    Points : 119 117
    Points
    119 117

    Par défaut 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
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions) ? Contactez-moi par MP.

    Nouveau ! Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  2. #2
    Expert éminent
    Avatar de Luc Hermitte
    Homme Profil pro
    Développeur informatique
    Inscrit en
    août 2003
    Messages
    5 126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : août 2003
    Messages : 5 126
    Points : 9 910
    Points
    9 910

    Par défaut

    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 c++ : 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
    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().
    Blog|FAQ C++|FAQ fclc++|FAQ Comeau|FAQ C++lite|FAQ BS|Bons livres sur le C++
    Les MP ne sont pas une hotline. Je ne réponds à aucune question technique par le biais de ce média. Et de toutes façons, ma BAL sur dvpz est pleine...

  3. #3
    Membre expérimenté

    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    mai 2009
    Messages
    1 007
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 29
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : mai 2009
    Messages : 1 007
    Points : 1 735
    Points
    1 735

    Par défaut

    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.

  4. #4
    Expert éminent
    Avatar de Luc Hermitte
    Homme Profil pro
    Développeur informatique
    Inscrit en
    août 2003
    Messages
    5 126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : août 2003
    Messages : 5 126
    Points : 9 910
    Points
    9 910

    Par défaut

    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.
    Blog|FAQ C++|FAQ fclc++|FAQ Comeau|FAQ C++lite|FAQ BS|Bons livres sur le C++
    Les MP ne sont pas une hotline. Je ne réponds à aucune question technique par le biais de ce média. Et de toutes façons, ma BAL sur dvpz est pleine...

  5. #5
    Membre expérimenté

    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    mai 2009
    Messages
    1 007
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 29
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : mai 2009
    Messages : 1 007
    Points : 1 735
    Points
    1 735

    Par défaut

    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/

  6. #6
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    juillet 2005
    Messages
    9 804
    Détails du profil
    Informations personnelles :
    Âge : 35
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : juillet 2005
    Messages : 9 804
    Points : 21 935
    Points
    21 935

    Par défaut

    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.

Discussions similaires

  1. Réponses: 11
    Dernier message: 09/06/2010, 15h32
  2. Grandir une table de hachage
    Par étoile de mer dans le forum Débuter
    Réponses: 7
    Dernier message: 19/06/2008, 22h47
  3. Affichage d'une table de hachage
    Par pymouse dans le forum Langage
    Réponses: 6
    Dernier message: 06/07/2007, 11h35
  4. Réponses: 2
    Dernier message: 21/06/2006, 09h23

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo