比较在AVL树由指针对象

我有一个使用模板和假设节点对象具有可比性，所以他们直接进行比较，而不是比较某种键与对象相关联的AVL树：比较在AVL树由指针对象

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

这工作完全当我创建一个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); 
}

为了这个工作，我在我的课，它使用类的成员变量两个比较对象实现重载<操作对象树：

AvlTree<myClass> myTree;

但是，当我创建的指针AVL树对象不起作用：

AvlTree<myClass*> myTree;

树内的比较似乎比较指针的地址，而不是成员变量。我试图在我的课实施了类似的重载<运营商指针：

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

但比较会忽略我的重载运营商，仍使用指针的地址。有什么办法可以强制比较使用我的操作符，就像使用普通对象一样？

来源

2014-10-30 CuriouS

不要（仅）重载'<'，将比较器类作为另一个模板参数传递给树模板。详情请参阅std :: map。 – 2014-10-30 13:49:34

我建议你看看这个 http://stackoverflow.com/questions/301330/determine-if-type-is-a-pointer-in-a-template-function – 2014-10-30 13:54:48

这是可能的，但有点不重要。

完成这项工作的常用方法是传递树将用来比较存储内容的函数。您可以为此功能提供默认值，通常使用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 **树，这可能（可能会）会遇到问题。至少对我来说，这里潜在的问题看起来非常严重，尽管如此我还是建议不要这样做。

来源

2014-10-30 13:47:30

比较在AVL树由指针对象

回答

相关问题