草庐IT

c++ - 在保留原始顺序的同时删除/删除多个 std::vector 元素的最有效方法？

coder 2023-06-01 原文


我有一个 std::vector<int>和第二个容器保存迭代器或索引(没有键，我想要不断访问元素)到这个 vector 用于删除目的。 假设我有一个包含 1000 个元素的 vector ，并且想要删除其中的 200 个。在删除操作之后，未删除元素的顺序应该和之前一样。

在我的问题的第一个版本中我错过了另一件事:值是唯一的。它们是身份。

您将如何以安全(关于 STL 规则)和有效的方式( vector 的决定应为最终决定)来做到这一点？

可能性或方法我想过:

  • erase-remove idiom(http://en.wikipedia.org/wiki/Erase-remove_idiom):最初用于删除满足条件的元素(包括线性搜索)，但我考虑大小为 1 的范围，此方法可用于已经给定的迭代器和虚拟条件。 问题:是否保留了元素的原始顺序，是否比上一种方法更高效？
  • 使用 vector.erase(vector.begin()+index+offset) 遍历索引并删除元素同时将删除的索引保留在容器中以计算偏移量。可以使用 std::lower_bound 为每次删除迭代确定此偏移量。 n 已移除元素的容器。 问题:由于随机位置删除，大量二进制搜索用于获取偏移量和大量移动操作。
  • 目前我正在执行以下操作:获取要删除的元素的所有迭代器。根据 vector 中的位置以降序对它们进行排序，并循环它们以使用 vector.erase 进行最终删除.现在我没有使任何迭代器失效，并且除了删除本身之外没有 vector 重新排列操作。 问题:很多排序

那么，你将如何解决这个问题？有什么新想法吗？有什么建议吗？

感谢您的意见。

萨沙

编辑/更新/自己的结果:我实现了erase-remove idiom，这也是KennyTM提到的，带有一个谓词基于在一个 boost::dynamic_bitset 并且它非常快。此外，我尝试了 PigBen 的移动和截断方法(Steve Jessop 也提到过)，它也在其 while 循环中访问位集。对于我的数据，两者似乎都同样快。我尝试删除 1000 个元素中的 100 个(无符号整数)，这 100 个删除了 1M 次，没有显着差异。因为我认为基于 STL 的删除删除习语有点“自然”，所以我选择了这种方法(KennyTM 也提到了这个论点)。

最佳答案

在 <algorithm>有一个 remove_if function它将所有未删除的值挤压到前面以保持顺序。如果这 200 个元素可以完全由值而不是索引确定，则此方法有效。

这本质上是您链接到的删除删除习语。 remove_if保证执行 O(N) 比较(最多 O(N) 次复制)，这将比排序 (O(N log N)) 更有效，尽管如果索引是，您的最后一个选项实际上不需要排序根据值确定(复印时只需反向扫描)。

尽管如此，使用 remove_if (如果可以的话)比其他 2 个选项更好，因为已经为您编写了实现，因此逻辑错误的可能性较小并且传达了更好的 what(而不是 how ) 去做。

关于c++ - 在保留原始顺序的同时删除/删除多个 std::vector 元素的最有效方法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4115279/

ampvectorstrongcodec++algorithmstlperformancestd

有关c++ - 在保留原始顺序的同时删除/删除多个 std::vector 元素的最有效方法？的更多相关文章

  1. ruby-on-rails - Rails 3 中的多个路由文件 - 2

    Rails2.3可以选择随时使用RouteSet#add_configuration_file添加更多路由。是否可以在Rails3项目中做同样的事情？ 最佳答案 在config/application.rb中:config.paths.config.routes在Rails3.2(也可能是Rails3.1)中，使用:config.paths["config/routes"] 关于ruby-on-rails-Rails3中的多个路由文件，我们在StackOverflow上找到一个类似的问题

  2. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  3. ruby-on-rails - Rails - 一个 View 中的多个模型 - 2

    我需要从一个View访问多个模型。以前，我的links_controller仅用于提供以不同方式排序的链接资源。现在我想包括一个部分(我假设)显示按分数排序的顶级用户(@users=User.all.sort_by(&:score))我知道我可以将此代码插入每个链接操作并从View访问它，但这似乎不是“ruby方式”，我将需要在不久的将来访问更多模型。这可能会变得很脏，是否有针对这种情况的任何技术？注意事项:我认为我的应用程序正朝着单一格式和动态页面内容的方向发展，本质上是一个典型的网络应用程序。我知道before_filter但考虑到我希望应用程序进入的方向，这似乎很麻烦。最终从任何

  4. 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代码修改为

  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 - 多个属性的 update_column 方法 - 2

    我有一个具有一些属性的模型:attr1、attr2和attr3。我需要在不执行回调和验证的情况下更新此属性。我找到了update_column方法，但我想同时更新三个属性。我需要这样的东西:update_columns({attr1:val1,attr2:val2,attr3:val3})代替update_column(attr1,val1)update_column(attr2,val2)update_column(attr3,val3) 最佳答案 您可以使用update_columns(attr1:val1,attr2:val2

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

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

  9. ruby - Chef 执行非顺序配方 - 2

    我遵循了教程http://gettingstartedwithchef.com/,第1章。我的运行list是"run_list":["recipe[apt]","recipe[phpap]"]我的phpapRecipe默认Recipeinclude_recipe"apache2"include_recipe"build-essential"include_recipe"openssl"include_recipe"mysql::client"include_recipe"mysql::server"include_recipe"php"include_recipe"php::modul

  10. ruby-on-rails - 在 ruby​​ .gemspec 文件中，如何指定依赖项的多个版本？ - 2

    我正在尝试修改当前依赖于定义为activeresource的gem:s.add_dependency"activeresource","~>3.0"为了让gem与Rails4一起工作，我需要扩展依赖关系以与activeresource的版本3或4一起工作。我不想简单地添加以下内容，因为它可能会在以后引起问题:s.add_dependency"activeresource",">=3.0"有没有办法指定可接受版本的列表？~>3.0还是~>4.0？ 最佳答案 根据thedocumentation,如果你想要3到4之间的所有版本，你可以这

随机推荐