草庐IT

c++ - 从容器中获取唯一元素 [c++]

coder 2024-02-25 原文

我只想从容器中获取独特的元素。假设 srcContainer 是我想要从中获取独特元素的容器。我查看了三个选项:

  1. 使用 std::unique 

       std::sort(srcContainer.begin(), srcContainer.end());
   srcContainer.erase(std::unique(srcContainer.begin(), srcContainer.end()), srcContainer.end());

  2. 使用 BOOST::unique 

    boost::erase(srcContainer, boost::unique<boost::return_found_end>(boost::sort(srcContainer)));

  3. 我自己的方法

    std::set<T> uniqueElems(srcContainer.begin(), srcContainer.end());  
srcContainer.clear();  
srcContainer.insert(srcContainer.end(), uniqueElems.begin(), uniqueElems.end());

问题 1. 和 2. 是它们改变了成员在原始 srcContainer 中出现的顺序。对于 3.，顺序没有变化，此外，与上面的 1. 和 2(是因为 3. 中没有显式排序吗？？)相比，它提供了更好的性能。上面 3 种方法经过的挂钟时间和 srcContainer 中的元素数量如下:

  1. srcContainer 的大小(包含整数)= 1e+6
    - std::unique = 1.04779 秒
    - BOOST::unique = 1.04774 秒
    - 自己的方法 = 0.481638 秒

  2. srcContainer 的大小(包含整数)= 1e+8
    - std::unique = 151.554 秒
    - BOOST::unique = 151.474 秒
    - 自己的方法 = 57.5693 秒

我的问题是:

  1. 是否有更好的方法来使用 std::unique 或 BOOST::unique 或任何其他代码来查找唯一性并保持容器中的原始顺序？
  2. 使用上述方法 3 的任何问题。

为了性能分析，srcContainer 创建如下:

std::vector<int> srcContainer;  
int halfWay = numElems/2;  
for (size_t k=0; k<numElems; ++k) {  
   if (k < halfWay)  
      srcContainer.push_back(k);  
   else  
      srcContainer.push_back(k - halfWay);  
}

编辑:
同意方法 3 的评论。也改变了元素的顺序。有没有更好的方法在不改变顺序的情况下获得独特的元素？

谢谢

最佳答案

根据有关源数据的信息进行编辑: 您看到集合插入比排序 vector 更快完成的原因是您的输入数据是两个已经排序的范围。对于快速排序(通常由 std::sort 使用)，这是一个退化的情况，也是您可以给它的最糟糕的输入之一。对于 1e8 的输入大小，将排序从 std::sort 更改为 std::stable_sort 将运行时间从 ~25s 缩短到 <9s。>

如果你想保持原来的项目顺序，你可以尝试像下面这样的东西，它会保留所有项目的哈希值。我不知道这会是什么性能，但是例如，您可以使用散列和 remove_if 的方法，如下所示:

struct Remover
{
    explicit Remover(hash& found_items) : found_items_(found_items) { }
    bool operator()(const Iter& item) { retval = <does exist in hash>; add to hash; return retval; }

    hash& found_items_;
};

hash dup_finder;
Remover remover(dup_finder);
std::erase(std::remove_if(src.begin(), src.end(), remover), src.end());

我的回答的原始组成部分:

如果源容器中的元素大部分已经排序，您可能会看到使用 stable_sort 的性能比调用 unique 之前的排序更好。如果没有关于 yoru 数据集的更多信息，我无法猜测是什么导致选项 3 的性能优于 1 和 2。

选项 3 应该删除唯一值，但请记住，无论您断言什么，它仍会按照与前两个选项完全相同的方式重新排序项目。

关于c++ - 从容器中获取唯一元素 [c++]，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16489848/

amp43srcContainercodestrongc++boostunique

