std ::地圖在tempate類<T>與密鑰<T>

我有自定義二進制樹類保存模板類型的值T（它可能是值或指針）。每個值都用數字封裝（該數字用於在樹中搜索）。我想在我的樹類中有一個std::map以快速地O（1）訪問沒有數字的對象。std ::地圖在tempate類<T>與密鑰<T>

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在樹下值n插入。現在我想要獲得與此a相關聯的節點。我無法搜索樹，因爲我沒有n。所以我想用a，從std::map得到node = map[a]。現在我可以做node->n。

我該如何做到這一點？我可以覆蓋比較std::map方法：

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

但它並不適用於價值和指針同時工作：不能從const double轉換參數1至const void *。

來源

2012-09-09 Martin Perry

'的std :: map'提供O（日誌N）的訪問，而不是O（1）。 – interjay

我知道...我也可以使用其他實現。它的速度比迭代整個BST還要快，並且要避免O（N）中的每個節點 –

「a」的類型是什麼？你只是說它是一個「類實例」。如果它是'T'的一個實例，那麼爲什麼你需要重寫任何東西？要麼可以比較「T」（在這種情況下地圖將起作用），要麼不能（在這種情況下，你所做的事情是不可能的 - 你的模板必須要求「T」具有可比性，或者拿一個象'map'這樣的比較器並將該比較器傳遞給它的'map'數據成員）。 –

做一個traited比較：

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-09 16:57:08

它不會工作...比較器寫在BSTNode ，而關鍵只是T ...或者我誤會了嗎？ –

@MartinPerry：你是對的！我改變了它。 –

std ::地圖在tempate類<T>與密鑰<T>

回答

相關問題