C++ design question (need cheap smart pointer)

Question

I have a huge tree where keys insides nodes are indices into a big hash_map v, where v[key] is a (big) record associated with that key (includes how many nodes in the tree have this key). Right now, key is an integer. So each node has overhead of storing pointers for children and an integer.
We can remove a key from a node in the tree. We can't store the actual record in the tree node (because that would be a memory hog). When a key is removed from a node, we need to look at v, update the count and remove the element (and compact the vector).

This cries out for a smart pointer implementation: where we have a shared_ptr spread around the tree. Once the last node that refers to key k is remove, the object is destroyed.

However, I am leery of the size requirements for shared_ptr. I need a cheep reference counted smart counter. I don't care about concurrent access.

Answer 1

Why not just extend your tree implementation to keep track of counts for the keys stored within in? All you need then is another hashmap (or an additional field within each record of your existing hashmap) to keep track of the counts, and some added logic in your tree's add/remove functions to update the counts appropriately.

Answer 2

Here's a simple reference-counting smart pointer I picked off the web a few years ago and patched up a little:

/// 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;
     }
    }
};

Storage requirements per smart pointer are modest: only the real pointer and the reference count.