[心得] cached hash value

[yoco315 (眠月)]

之前想要繼承 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
推 legnaleurc:如果我記得沒錯的話，STL所有的value classes都
→ legnaleurc:沒有virtual destructor
→ xam:這個跟 std::map 的差別在哪邊?
推 littleshan: std::map 用的是 tree，search 時間 O(log(n))
推 littleshan:我覺得把 hash value 一起塞進去是比較好的做法
→ littleshan:如果算 hash 很久，字串長度應該會遠大於 size_t
推 akasan:hashed似乎多一個回傳reference的函數會比較好?