Сравнения в AVL Tree, состоящие из указателей на объекты

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 ** хоть. По крайней мере, для меня потенциал проблем здесь выглядит достаточно серьезным, поэтому я бы посоветовал против этого.