7

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

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

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

4

2 回答 2

10

不，一般来说。事实上，在没有std::hash.

究其原因，就在于价值观和价值观表现的不同。

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

再举一个例子，考虑：

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 /* ??? */;
    }
};

最重要的要求是 if x == y， then 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的结果会给你同样的结果。

所以有第一个问题：在这个实现中，我们的哈希值可能会因指针值相等而不同。

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

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

Remember, in practice we compile for certain implementations, and because the results of these operations are implementation-defined they are reliable if you take care to only use them properly. This is what Mats Petersson is saying: find out the guarantees of the implementation and you'll be fine.

In fact, most consumer platforms you use will handle the std::uintptr_t attempt just fine. If it's not available on your system, or if you want an alternative approach, just combine the hashes of the individual bytes in the pointer. All this requires to work is that the unused representation bits always take on the same value. In fact, this is the approach MSVC2012 uses!

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

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

于 2013-01-05T08:02:56.770 回答
5

您的问题的答案实际上取决于您想要它的“便携性”。许多架构都会有一个 uintptr_t，但是如果你想要一些可以在 DSP、Linux、Windows、AIX、旧 Cray 机器、IBM 390 系列机器等上编译的东西，那么你可能需要一个配置选项来定义你的如果该架构中不存在“uintptr_t”，则拥有它。

将指针转换为整数类型应该没问题。如果你把它扔回去，你可能会遇到麻烦。当然，如果您有很多指针，并且您在 64 位机器上分配了相当大的内存部分，使用 32 位整数，那么您可能会遇到很多冲突。请注意，64 位窗口仍然有一个“长”作为 32 位。

于 2013-01-05T01:53:13.753 回答