是否可以在 C++03 中可移植地散列一个指针,它没有 std::hash
定义?
包含指针的哈希值在 C++ 中是不可能的,这似乎很奇怪,但我想不出任何制作它们的方法。
我能想到的最接近的方法是做 reinterpret_cast<uintptr_t>(ptr)
,但是 uintptr_t
不需要在 C++03 中定义,我不确定即使定义了该值是否可以合法操作......这甚至可能吗?
最佳答案
不,一般来说。事实上,如果没有 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
到一个常数,它也会在那里工作。但是对于实现来说没有任何要求。希望这可以澄清一些事情。
关于c++ - 是否可以在可移植 C++03 代码中散列指针?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14167455/