由指向对象的指针组成的AVL树中的比较

Question

我有一个使用模板的AVL树，假设节点对象是可比较的，因此直接进行比较，而不是比较与对象关联的某种键：

void insert( const Comparable & x, AvlNode * & t )
{
    if( t == nullptr )
        t = new AvlNode( x, nullptr, nullptr );
    else if( x < t->element )
        insert( x, t->left );
    else if( t->element < x )
        insert( x, t->right );

    balance( t );
}

为了使这个工作正常，我在我的类中实现了一个重载的 < 操作符，它使用类的成员变量来比较这两个对象：

bool operator <(const myClass & myObject) const
{
    return myVariable < myObject.myVariable;
}

当我创建一个对象的AVL树时，这个工作完美：

AvlTree<myClass> myTree;

然而，当我创建一个指向对象的AVL树时，它无法工作：

AvlTree<myClass*> myTree;

树内部的比较似乎是比较指针的地址，而不是成员变量。我尝试在我的指针类中实现了一个类似的重载 < 运算符：

bool operator <(const myClass *& myObject) const
{
    return myVariable < myObject->myVariable;
}

但是这些比较忽略了我的重载运算符，并且仍然使用指针的地址。有没有办法强制比较运算符使用我的运算符，就像它们与普通对象一样？

- CuriouS

---

不要仅仅重载 <，而是将比较器类作为树模板的另一个模板参数传递。请参阅 std::map 以获取详细信息。 - n. m.

我建议你看一下这个链接： https://dev59.com/bHVC5IYBdhLWcg3wbQbA - Lan Pac

Answer 1

这是可能的，但有些复杂。

通常的做法是传递一个函数给树来比较存储的内容。你可以提供一个默认值给这个函数，通常使用std::less<T>作为默认值，但允许用户传递其他函数。当然，你需要重写你的代码来使用这个函数而不是直接使用<：

template <class T, class Less=std::less<T>>
class AvlTree {

public:

    void insert( const Comparable & x, AvlNode * & t )
    {
        if( t == nullptr )
            t = new AvlNode( x, nullptr, nullptr );
        else if( Less(x, t->element) )
            insert( x, t->left );
        else if( Less(t->element, x) )
            insert( x, t->right );

        balance( t );
    }

    // ...
};

如果是指向树的指针，您需要指定一种适当的比较方式：

template <class T>
struct LessPtr { 
    bool operator()(T *a, T *b) { 
        return *a < *b;
    }
};

当您实例化树时，需要传递一个该类的实例：

AvlTree<MyClass *, LessPtr<MyClass>> my_tree;

现在你的树应该比较指向的对象而不是指针本身。

当然，还有其他方法可以做到这一点。冒着在某些情况下做错事的风险，您可以（例如）使用模板特化来定义指针的特化，以比较指向对象而不是指针本身。但是，如果用户尝试创建MyObject **的树，则仍可能遇到问题。至少对我来说，这里的潜在问题看起来足够严重，我建议不要这样做。

- Jerry Coffin