作者yoco315 (眠月)
看板C_and_CPP
標題[心得] cached hash value
時間Fri Mar 20 23:32:23 2009
之前想要繼承 std::string 多增加一個快取的 hash_value 欄位，
這樣在使用 std::unordered 的時候，可以加速查找的效能。
但是經過一些摸索之後證明這是一個愚蠢的念頭，
比較好的做法是設計一個 class 把 std::string 包裝在內部，而不是繼承。
真的開始改 code 之後，發現這也不是一個好念頭，
更好的是設計一個泛型 class，對於任何型別都可以作 hash_value 快取。
像是這樣……
template < class T >
class hashed {
public :
hashed ( const hashed& h ) ;
hashed ( const T& v ) ;
T value () ;
size_t hash_value () ;
private :
T v_ ;
size_t hash_value_ ;
} ;
使用起來是這樣：
int main () {
std::string s = "three"
hashed<std::string> hs ;
hs = s ;
std::unordered<hashed<std::string>, int> umap ;
umap[hs] = 3 ;
std::cout << umap[hs] << std::endl ;
}
美中不足的時候每個被拷貝進去 unordered map 的字串都會多帶一個 hash_value，
其實我們只有在查找的時候才需要快取的 hash value，一旦存進去之後就用不到，
想了一下唯一的解法好像是去繼承 unordered_map，多加一個 find 的覆載…
Iterator find ( const hashed<KeyType>& h ) ;
然後使用 unordered 的時候還是使用沒有包覆的型別
std::unordered<std::string, int> umap ;
std::string s = "three" ;
hashed<string> hs = s ;
umap[s] = 3 ;
std::cout << umap[hs] << std::endl ;
各位大大有沒有建議…
可能我這次又跟上次一樣鬧笑話 orz
--
To iterate is human, to recurse, divine.
遞迴只應天上有, 凡人該當用迴圈. L. Peter Deutsch
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.160.106.44
1F：推 legnaleurc:如果我記得沒錯的話，STL所有的value classes都 03/21 00:21
2F：→ legnaleurc:沒有virtual destructor 03/21 00:21
3F：→ xam:這個跟 std::map 的差別在哪邊? 03/21 00:23
4F：推 littleshan: std::map 用的是 tree，search 時間 O(log(n)) 03/21 00:25
5F：推 littleshan:我覺得把 hash value 一起塞進去是比較好的做法 03/21 00:30
6F：→ littleshan:如果算 hash 很久，字串長度應該會遠大於 size_t 03/21 00:32
7F：推 akasan:hashed似乎多一個回傳reference的函數會比較好? 03/21 10:19