草庐IT

c++ - std::merge 和 std::inplace_merge 之间的区别？

coder 2023-05-31 原文

std::merge 和 std::inplace_merge 在复杂度和结果方面有什么区别？不同的 ？ (我不是以英语为母语的人，我不确定是否清楚地理解“就地”是什么意思)

最佳答案

查看 std::merge 的引用资料和 std::inplace_merge您会看到以下复杂性:
对于 std::merge:

At most std::distance(first1, last1) + std::distance(first2, last2) - 1 comparisons.

对于std::inplace_merge:

Exactly N-1 comparisons if enough additional memory is available, otherwise N·log(N) where N = std::distance(first, last).

如果有足够的额外内存可用具有非常具体的含义，来自该页面上的注释:

This function attempts to allocate a temporary buffer, typically by calling std::get_temporary_buffer. If the allocation fails, the less efficient algorithm is chosen.

std::get_temporary_buffer 动态分配内存(如果您想在紧密循环中使用 std::inplace_merge 或限制内存需求，这一点很重要)。

最后，引用页面没有提到这一点(edit:cppreference 已根据下面的评论更新)，但在 std::merge 我没有t 认为 d_first 可以重叠 [first1, last1) 或 [first2, last2)。这意味着 std::merge 必须输出到与任一输入范围不同的范围。
这也意味着以下调用(对于某些 RandomAccessContainer a):

    std::inplace_merge(a.begin(), a.begin() + n, a.end());

不等于:

    std::merge(a.begin(), a.begin() + n,
               a.begin() + n, a.end(), a.begin());

因为如果你正在读取它，你就不能输出到 a 中。你需要:

    decltype(a) b;
    std::merge(a.begin(), a.begin() + n,
               a.begin() + n, a.end(),
               std::back_inserter(b));

例如。

有趣的是，this reference声明范围不应重叠(仅在返回值部分上方)，这似乎比必要的更严格，因为这意味着两个输入范围也不应重叠。此外，在数据竞争部分中，它非常清楚地说明了两个输入范围只能访问，所以这个稍微做作(人为)的例子:

    std::merge(a.begin(), a.end(), a.begin(), a.end(), b.begin());

据此将是非法的，但我不相信。这些引用资料都不是标准，不幸的是我自己没有引用资料的拷贝，但也许有访问权限的人可以验证这些要求。

编辑:
借助 TemplateRex 对标准草案的有用指针，我现在可以说

N3797 25.4.4 [alg.merge]

2 Requires: [...] The resulting range shall not overlap with either of the original ranges.

这完全证实了我所说的。

关于c++ - std::merge 和 std::inplace_merge 之间的区别？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21624268/

mergeinplace_mergecodestdc++algorithmc++11stlstl-algorithm

