c++ - 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;
}

但是比较忽略了我重载的运算符并且仍然使用指针的地址。有什么方法可以强制比较使用我的运算符，就像它们对普通对象所做的那样？

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 ** 的树，这可能(可能)仍然会遇到问题。尽管。至少对我来说，这里可能出现的问题看起来很严重，所以我建议不要这样做。