草庐IT

c++ - 是否可以在没有临时存储的情况下进行就地合并？

coder 2023-06-04 原文

我只是在想，如果我要实现 std::inplace_merge，它可能看起来像这样:

template <class Bi, class Cmp>
void inplace_merge(Bi first, Bi middle, Bi last, Cmp cmp) {
    if(first != last) {
        typedef typename iterator_traits<Bi>::value_type T;
        typedef typename iterator_traits<Bi>::difference_type Dist;

        const Dist count = distance(first, last);
        if(count != 1) {
            // can I avoid this allocation?
            T *const temp = new T[count];       
            merge(first, middle, middle, last, temp, cmp);      
            copy(temp, temp + count, first);
            delete [] temp;
        }
    }
}

我知道我可以只使用现有的实现，但这不是重点。 我只是好奇是否有比我所知道的更好的算法。

想到这一点的原因是大多数 c++ 标准库(如果我没记错的话，所有的 STL)都允许用户指定执行分配的方式和位置，但是如果 std::inplace_merge 需要按设计分配，如果这是一个问题，似乎没有办法控制它。

我认为答案的提示来自标准本身关于 std::inplace_merge:

的复杂性

Complexity: When enough additional memory is available, (last - first) - 1 comparisons. If no additional memory is available, an algorithm with complexity N log N (where N is equal to last -first) may be used.

对我来说，这意味着已知的高效算法版本需要额外的存储空间。我读对了吗？如果是这样，有没有提到存储应该来自哪里？

最佳答案

有几种已知的就地合并算法，尽管其中一些相当复杂。它们工作的一般方式是进行异地合并，使用一些数组元素本身作为外部存储空间。我知道 Alex Stepanov 和 Paul McJones 的“编程要素”详细介绍了一种算法。

我最近阅读了一篇关于就地合并的论文，名为 "Practical In-Place Merging"详细说明了进行这种合并的一个相当简单的算法。我编码了an implementation of this algorithm以一种接近 std::inplace_merge 接口(interface)的方式，尽管有一些不同之处。也许里面有一些你可能会觉得有用的东西？

关于c++ - 是否可以在没有临时存储的情况下进行就地合并？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4373307/

就地ampsectioncodeinplace_mergec++algorithm

有关c++ - 是否可以在没有临时存储的情况下进行就地合并？的更多相关文章

  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 - 解析 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

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

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

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

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

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

  7. ruby - 默认情况下使选项为 false - 2

    这是在Ruby中设置默认值的常用方法:classQuietByDefaultdefinitialize(opts={})@verbose=opts[:verbose]endend这是一个容易落入的陷阱:classVerboseNoMatterWhatdefinitialize(opts={})@verbose=opts[:verbose]||trueendend正确的做法是:classVerboseByDefaultdefinitialize(opts={})@verbose=opts.include?(:verbose)?opts[:verbose]:trueendend编写Verb

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

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

  9. ruby - 在没有 sass 引擎的情况下使用 sass 颜色函数 - 2

    我想在一个没有Sass引擎的类中使用Sass颜色函数。我已经在项目中使用了sassgem，所以我认为搭载会像以下一样简单:classRectangleincludeSass::Script::FunctionsdefcolorSass::Script::Color.new([0x82,0x39,0x06])enddefrender#hamlengineexecutedwithcontextofself#sothatwithintemlateicouldcall#%stop{offset:'0%',stop:{color:lighten(color)}}endend更新:参见上面的#re

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

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

随机推荐