0

テンプレートタイプの値を保持するカスタムバイナリツリークラスが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.
}

例:ツリーのvalueの下にクラスインスタンスをa挿入しましたn。ここで、これに関連付けられているノードを取得しますa。持っていないので、ツリーを検索できませんn。だから私はを使いたいa、そしてstd::mapgetからnode = map[a]。今、私はすることができますnode->n

どうすればこれを達成できますか?のcompareメソッドをオーバーライドできますstd::map

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

ただし、値とポインタに対しては同時に機能しません。パラメータ1をからconst doubleに変換することはできませんconst void *

4

1 に答える 1

2

特性のあるコンパレータを作成します。

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;
}
于 2012-09-09T16:57:08.063 に答える