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

Question

我正在编写自定义 OrderedTree class 我想用作 unordered_set.

的键

我想在散列树时做几件事：

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

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

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

我可以将 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

保证 std 容器在执行 const 或逻辑上 const 操作时只会调用 const 成员。如果这些 const 操作是多重的 - reader 安全，那么容器也是如此；相反，如果它们不是，则容器也不是。

散列值的不变性和相等性（或 < 在有序容器上）是仅您需要在关联容器中的键类型中保证的事情。 Actual const 给出了上面的 multiple-reader 保证，这可能非常有用。更重要的是，违反它会让你在未来使用它，and/or 微妙但是当有人认为 const 意味着不可变时。

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

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

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

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

Modify internal structure when implementing std::hash<T>

c++

hash

constants

unordered-set

c++11