时间戳

首页 > 解决方案 > 如何自定义模板 AVL 树的不变量？

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

问题描述

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

我对 C++ 中的函数指针/对象不是很熟悉，我应该在哪里寻找？标准：：绑定（）？拉姆达斯？

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

标签： c++c++17avl-tree

解决方案

你应该模仿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)

推荐阅读