0

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

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

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

4

2 回答 2

2

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

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

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

于 2009-12-23T04:50:08.767 回答
1

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

于 2009-12-23T04:40:44.143 回答