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 に答える