c++ - 临时类中的 std::map用钥匙

Question

我有自定义二叉树类，它保存模板类型的值T（它可以是值或指针）。每个值都用数字封装（这个数字用于在树中搜索）。我想std::map在我的树类中有一个快速 O(1) 访问没有数字的对象。

template <typename T>
stuct BSTNode 
{
  T value;
  int searchValue;
}

template <typename T>
class BST 
{
  BSTNode<T> * root;
  std::map<T, BSTNode<T>> cache;
  //... etc.
}

示例：我a在 value 下的树中插入了类实例n。现在我想获取与 this 关联的节点a。我无法搜索树，因为我没有n. 所以我想用a, 并从std::mapget node = map[a]。现在我可以做到了node->n。

我怎样才能做到这一点？我可以覆盖比较方法std::map：

bool operator()(const void * s1, const void * s2) const

但它不能同时用于值和指针：不能将参数 1 从 转换const double为const void *.

Answer 1

做一个有特征的比较器：

template <typename T>
struct NodeComp
{
    bool operator<(T const & lhs, T const & rhs) const
    {
        return lhs < rhs;
    }
};

template <typename U>
struct NodeComp<U *>
{
    bool operator<(U * lhs, U * rhs) const
    {
        return *lhs < *rhs;
    }
};

现在您的地图可以这样定义：

template <typename T>
class BST 
{
    BSTNode<T> * root;
    std::map<T, BSTNode<T>, NodeComp<T>> cache;
}