c++ - 如何在 C++ 中管理不相交集合中的内存释放？

Question

我有一组类来处理 Disjoint sets在我的 C++ 应用程序中。我很难为这些类实现析构函数。任何人都可以帮助我吗？

这些基本上做的是:将 node 的指针放入 NodeAddress[]，每个 node 由其 val 区分。每个节点都有一个指向 Item 的指针，它是不相交集的 hd head 和 tl tail 的占位符。

我想提一下，我意识到有一些问题，例如。 :可变可见性(公共(public)访问)，恒定大小的 NodeAddress 缓冲区，但我想在这里关注内存释放。

是的，我希望(需要)在指针上执行此操作(无 STL)。如果您有任何建议或问题，请随时发表评论。

这是代码:

标题

class ListSet {
public:
    unsigned int size;
    node* NodeAddress[MAX_NUMBER_OF_LABELS];

    struct Item;
    class node {
    public:
        unsigned int val;
        node *next;
        Item *itemPtr;

        node () : val(0), next(0), itemPtr(0) {}
        node (const int& a) : val(a), next(0), itemPtr(0) {}
    };
    struct Item {
    public:
        node *hd, *tl;
        Item(node *shd) : hd(shd), tl(shd) {}
        void ListSet::Item::append (const Item* other);

        //removal
        ListSet::node* remove(node* old);
    };

    ListSet()
    {
        this->size = 0;
        memset(NodeAddress, 0, sizeof(NodeAddress));
    }

    void setNodeAddress(const int& a, node* shd)
    {
        NodeAddress[a] = shd;
    }
    node* getNodeAddress(const int& a)
    {
        return NodeAddress[a];
    }

    ListSet::Item* ListSet::makeSet (const int& a) ;
    ListSet::Item* ListSet::find (const int& a);

    ListSet::Item* ListSet::unionSets (Item* s1, Item* s2);
    void ListSet::unionSets (const int& a1, const int& a2);
};

来源

void ListSet::Item::append (const Item* other) {
    //join the tail of the set to head of the other set
    tl->next = other->hd;
    tl = other->tl;
    for (node* cur = other->hd; cur; cur = cur->next) {
        cur->itemPtr = this;
    }
}

ListSet::Item* ListSet::makeSet (const int& a) {
    if( a > this->size) {this->size = a;}

    assert(!getNodeAddress(a));
    node *shd = new node(a);
    Item *newSet = new Item(shd);
    setNodeAddress(a, shd);
    shd->itemPtr = newSet;
    return newSet;
}

ListSet::Item* ListSet::find (const int& a) {
    node* ptr = getNodeAddress(a);
    if (ptr)
        return ptr->itemPtr;
    return 0;
}

ListSet::Item* ListSet::unionSets (Item* s1, Item* s2) {
    Item *set1 = s1;
    Item *set2 = s2;

    set2->append(set1);
    delete set1;

    return set2;
}
void ListSet::unionSets (const int& a1, const int& a2) {
    Item* s1 = find(a1);
    Item* s2 = find(a2);
    if (s1 && s2) {
        (void) unionSets(s1, s2);
    }
}

*编辑:*我有一些东西但没有用

ListSet::node* ListSet::Item::remove(node* old) {
    if (old == hd) {
        if (old == tl) {
            assert(! old->next);
            return 0;
        }
        assert(old->next);
        hd = old->next;
    } else {
        node* prev;
        for (prev = hd; prev->next != old; prev = prev->next) {
            assert(prev->next);
            ;
        }
        if (old == tl) {
            assert(! old->next);
            //
            tl = prev;
            prev->next = 0;
        } else {
            assert(old->next);
            prev->next = old->next;
        }
    }
    return hd;
}

ListSet::node::~node() {
    if (itemPtr) {
        if (! itemPtr->remove(this)) {
            // Don't leak an empty set.
            delete itemPtr;
        }
    }
}

void ListSet::remove(const int& a) {
    node* ptr = getNodeAddress(a);
    if (ptr) {
        setNodeAddress(a, 0);
        delete ptr;
    }
    // else error?
}

Answer 1

您的代码过于复杂。这是 my take on a disjoint set forest ;所有的内存管理都可以通过将这些集合放在一个vector 中来从外部处理。请注意，不需要指针操作，因为集合可以通过森林中的 size_t 类型索引唯一标识。