0

ノード内のキーが大きな hash_map v へのインデックスである巨大なツリーがあります。ここで、v[key] はそのキーに関連付けられた (大きな) レコードです (ツリー内でこのキーを持つノードの数を含みます)。現在、キーは整数です。したがって、各ノードには、子のポインターと整数を格納するオーバーヘッドがあります。
ツリーのノードからキーを削除できます。実際のレコードをツリー ノードに格納することはできません (メモリを大量に消費するため)。キーがノードから削除されると、v を見て、カウントを更新し、要素を削除する (そしてベクトルを圧縮する) 必要があります。

これは、スマート ポインターの実装を求めています。ここでは、shared_ptr がツリー全体に広がっています。キー k を参照する最後のノードが削除されると、オブジェクトは破棄されます。

ただし、shared_ptr のサイズ要件には不安があります。安価なリファレンス カウント スマート カウンターが必要です。同時アクセスは気にしません。

4

2 に答える 2

2

これは、私が数年前に Web から拾い上げ、少しパッチを当てた単純な参照カウント スマート ポインターです。

/// 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 に答える