std :: hashを実装するときの内部構造を変更します

Question

私はのキーとして使用するカスタムOrderedTreeクラスを作成しています。

私はツリーをハッシュするときカップルの事をしたい：

1. （これは高価な操作であってもよいので）多分木のバランスをとる
2. 、なまけハッシュを計算し、必要に応じてキャッシュします。

これらの操作のどちらも、オブジェクトの意味的同等性またはハッシュ値を変更しませんが、いくつかのプライベートフィールドを変更します。

OrderedTree内のメンバーを変更しようとすると、std::hash<Tree>::operator()は、unordered_setが期待するconstの正しさに違反しているようです。

OrderedTreeをunordered_setとすることはできますか？もしそうなら、どうですか？

編集：コメント欄にリクエストを1として

、概念の最小限の証拠：

#include <unordered_set> 

std::size_t hash_combine(std::size_t a, std::size_t b) { 
    // TODO: Copy from boost source or something 
    return 0; 
} 

struct Node { 
    int value; 
    Node *left, *right, *parent; 

    std::size_t hash(std::size_t seed) const { 
    if (left != nullptr) 
     seed = left->hash(seed); 
    std::hash<int> hasher; 
    seed = hash_combine(seed, hasher(value)); 
    if (right != nullptr) 
     seed = right->hash(seed); 
    return seed; 
    } 
}; 

struct Tree { 

    Tree(): hash_(0), root(nullptr) {} 

    Node *root; 

    std::size_t hash() const { 
    if (hash_ == 0 && root != nullptr) { 
     hash_ = root->hash(7); 
    } 
    return hash_; 
    } 

private: 
    std::size_t hash_; 
}; 

namespace std { 
    template<> 
    struct hash<Tree> { 
    std::size_t operator()(const Tree& t) const { 
     return t.hash(); 
    } 
    }; 
} 

int main() { 
    std::unordered_set<Tree> set; 
} 

私がコンパイルしようとする私が取得：

Sample.cc:31:13: error: cannot assign to non-static data member within const member function 'hash' 
     hash_ = root->hash(7); 
     ~~~~~^
Sample.cc:29:15: note: member function 'Tree::hash' is declared const here 
    std::size_t hash() const { 
    ~~~~~~~~~~~~^~~~~~~~~~~~ 

Answer 1

そのSTD保証はありコンテナはconstまたは論理的にconstの操作を行うときにのみconstメンバーにコールします。それらの操作が複数のリーダーで安全な場合、コンテナも同じです。逆に、もしそうでなければ、どちらもコンテナではない。

ハッシュ値と等価性（または<の順序付きコンテナ）の不変性は、のみであり、関連コンテナのキータイプで保証されます。実際のconstは、上記の複数リーダーの保証を提供します。これは非常に便利です。それを違反することは、これを将来的に使用することに費用がかかります。そして/または微妙ですが、誰かが推測するときにはconstは不変を意味します。

複数のリーダーの保証を維持するために、書き込み操作を内部で慎重に同期させることも、放棄することもできます。

constに違反すると、通常mutableが使用されます。 constconstのリスクを回避するためにキャスティングを使用するメソッド未定義オブジェクトがの場合、実際にはconstであり、constオブジェクトのビューではなく、constオブジェクトです。

一般に、この種の最適化を使用する前に注意してください。速度を上げるよりも、コードの複雑さ（ハンスバグ、メンテナンスなど）を簡単に増やすことができます。コードの高速化は可能です。遅いコードとこの部分を投資に先立つボトルネックと認識されていることを確認してください。そして、ハッシュでバランスを取る場合は、なぜハッシュを待つのですか？挿入前のバランス！