C++设计问题（需要便宜的智能指针）

Question

我有一棵巨大的树，其中节点内的键是大 hash_map v 的索引， 其中 v[key] 是与该键关联的（大）记录（包括树中有多少个节点具有该键）。现在，key 是一个整数。所以每个节点 有存储子指针和整数的开销。
我们可以从树中的节点中删除键。 我们无法将实际记录存储在树节点中（因为这会占用内存）。 当从节点中删除键时，我们需要查看 v，更新计数并删除元素 （并压缩向量）。

这就需要一个智能指针的实现：我们有一个shared_ptr分布在树上。 一旦引用键 k 的最后一个节点被删除，该对象就被销毁。

但是，我对shared_ptr 的大小要求持怀疑态度。我需要一个廉价的参考计数 智能柜台。我不关心并发访问。

Answer 1

这是我几年前从网上摘下来的一个简单的引用计数智能指针，并进行了一些修补：

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

每个智能指针的存储要求适中：只有真正的指针和引用计数。

Answer 2

为什么不直接扩展树的实现来跟踪存储在其中的键的计数呢？然后，您所需要的只是另一个哈希映射（或现有哈希映射的每个记录中的附加字段）来跟踪计数，以及树的添加/删除函数中的一些添加逻辑以适当地更新计数。