c++ - 是否可以在可移植 C++03 代码中散列指针？

Question

是否可以在 C++03 中可移植地散列一个指针，它没有 std::hash定义？

包含指针的哈希值在 C++ 中是不可能的，这似乎很奇怪，但我想不出任何制作它们的方法。

我能想到的最接近的方法是做 reinterpret_cast<uintptr_t>(ptr) ，但是 uintptr_t不需要在 C++03 中定义，我不确定即使定义了该值是否可以合法操作......这甚至可能吗？

Answer 1

不，一般来说。事实上，如果没有 std::hash，在 C++11 中通常是不可能的。 .

原因在于值(value)和值(value)表示之间的差异。

您可能还记得用于演示值与其表示之间的区别的非常常见的示例:空指针值。许多人错误地认为这个值的表示都是零位。这不能以任何方式保证。您仅通过其值(value)来保证行为。

再举一个例子，考虑:

int i;
int* x = &i;
int* y = &i;

x == y;  // this is true; the two pointer values are equal

但是，在此之下， x 的值表示和 y可以不一样!

让我们玩编译器。我们将实现指针的值表示。假设我们需要(出于假设的架构原因)指针至少为两个字节，但只有一个用于值。

我会跳到前面说它可能是这样的:

struct __pointer_impl
{
    std::uint8_t byte1; // contains the address we're holding
    std::uint8_t byte2; // needed for architecture reasons, unused
    // (assume no padding; we are the compiler, after all)
};

好的，这是我们的值表示，现在让我们实现值语义。一、平等:

bool operator==(const __pointer_impl& first, const __pointer_impl& second)
{
    return first.byte1 == second.byte1;
}

因为指针的值实际上只包含在第一个字节中(即使它的表示有两个字节)，这就是我们要比较的全部内容。第二个字节无关紧要，即使它们不同。

我们需要操作符的地址实现，当然:

__pointer_impl address_of(int& i)
{
    __pointer_impl result;

    result.byte1 = /* hypothetical architecture magic */;

    return result;
}

这个特定的实现重载为我们提供了一个给定 int 的指针值表示。 .请注意，第二个字节未初始化!没关系:这对值(value)来说并不重要。

这真的是我们把重点带回家所需要的全部。假设其余的实现已经完成。 :)

所以现在再次考虑我们的第一个例子，“编译器化”:

int i;

/* int* x = &i; */
__pointer_impl x = __address_of(i);

/* int* y = &i; */
__pointer_impl y = __address_of(i);

x == y;  // this is true; the two pointer values are equal

对于我们关于假设架构的小例子，这足以提供指针值标准所需的保证。但请注意，您永远无法保证 x == y暗示 memcmp(&x, &y, sizeof(__pointer_impl)) == 0 .对值表示根本没有要求这样做。

现在考虑你的问题:我们如何散列指针？也就是说，我们要实现:

template <typename T>
struct myhash;

template <typename T>
struct myhash<T*> :
    std::unary_function<T*, std::size_t>
{
    std::size_t operator()(T* const ptr) const
    {
        return /* ??? */;
    }
};

最重要的要求是如果 x == y ，然后 myhash()(x) == myhash()(y) .我们也已经知道如何散列整数。我们可以做什么？

我们唯一能做的就是尝试以某种方式将指针转换为整数。好吧，C++11 给了我们 std::uintptr_t ，所以我们可以这样做，对吗？

return myhash<std::uintptr_t>()(reinterpret_cast<std::uintptr_t>(ptr));

也许令人惊讶的是，这是不正确的。要理解为什么，再想象一下我们正在实现它:

// okay because we assumed no padding:
typedef std::uint16_t __uintptr_t; // will be used for std::uintptr_t implementation

__uintptr_t __to_integer(const __pointer_impl& ptr)
{
    __uintptr_t result;
    std::memcpy(&result, &ptr, sizeof(__uintptr_t));

    return result;
}

__pointer_impl __from_integer(const __uintptr_t& ptrint)
{
    __pointer_impl result;
    std::memcpy(&result, &ptrint, sizeof(__pointer_impl));

    return result;
}

所以当我们 reinterpret_cast指向整数的指针，我们将使用 __to_integer ，然后我们将使用 __from_integer .请注意，结果整数的值取决于指针值表示中的位。也就是说，两个相等的指针值可能会以不同的整数表示结束……​​这是允许的!

这是允许的，因为 reinterpret_cast 的结果完全由实现定义；你只能保证相反的结果 reinterpret_cast给你同样的结果。

所以有第一个问题:在这个实现中，对于相等的指针值，我们的哈希最终可能会有所不同。

这个想法出来了。也许我们可以深入到表示本身并将字节散列在一起。但这显然以同样的问题告终，这就是对您的问题的评论所暗示的。那些讨厌的未使用的表示位总是挡在路上，而且没有办法弄清楚它们在哪里，所以我们可以忽略它们。

我们被困住了!这是不可能的。一般来说。

请记住，在实践中我们针对某些实现进行编译，并且因为这些操作的结果是实现定义的，如果您注意正确使用它们，它们是可靠的。这是什么 Mats Petersson is saying :找出实现的保证，你会没事的。

事实上，您使用的大多数消费者平台都会处理 std::uintptr_t尝试就好了。如果它在您的系统上不可用，或者如果您想要其他方法，只需组合指针中各个字节的哈希值。所有这些工作需要的是未使用的表示位始终采用相同的值。实际上，这就是 MSVC2012 使用的方法!

如果我们假设的指针实现总是简单地初始化 byte2到一个常数，它也会在那里工作。但是对于实现来说没有任何要求。

希望这可以澄清一些事情。