草庐IT

c++ - 存储桶键值映射？

coder 2024-02-19 原文

我需要一个结构，我可以在其中按升序推送键值。如果我请求一个键的值，我想获得 map 内最近的更大(但不相等)键的值。

例如，我确实推送了 100、500 和 1000。如果我请求 750，我会得到 1000 的值。如果我请求 450，我将获得 500 的值(value)。如果我请求 500，我会得到 1000 的值。这些键是动态的，无法在此处进行切换。

我的方法是将具有键和值的类推送到 vector ，但这将在 O(n) 内持续。

有没有更好/更快的方法来实现这一点，而不是通过 Key vector 向前迭代并进行比较？

最佳答案

我认为你应该使用 std::map 作为容器。 并使用 std::map::upper_bound 找到最近的更大的键。

如果可接受相等，请使用 std::map::lower_bound。

std::map::upper_bound 和 std::map::lower_bound 保证复杂度为 O(log(n))。

顺便说一句，如果你还想使用std::vector，std::upper_bound和std::lower_bound是有保证的std::vector

的复杂度为 O(log(n))

关于c++ - 存储桶键值映射？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34351012/

amp43codesectionstdc++containers

有关c++ - 存储桶键值映射？的更多相关文章

  1. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

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

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

  3. ruby - Rack:如何将 URL 存储为变量？ - 2

    我正在编写一个简单的静态Rack应用程序。查看下面的config.ru代码:useRack::Static,:urls=>["/elements","/img","/pages","/users","/css","/js"],:root=>"archive"map'/'dorunProc.new{|env|[200,{'Content-Type'=>'text/html','Cache-Control'=>'public,max-age=6400'},File.open('archive/splash.html',File::RDONLY)]}endmap'/pages/search.

  4. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  5. ruby - 在 Ruby 中创建按公共(public)键值分组的新哈希 - 2

    假设我有一个在Ruby中看起来像这样的哈希:{:ie0=>"Hi",:ex0=>"Hey",:eg0=>"Howdy",:ie1=>"Hello",:ex1=>"Greetings",:eg1=>"Goodday"}有什么好的方法可以将它变成如下内容:{"0"=>{"ie"=>"Hi","ex"=>"Hey","eg"=>"Howdy"},"1"=>{"ie"=>"Hello","ex"=>"Greetings","eg"=>"Goodday"}} 最佳答案 您要求一个好的方法来做到这一点，所以答案是:一种您或同事可以在六个月后理解

  6. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  7. ruby-on-rails - 为什么在 Rails 5.1.1 中删除了 session 存储初始化程序 - 2

    我去了这个website查看Rails5.0.0和Rails5.1.1之间的区别为什么5.1.1不再包含:config/initializers/session_store.rb？谢谢 最佳答案 这是删除它的提交:Setupdefaultsessionstoreinternally,nolongerthroughanapplicationinitializer总而言之，新应用没有该初始化器，session存储默认设置为cookie存储。即与在该初始值设定项的生成版本中指定的值相同。 关于

  8. ruby-on-rails - 只有当不是 nil 时才执行映射？ - 2

    如果names为nil，则以下中断。我怎样才能让这个map只有在它不是nil时才执行？self.topics=names.split(",").mapdo|n|Topic.where(name:n.strip).first_or_create!end 最佳答案 其他几个选项:选项1(在其上执行map时检查split的结果):names_list=names.try(:split,",")self.topics=names_list.mapdo|n|Topic.where(name:n.strip).first_or_create!e

  9. ruby-on-rails - 尝试设置 Amazon 的 S3 存储桶 : 403 Forbidden error & setting permissions - 2

    我正在关注Hartl的railstutorial.org并已到达11.4.4:Imageuploadinproduction.我做了什么:注册亚马逊网络服务在AmazonIdentityandAccessManagement中，我创建了一个用户。用户创建成功。在AmazonS3中，我创建了一个新存储桶。设置新存储桶的权限:权限:本教程指示“授予上一步创建的用户读写权限”。但是，在存储桶的“权限”下，未提及新用户名。我只能在每个人、经过身份验证的用户、日志传送、我和亚马逊似乎根据我的名字+数字创建的用户名之间进行选择。我已经通过选择经过身份验证的用户并选中了上传/删除和查看权限的框(而不

  10. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

随机推荐