Question de conception C++ (besoin pas cher pointeur intelligent)

Question

J'ai un arbre énorme où les clés à l'intérieur des nœuds sont des indices dans un grand hash_map v, où v [clé] est un (grand) enregistrement associé à cette clé (comprend combien de nœuds dans l'arbre ont cette clé). À l'heure actuelle, la clé est un nombre entier. Ainsi, chaque noeud dispose d'un surcoût de stockage des pointeurs pour les enfants et un nombre entier.
Nous pouvons supprimer une clé d'un nœud dans l'arborescence. Nous ne pouvons pas stocker l'enregistrement réel dans le nœud de l'arborescence (parce que ce serait un disque de mémoire). Lorsqu'une clé est retirée d'un nœud, nous devons regarder v, mettre à jour le nombre et supprimer l'élément (et compacter le vecteur).

Ceci appelle une implémentation de pointeur intelligent: où nous avons une propagation shared_ptr autour de l'arbre. Une fois que le dernier nœud faisant référence à la clé k est supprimé, l'objet est détruit.

Cependant, je me méfie des exigences de taille pour shared_ptr. J'ai besoin d'une référence de cheep compté compteur intelligent. Je me fiche de l'accès simultané.

Answer 1

Pourquoi ne pas simplement étendre votre implémentation d'arborescence pour garder une trace du nombre de clés stockées dans? Tout ce dont vous avez besoin est alors un autre hashmap (ou un champ supplémentaire dans chaque enregistrement de votre hashmap existant) pour garder une trace des comptages, et une certaine logique ajoutée dans les fonctions d'ajout/suppression de votre arbre pour mettre à jour les comptes correctement.

Answer 2

est ici d'un simple pointeur intelligent comptage référence Je pris sur le web il y a quelques années et rafistolé un peu:

/// A simple non-intrusive reference-counted pointer. 
/// Behaves like a normal pointer to T, providing 
/// operators * and ->. 
/// Multiple pointers can point to the same data 
/// safely - allocated memory will be deleted when 
/// all pointers to the data go out of scope. 
/// Suitable for STL containers. 
/// 
template <typename T> class counted_ptr 
{ 
public: 
    explicit counted_ptr(T* p = 0) 
     : ref(0) 
    { 
     if (p) 
      ref = new ref_t(p); 
    } 

    ~counted_ptr() 
    { 
     delete_ref(); 
    } 

    counted_ptr(const counted_ptr& other) 
    { 
     copy_ref(other.ref); 
    } 

    counted_ptr& operator=(const counted_ptr& other) 
    { 
     if (this != &other) 
     { 
      delete_ref(); 
      copy_ref(other.ref); 
     } 

     return *this; 
    } 

    T& operator*() const 
    { 
     return *(ref->p); 
    } 

    T* operator->() const 
    { 
     return ref->p; 
    } 

    T* get_ptr() const 
    { 
     return ref ? ref->p : 0; 
    } 

    template <typename To, typename From> 
    friend counted_ptr<To> up_cast(counted_ptr<From>& from); 

private: // types & members 

    struct ref_t 
    { 
     ref_t(T* p_ = 0, unsigned count_ = 1) 
      : p(p_), count(count_) 
     { 
     } 

     T* p; 
     unsigned count; 
    }; 

    ref_t* ref; 

private: // methods 

    void copy_ref(ref_t* ref_) 
    { 
     ref = ref_; 

     if (ref) 
      ref->count += 1; 
    } 

    void delete_ref() 
    { 
     if (ref) 
     { 
      ref->count -= 1; 

      if (ref->count == 0) 
      { 
       delete ref->p; 
       delete ref; 
      } 

      ref = 0; 
     } 
    } 
}; 

exigences de stockage par pointeur intelligent sont modestes: seul le pointeur réel et le nombre de références .