有关c++ - std::merge 和 std::inplace_merge 之间的区别？的更多相关文章

  1. ruby-on-rails - Rails 应用程序之间的通信 - 2

    我构建了两个需要相互通信和发送文件的Rails应用程序。例如，一个Rails应用程序会发送请求以查看其他应用程序数据库中的表。然后另一个应用程序将呈现该表的json并将其发回。我还希望一个应用程序将存储在其公共(public)目录中的文本文件发送到另一个应用程序的公共(public)目录。我从来没有做过这样的事情，所以我什至不知道从哪里开始。任何帮助，将不胜感激。谢谢! 最佳答案 无论Rails是什么，几乎所有Web应用程序都有您的要求，大多数现代Web应用程序都需要相互通信。但是有一个小小的理解需要你坚持下去，网站不应直接访问彼此

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

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

  3. ruby - 触发器 ruby​​ 中 3 点范围运算符和 2 点范围运算符的区别 - 2

    请帮助我理解范围运算符...和..之间的区别，作为Ruby中使用的“触发器”。这是PragmaticProgrammersguidetoRuby中的一个示例:a=(11..20).collect{|i|(i%4==0)..(i%3==0)?i:nil}返回:[nil,12,nil,nil,nil,16,17,18,nil,20]还有:a=(11..20).collect{|i|(i%4==0)...(i%3==0)?i:nil}返回:[nil,12,13,14,15,16,17,18,nil,20] 最佳答案 触发器(又名f/f)是

  4. ruby-on-rails - 在默认方法参数中使用 .reverse_merge 或 .merge - 2

    两者都可以defsetup(options={})options.reverse_merge:size=>25,:velocity=>10end和defsetup(options={}){:size=>25,:velocity=>10}.merge(options)end在方法的参数中分配默认值。问题是:哪个更好？您更愿意使用哪一个？在性能、代码可读性或其他方面有什么不同吗？编辑:我无意中添加了bang(!)...并不是要询问nobang方法与bang方法之间的区别 最佳答案 我倾向于使用reverse_merge方法:option

  5. ruby - ＃之间？ Cooper 的 *Beginning Ruby* 中的错误或异常 - 2

    在Cooper的书BeginningRuby中，第166页有一个我无法重现的示例。classSongincludeComparableattr_accessor:lengthdef(other)@lengthother.lengthenddefinitialize(song_name,length)@song_name=song_name@length=lengthendenda=Song.new('Rockaroundtheclock',143)b=Song.new('BohemianRhapsody',544)c=Song.new('MinuteWaltz',60)a.betwee

  6. ruby-on-rails - `a ||= b` 和 `a = b if a.nil 之间的区别？ - 2

    我正在检查一个Rails项目。在ERubyHTML模板页面上，我看到了这样几行:我不明白为什么不这样写:在这种情况下，||=和ifnil?有什么区别？ 最佳答案 在这种特殊情况下没有区别，但可能是出于习惯。每当我看到nil?被使用时，它几乎总是使用不当。在Ruby中，很少有东西在逻辑上是假的，只有文字false和nil是。这意味着像if(!x.nil?)这样的代码几乎总是更好地表示为if(x)除非期望x可能是文字false。我会将其切换为||=false，因为它具有相同的结果，但这在很大程度上取决于偏好。唯一的缺点是赋值会在每次运行

  7. ruby - 这两个 Ruby 类初始化定义有什么区别？ - 2

    我正在阅读一本关于Ruby的书，作者在编写类初始化定义时使用的形式与他在本书前几节中使用的形式略有不同。它看起来像这样:classTicketattr_accessor:venue,:datedefinitialize(venue,date)self.venue=venueself.date=dateendend在本书的前几节中，它的定义如下:classTicketattr_accessor:venue,:datedefinitialize(venue,date)@venue=venue@date=dateendend在第一个示例中使用setter方法与在第二个示例中使用实例变量之间是

  8. 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.你能做的最好的事情是:

  9. [工业相机] 分辨率、精度和公差之间的关系 - 2

    📢博客主页：https://blog.csdn.net/weixin_43197380📢欢迎点赞👍收藏⭐留言📝如有错误敬请指正！📢本文由Loewen丶原创，首发于CSDN，转载注明出处🙉📢现在的付出，都会是一种沉淀，只为让你成为更好的人✨文章预览：一.分辨率（Resolution）1、工业相机的分辨率是如何定义的？2、工业相机的分辨率是如何选择的？二.精度（Accuracy）1、像素精度（PixelAccuracy）2、定位精度和重复定位精度（RepeatPrecision）三.公差（Tolerance）四.课后作业（Post-ClassExercises）视觉行业的初学者，甚至是做了1~2年

  10. spring.profiles.active和spring.profiles.include的使用及区别说明 - 2

    转自:spring.profiles.active和spring.profiles.include的使用及区别说明下文笔者讲述spring.profiles.active和spring.profiles.include的区别简介说明,如下所示我们都知道，在日常开发中,开发|测试|生产环境都拥有不同的配置信息如：jdbc地址、ip、端口等此时为了避免每次都修改全部信息，我们则可以采用以上的属性处理此类异常spring.profiles.active属性例：配置文件,可使用以下方式定义application-${profile}.properties开发环境配置文件:application-dev

随机推荐