红色黑树中的虚空指针

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);