c++ - 如何自定义模板 AVL 树的不变量？

Question

我正在开发一个通用的 AVL 树，并希望通过以下方式使用 T 的 < 和 > 运算符默认值，但也可以选择替换自定义的，这样我就可以更好地控制不变量和自由 T，而无需将其放入我的盒子中。

我不是很熟悉 C++ 中的函数指针/对象，我应该去哪里找？标准::绑定(bind)()？ lambda ？

template <typename T>
class avl_tree
{
   private:

   std::shared_ptr<avl_node<T>> root_ {nullptr};

   // > function object? uses T's > by default
   // < function object? uses T's < by default

   public: 

   avl_tree() = default;

   // avl_tree(?, ?) constructor accepting overloads
   //                for the < and > operators
};

Answer 1

你应该模仿std::set .将比较器作为模板参数:

template <typename T, class Compare = std::less<Key>>
class avl_tree
{
private:
    Compare comp;

public:
    avl_tree() = default;
    avl_tree(Compare comp) : comp{comp} {}
}

比较

comp(a, b); // instead of (a < b)
comp(b, a); // instead of (b < a)