草庐IT

c++ - hash_map : why it defines less, 而不是 equal_to

coder 2024-02-16 原文

C++，使用 Visual Studio 2010。关于为什么 hash_map 的用户定义特征的问题实际上需要总排序。

我有一个简单的结构，比如说 FOO , 它只有一些整数。我想使用 hash_map ，这是一个哈希表，其键无序，用于存储FOO的结构。 .我只需要快速搜索它的关联值，所以这是一个正确的选择:hash_map<FOO, int32_t> .

但是，我需要为 FOO 实现自己的哈希函数和一些比较函数.这是 hash_map 的定义, 摘自 MSDN:

template <
   class Key, 
   class Type, 
   class Traits=hash_compare<Key, less<Key> >, 
   class Allocator=allocator<pair <const Key, Type> > 
>
class hash_map

原来我需要实现hash_compare仿函数:

template<class Key, class Traits = less<Key> >
   class hash_compare
   {
   Traits comp;
public:
   const size_t bucket_size = 4;
   const size_t min_buckets = 8;
   hash_compare( );
   hash_compare( Traits pred );
   size_t operator( )( const Key& _Key ) const; // This is a hash function
   bool operator( )(                            // This is an ordering function
      const Key& _Key1,
      const Key& _Key2
   ) const;
   };

这里是来自 MSDN 的 bool operatod() 的详细描述:

For any value _Key1 of type Key that precedes _Key2 in the sequence and has the same hash value (value returned by the hash function), hash_comp(_Key2, _Key1) is false. The function must impose a total ordering on values of type Key.

The function supplied by hash_compare returns comp(_Key2, _Key1), where comp is a stored object of type Traits that you can specify when you construct the object hash_comp. For the default Traits parameter type less, sort keys never decrease in value.

很容易写出 hash_compare FOO 的类别.这个问题不是询问如何实现一个类。但是，为什么他们将默认特征参数设置为 less<key> 对我来说并不简单并要求总排序。

hash_map是一个无序数据结构。所以，我认为 equal_to 就足够了或 not_equal_to而不是 less或 greater .然而，MSDN的描述中明确指出键是有序的，这让我感到困惑。

我是不是误解了 hash_map 的定义？ ？为什么选择 STL hash_map实际上需要它的 key 命令？

最佳答案

For any value _Key1 of type Key that precedes _Key2 in the sequence and has the same hash value (value returned by the hash function), hash_comp(_Key2, _Key1) is false. The function must impose a total ordering on values of type Key.

具有相同散列值的键的总排序保证了散列到同一个桶的键的总排序。

这为更有效地实现特定存储桶中的键搜索提供了机会 - 例如Θ(log n) 二进制搜索是可能的。如果没有这样的保证顺序，最坏的情况(许多不同的键都在同一个桶中，因为它们都散列为相同的值)是 Θ(n)。

关于c++ - hash_map : why it defines less, 而不是 equal_to，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4018350/

amphash_mapcodehashKeyc++data-structuresstl

有关c++ - hash_map : why it defines less, 而不是 equal_to的更多相关文章

  1. 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

  2. ruby-on-rails - 如何从 format.xml 中删除 <hash></hash> - 2

    我有一个对象has_many应呈现为xml的子对象。这不是问题。我的问题是我创建了一个Hash包含此数据，就像解析器需要它一样。但是rails自动将整个文件包含在.........我需要摆脱type="array"和我该如何处理？我没有在文档中找到任何内容。 最佳答案 我遇到了同样的问题；这是我的XML:我在用这个:entries.to_xml将散列数据转换为XML，但这会将条目的数据包装到中所以我修改了:entries.to_xml(root:"Contacts")但这仍然将转换后的XML包装在“联系人”中，将我的XML代码修改为

  3. ruby - Ruby 的 Hash 在比较键时使用哪种相等性测试？ - 2

    我有一个围绕一些对象的包装类，我想将这些对象用作散列中的键。包装对象和解包装对象应映射到相同的键。一个简单的例子是这样的:classAattr_reader:xdefinitialize(inner)@inner=innerenddefx;@inner.x;enddef==(other)@inner.x==other.xendenda=A.new(o)#oisjustanyobjectthatallowso.xb=A.new(o)h={a=>5}ph[a]#5ph[b]#nil,shouldbe5ph[o]#nil,shouldbe5我试过==、===、eq?并散列所有无济于事。

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

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

  5. ruby-on-rails - rails : save file from URL and save it to Amazon S3 - 2

    从给定URL下载文件并立即将其上传到AmazonS3的更直接的方法是什么(+将有关文件的一些信息保存到数据库中，例如名称、大小等)？现在，我既不使用Paperclip，也不使用Carrierwave。谢谢 最佳答案 简单明了:require'open-uri'require's3'amazon=S3::Service.new(access_key_id:'KEY',secret_access_key:'KEY')bucket=amazon.buckets.find('image_storage')url='http://www.ex

  6. ruby - 续集在添加关联时访问many_to_many连接表 - 2

    我正在使用Sequel构建一个愿望list系统。我有一个wishlists和itemstable和一个items_wishlists连接表(该名称是续集选择的名称)。items_wishlists表还有一个用于facebookid的额外列(因此我可以存储opengraph操作)，这是一个NOTNULL列。我还有Wishlist和Item具有续集many_to_many关联的模型已建立。Wishlist类也有:selectmany_to_many关联的选项设置为select:[:items.*,:items_wishlists__facebook_action_id].有没有一种方法可以

  7. ruby-on-rails - rails : How to make a form post to another controller action - 2

    我知道您通常应该在Rails中使用新建/创建和编辑/更新之间的链接，但我有一个情况需要其他东西。无论如何我可以实现同样的连接吗？我有一个模型表单，我希望它发布数据(类似于新View如何发布到创建操作)。这是我的表格prohibitedthisjobfrombeingsaved: 最佳答案 使用:url选项。=form_for@job,:url=>company_path,:html=>{:method=>:post/:put} 关于ruby-on-rails-rails:Howtomak

  8. ruby-on-rails - 使用 rails 4 设计而不更新用户 - 2

    我将应用程序升级到Rails4，一切正常。我可以登录并转到我的编辑页面。也更新了观点。使用标准View时，用户会更新。但是当我添加例如字段:name时，它​​不会在表单中更新。使用devise3.1.1和gem'protected_attributes'我需要在设备或数据库上运行某种更新命令吗？我也搜索过这个地方，找到了许多不同的解决方案，但没有一个会更新我的用户字段。我没有添加任何自定义字段。 最佳答案 如果您想允许额外的参数，您可以在ApplicationController中使用beforefilter，因为Rails4将参数

  9. java - 等价于 Java 中的 Ruby Hash - 2

    我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/

  10. ruby-on-rails - link_to 不显示任何 rails - 2

    我试图在索引页中创建一个超链接，但它没有显示，也没有给出任何错误。这是我的index.html.erb代码。ListingarticlesTitleTextssss我检查了我的路线，我认为它们也没有问题。PrefixVerbURIPatternController#Actionwelcome_indexGET/welcome/index(.:format)welcome#indexarticlesGET/articles(.:format)articles#indexPOST/articles(.:format)articles#createnew_articleGET/article

随机推荐