草庐IT

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

coder 2024-01-31 原文

是否可以在 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/

amp中散codebrpointer_implc++pointershashlanguage-lawyer

有关c++ - 是否可以在可移植 C++03 代码中散列指针？的更多相关文章

  1. ruby - 为什么我可以在 Ruby 中使用 Object#send 访问私有(private)/ protected 方法？ - 2

    类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc

  2. ruby-on-rails - 如何验证 update_all 是否实际在 Rails 中更新 - 2

    给定这段代码defcreate@upgrades=User.update_all(["role=?","upgraded"],:id=>params[:upgrade])redirect_toadmin_upgrades_path,:notice=>"Successfullyupgradeduser."end我如何在该操作中实际验证它们是否已保存或未重定向到适当的页面和消息？ 最佳答案 在Rails3中，update_all不返回任何有意义的信息，除了已更新的记录数(这可能取决于您的DBMS是否返回该信息)。http://ar.ru

  3. ruby - 如何在 buildr 项目中使用 Ruby 代码？ - 2

    如何在buildr项目中使用Ruby？我在很多不同的项目中使用过Ruby、JRuby、Java和Clojure。我目前正在使用我的标准Ruby开发一个模拟应用程序，我想尝试使用Clojure后端(我确实喜欢功能代码)以及JRubygui和测试套件。我还可以看到在未来的不同项目中使用Scala作为后端。我想我要为我的项目尝试一下buildr(http://buildr.apache.org/)，但我注意到buildr似乎没有设置为在项目中使用JRuby代码本身!这看起来有点傻，因为该工具旨在统一通用的JVM语言并且是在ruby中构建的。除了将输出的jar包含在一个独特的、仅限ruby​​

  4. ruby - 使用 Vim Rails，您可以创建一个新的迁移文件并一次性打开它吗？ - 2

    使用带有Rails插件的vim，您可以创建一个迁移文件，然后一次性打开该文件吗？textmate也可以这样吗？ 最佳答案 你可以使用rails.vim然后做类似的事情::Rgeneratemigratonadd_foo_to_bar插件将打开迁移生成的文件，这正是您想要的。我不能代表textmate。 关于ruby-使用VimRails，您可以创建一个新的迁移文件并一次性打开它吗？，我们在StackOverflow上找到一个类似的问题： https://sta

  5. ruby-on-rails - Rails 源代码 : initialize hash in a weird way? - 2

    在rails源中:https://github.com/rails/rails/blob/master/activesupport/lib/active_support/lazy_load_hooks.rb可以看到以下内容@load_hooks=Hash.new{|h,k|h[k]=[]}在IRB中，它只是初始化一个空哈希。和做有什么区别@load_hooks=Hash.new 最佳答案 查看rubydocumentationforHashnew→new_hashclicktotogglesourcenew(obj)→new_has

  6. ruby - 我可以使用 Ruby 从 CSV 中删除列吗？ - 2

    查看Ruby的CSV库的文档，我非常确定这是可能且简单的。我只需要使用Ruby删除CSV文件的前三列，但我没有成功运行它。 最佳答案 csv_table=CSV.read(file_path_in,:headers=>true)csv_table.delete("header_name")csv_table.to_csv#=>ThenewCSVinstringformat检查CSV::Table文档:http://ruby-doc.org/stdlib-1.9.2/libdoc/csv/rdoc/CSV/Table.html

  7. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  8. ruby - 检查数组是否在增加 - 2

    这个问题在这里已经有了答案:Checktoseeifanarrayisalreadysorted?(8个答案)关闭9年前。我只是想知道是否有办法检查数组是否在增加？这是我的解决方案，但我正在寻找更漂亮的方法:n=-1@arr.flatten.each{|e|returnfalseife

  9. ruby - 我可以使用 aws-sdk-ruby 在 AWS S3 上使用事务性文件删除/上传吗？ - 2

    我发现ActiveRecord::Base.transaction在复杂方法中非常有效。我想知道是否可以在如下事务中从AWSS3上传/删除文件:S3Object.transactiondo#writeintofiles#raiseanexceptionend引发异常后，每个操作都应在S3上回滚。S3Object这可能吗？？ 最佳答案 虽然S3API具有批量删除功能，但它不支持事务，因为每个删除操作都可以独立于其他操作成功/失败。该API不提供任何批量上传功能(通过PUT或POST)，因此每个上传操作都是通过一个独立的API调用完成的

  10. ruby - 检查字符串是否包含散列中的任何键并返回它包含的键的值 - 2

    我有一个包含多个键的散列和一个字符串，该字符串不包含散列中的任何键或包含一个键。h={"k1"=>"v1","k2"=>"v2","k3"=>"v3"}s="thisisanexamplestringthatmightoccurwithakeysomewhereinthestringk1(withspecialcharacterslike(^&*$#@!^&&*))"检查s是否包含h中的任何键的最佳方法是什么，如果包含，则返回它包含的键的值？例如，对于上面的h和s的例子，输出应该是v1。编辑:只有字符串是用户定义的。哈希将始终相同。 最佳答案

随机推荐