c++ - 实现 std::hash<T> 时修改内部结构

Question

我正在编写自定义 OrderedTree我想用作 unordered_set 的键的类.

我想在对树进行哈希处理时做几件事:

1. 懒惰地计算哈希并根据需要缓存它(因为这可能是一个昂贵的操作)，
2. 也许平衡这棵树。

这些操作都不会改变对象的语义相等性或哈希值，但它们会修改一些私有(private)字段。

不幸的是，试图修改 OrderedTree 中的任何成员在里面std::hash<Tree>::operator()似乎违反了 unordered_set 的 const 正确性期待。

我可以使用我的 OrderedTree 吗？与 unordered_set ？如果是，怎么办？

编辑:

根据评论中的要求，最小的概念证明:

#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

可以保证标准容器只会调用 const成员(member)在做const或逻辑上 const操作。如果那些const操作是多读者安全的，容器也是如此；相反，如果它们不是，则容器也不是。

散列值的不变性和相等性(或有序容器上的 <)是唯一您需要在关联容器中的键类型中保证的事情。实际const给出了上面的多读者保证，这可能非常有用。更重要的是，违反它会让你在未来使用它，和/或当有人假设时微妙但会花费const表示不可变。

您可以小心地在内部同步写入操作以保持多读取器保证，或者您可以放弃。

违反const , 通常你使用 mutable . const使用转换绕过const的方法如果对象实际上是 则有未定义行为的风险 const ，而不仅仅是一个 const View 非 const对象。

一般来说，在使用这种优化之前要小心；它可以很容易地增加代码复杂性(hance bugs、维护等)，而不是增加速度。并且加速代码是可替代的:确保在投资之前将其识别为慢速代码并将这部分识别为瓶颈。如果您要在哈希中取得平衡，为什么要等待哈希？插入前平衡!