紅色黑樹中的虛空指針

Question

有兩個整數x和7是隨機生成的整數。該程序使用紅黑樹成員函數插入將新值插入樹中。

我不明白插入函數的參數，更具體的使用

(void*)x and (void*y) 

下面是主要

rbt.rbtree_insert(t, (void*)x, (void*)y, compare_int); 

這裏的函數調用的已定義

void RBTree::rbtree_insert(rbtree t, void* key, void* value, compare_func compare) 
{ 
    node inserted_node = new_node(key, value, RED, NULL, NULL); 
    if (t->root == NULL) 
    { 
     t->root = inserted_node; 
    } 
    else 
    { 
     node n = t->root; 
     while (1) 
     { 
      int comp_result = compare(key, n->key); 
      if (comp_result == 0) 
      { 
       n->value = value; 
       return; 
      } 
      else if (comp_result < 0) 
      { 
       if (n->left == NULL) 
       { 
        n->left = inserted_node; 
        break; 
       } 
       else 
       { 
        n = n->left; 
       } 
      } 
      else 
      { 
       assert(comp_result > 0); 
       if (n->right == NULL) 
       { 
        n->right = inserted_node; 
        break; 
       } 
       else 
       { 
        n = n->right; 
       } 
      } 
     } 
     inserted_node->parent = n; 
    } 
    insert_case1(t, inserted_node); 
    verify_properties(t); 
} 

插入功能

Answer 1

void*是一種類型。更具體地說，它是一個指針類型。更具體地說，它可以指向任何類型的special pointer類型。 void*是一種在C中實現polymorphism的方法。通常不建議在C++中使用void*。

(void*)x是一個explicit type conversion也被稱爲C風格類型演員表達。變量x的類型轉換爲void*。在C++中不鼓勵使用C風格的演員表。

推測x的類型不是void*，因此需要進行轉換以匹配參數的類型。

Answer 2

此代碼的作者使用C++中提供的最抽象的指針類型：void*。這是一個「東西」的指針。這個「東西」可能不是在編譯時定義的。 (void*)x是傳統C語法中的類型，它將任何其他指針解釋爲void*。首選的C++語法是static_cast<void*>(x)，但只有在有非常充分的理由時才應使用void*。

據我所知，這是遺留代碼，您被要求處理。所以讓我們坦率地說，它有很多錯誤。

1. 有整整兩個理由實施紅黑樹類：學習數據結構和std::map<>作爲標準庫實現的一部分。在所有其他情況下，沒有理由不喜歡std::map<>。它可以爲您節省所有設計陷阱，此代碼的作者已介入。

2. 將類的名稱添加到成員函數的名稱是多餘的。將其稱爲RBTree::insert()而不是RBTree::rbtree_insert()。當您爲不同的容器類型使用一致的成員函數名稱時，您可以在將來更換容易的成員函數名稱，而無需更改所有成員函數的所有調用。標準容器在這裏是一個很好的靈感來源。

3. 紅黑樹實例始終必須使用相同的比較函數。要一次又一次地將比較功能傳遞到insert()，find()，erase()等不僅是多餘的，而且還容易出錯。既可以將其作爲構造函數的參數，也可以作爲紅黑樹類模板的模板參數。

4. 在任何情況下，紅黑樹應該是一個模板，它有一個鍵和一個值類型作爲模板參數。然後所有的成員函數，如insert()，find()等都可以是類型安全的。

5. 爲什麼要將此對象顯式傳遞給成員函數。我想，該代碼的作者一直在試圖用C++編寫Python。在C++中，this對於成員函數總是隱含的，與Python中的self不同。

全部放在一起我會提出這樣的接口：

template<typename key_t, 
     typename value_t, 
     typename Compare = std::less<key_t>> 
class rb_tree { 
    void insert(const key_t& key, const value_t& value); 
    void erase(const key_t& key); 
    value_t find(const key_t& key); 
}; 

正如你看到的，我們現在定義類型鍵和值，並在insert()，erase()和find()使用它們。這些功能永遠不會嘗試使用int密鑰走路樹，就好像它有std::string密鑰。他們也總是使用相同的比較功能，該功能默認爲運營商<。

的使用是很多更好地理解，以及：

rb_tree<int, int> rbt; // we use the default comparison 
int x = 42; 
int y = 4711; 
rbt.insert(x, y); 
assert(rbt.find(x) == y); 
rbt.erase(x); 

嗯，其實我真正的建議是放棄比土生土長的紅黑樹和使用std::map<>來代替。它的使用更直觀：

std::map<int, int> rbt; 
int x = 42; 
int y = 4711; 
rbt[x] = y; 
assert(rbt[x] == y); 
rbt.erase(x);