按两个条件比较的 C++ 泛型树

Question

我开始研究通用树，而且我是 C++ 的新手。我希望能够形成两棵相同元素的树，但在每棵树中以不同的方式进行比较。据我所知，如果我重载 <，那么我只能定义一个函数。我想我也许可以传递一个指向函数的指针，但我觉得这是错误的方法。

template<class T, int (*Comp)(T*, T*)> class Tree 

尝试这样做的明智方法是什么？谢谢

Answer 1

不，您不想指定一个指向函数的指针(这样做会禁止使用函数对象，这通常更可取)。

模板参数通常应该是类型参数——在这种情况下，您几乎肯定希望提供默认值 std::less<T>。 ，所以它看起来像这样:

template <class T, class Comp = std::less<T>>
class Tree {
     // Implementation here.    
};

这将允许通过指向函数的指针进行实​​例化，但(如上所述)还将支持函数对象。

但是请注意，模板参数仅指定您用来进行比较的事物的类型。在典型情况下，您需要该类型的一个实例来执行某些操作。您通常会在构建对象时指定它，因此您将拥有如下内容:

template <class T, class Comp = std::less<T>>
class Tree {
public:
    Tree(Comp c = Comp()) : c(c) {}

    bool insert(T value) {
        if (c(value, root->value)) // if value < root->value
            // ...
        else if (c(root->value, value)) // if root->value < value
    }
private:
    struct Node { 
        T key;
        Node *left , *right;
    } *root;

    Comp c;     
};

因此，模板参数指定了进行比较的对象的类型。我们给它一个默认值 std::less<T> ;这对于内置类型以及任何其他使 a<b 的东西都很好地工作一个合法的表达式(当然假设我们想要这样的比较)。如果我们提供不同的类型，则需要使用它来确保它定义了严格的弱排序。

然后我们将比较类型的实例传递给构造函数。同样，我们指定该类型的默认构造实例的默认值。对于像 std::less<T> 这样的函数对象类型的常见情况或 std::greater<T> ，默认构造的对象将做正确的事情，所以这就是我们所需要的。

对于想要使用指向函数的指针的不太常见的情况，我们必须指定正确的类型作为模板参数，并且我们必须将指向正确函数的指针传递给构造函数。