C++のディスジョイントセットでメモリの割り当てを解除する方法を教えてください。

Question

私のC++アプリケーションにはDisjoint setsを扱うクラスがあります。私はこれらのクラスのデストラクタを実装するのに苦労します。誰か助けてくれますか？

これらの基本的なやり方は、nodeのポインタをNodeAddress[]に置きます。すべてnodeは、valで区別されます。すべてのノードは、hdヘッドのプレースホルダーであるItemへのポインターと、ディスジョイントセットのtl末尾を持ちます。

私はいくつかの問題があることを認識していると言いたいと思います。 ：変数の可視性（パブリックアクセス）、一定のサイズ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); 
    } 
} 

* EDIT：* そこに私が持っている何かがあるが、

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型指定インデックスによって、セットが一意に識別されるため、ポインタの操作は必要ありません。