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> ，默认构造的对象会做正确的事情，所以这就是我们所需要的。

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