作者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