有关c++ - 从容器中获取唯一元素 [c++]的更多相关文章

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

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

  2. ruby - 为什么 SecureRandom.uuid 创建一个唯一的字符串？ - 2

    关闭。这个问题需要detailsorclarity.它目前不接受答案。想改进这个问题吗？通过editingthispost添加细节并澄清问题.关闭8年前。Improvethisquestion为什么SecureRandom.uuid创建一个唯一的字符串？SecureRandom.uuid#=>"35cb4e30-54e1-49f9-b5ce-4134799eb2c0"SecureRandom.uuid方法创建的字符串从不重复？

  3. ruby - 简单获取法拉第超时 - 2

    有没有办法在这个简单的get方法中添加超时选项？我正在使用法拉第3.3。Faraday.get(url)四处寻找，我只能先发起连接后应用超时选项，然后应用超时选项。或者有什么简单的方法？这就是我现在正在做的:conn=Faraday.newresponse=conn.getdo|req|req.urlurlreq.options.timeout=2#2secondsend 最佳答案 试试这个:conn=Faraday.newdo|conn|conn.options.timeout=20endresponse=conn.get(url

  4. ruby - 从 Ruby 中的主机名获取 IP 地址 - 2

    我有一个存储主机名的Ruby数组server_names。如果我打印出来，它看起来像这样:["hostname.abc.com","hostname2.abc.com","hostname3.abc.com"]相当标准。我想要做的是获取这些服务器的IP(可能将它们存储在另一个变量中)。看起来IPSocket类可以做到这一点，但我不确定如何使用IPSocket类遍历它。如果它只是尝试像这样打印出IP:server_names.eachdo|name|IPSocket::getaddress(name)pnameend它提示我没有提供服务器名称。这是语法问题还是我没有正确使用类？输出:ge

  5. ruby - 获取模块中定义的所有常量的值 - 2

    我想获取模块中定义的所有常量的值:moduleLettersA='apple'.freezeB='boy'.freezeendconstants给了我常量的名字:Letters.constants(false)#=>[:A,:B]如何获取它们的值的数组，即["apple","boy"]？ 最佳答案 为了做到这一点，请使用mapLetters.constants(false).map&Letters.method(:const_get)这将返回["a","b"]第二种方式:Letters.constants(false).map{|c

  6. ruby-on-rails - 获取 inf-ruby 以使用 ruby​​ 版本管理器 (rvm) - 2

    我安装了ruby​​版本管理器，并将RVM安装的ruby​​实现设置为默认值，这样'哪个ruby'显示'~/.rvm/ruby-1.8.6-p383/bin/ruby'但是当我在emacs中打开inf-ruby缓冲区时，它使用安装在/usr/bin中的ruby​​。有没有办法让emacs像shell一样尊重ruby​​的路径？谢谢! 最佳答案 我创建了一个emacs扩展来将rvm集成到emacs中。如果您有兴趣，可以在这里获取:http://github.com/senny/rvm.el

  7. Ruby 从大范围中获取第 n 个项目 - 2

    假设我有这个范围:("aaaaa".."zzzzz")如何在不事先/每次生成整个项目的情况下从范围中获取第N个项目？ 最佳答案 一种快速简便的方法:("aaaaa".."zzzzz").first(42).last#==>"aaabp"如果出于某种原因你不得不一遍又一遍地这样做，或者如果你需要避免为前N个元素构建中间数组，你可以这样写:moduleEnumerabledefskip(n)returnto_enum:skip,nunlessblock_given?each_with_indexdo|item,index|yieldit

  8. ruby - Net::HTTP 获取源代码和状态 - 2

    我目前正在使用以下方法获取页面的源代码:Net::HTTP.get(URI.parse(page.url))我还想获取HTTP状态，而无需发出第二个请求。有没有办法用另一种方法做到这一点？我一直在查看文档，但似乎找不到我要找的东西。 最佳答案 在我看来，除非您需要一些真正的低级访问或控制，否则最好使用Ruby的内置Open::URI模块:require'open-uri'io=open('http://www.example.org/')#=>#body=io.read[0,50]#=>"["200","OK"]io.base_ur

  9. ruby - 在哈希的键数组中追加元素 - 2

    查看我的Ruby代码:h=Hash.new([])h[0]=:word1h[1]=h[1]输出是:Hash={0=>:word1,1=>[:word2,:word3],2=>[:word2,:word3]}我希望有Hash={0=>:word1,1=>[:word2],2=>[:word3]}为什么要附加第二个哈希元素(数组)？如何将新数组元素附加到第三个哈希元素？ 最佳答案 如果您提供单个值作为Hash.new的参数(例如Hash.new([])，完全相同的对象将用作每个缺失键的默认值。这就是您所拥有的，那是你不想要的。您可以改用

  10. ruby - 没有类方法获取 Ruby 类名 - 2

    如何在Ruby中获取BasicObject实例的类名？例如，假设我有这个:classMyObjectSystem我怎样才能使这段代码成功？编辑:我发现Object的实例方法class被定义为returnrb_class_real(CLASS_OF(obj));。有什么方法可以从Ruby中使用它？ 最佳答案 我花了一些时间研究irb并想出了这个:classBasicObjectdefclassklass=class这将为任何从BasicObject继承的对象提供一个#class您可以调用的方法。编辑评论中要求的进一步解释:假设你有对象

随机推荐