Как я могу управлять освобождением памяти в непересекающихся множествах в C ++?

Question

У меня есть набор классов для обработки Несвязных наборов в моем приложении C ++. Мне трудно реализовать деструкторы для этих классов. Может ли кто-нибудь помочь мне в этом?

Что они в основном делают: помещают указатели node s в NodeAddress[], каждый node отличается своим val. Каждый узел имеет указатель на Item, который является заполнителем для hd головы и tl хвоста непересекающегося множества.

Я хочу упомянуть, что я понимаю, что есть некоторые проблемы, например, с. : переменная видимость (публичный доступ), постоянный размер NodeAddress буфер, но я хочу сосредоточиться здесь на освобождении памяти.

И да, я хочу (нужно) сделать это по указателю (без STL). Если у вас есть интересные предложения или вопросы, не стесняйтесь комментировать.

Это код:

header

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

Ваш код слишком сложен. Вот мой взгляд на несвязный набор леса ; все управление памятью может осуществляться извне путем помещения наборов в vector. Обратите внимание, что манипулирование указателем не требуется, поскольку набор может быть однозначно идентифицирован с помощью size_t -типного индекса в лесу.