草庐IT

c++ - 如何在 C++ 中计算两个 STL 集的交集的大小

coder 2024-02-06 原文

我得到了两组(来自 <set> 的 std::set)，我想知道其中交集的大小。我可以使用 <algorithm> 中的 std::set_intersection| ，但我必须为它提供一个输出迭代器，以将交集复制到其他容器中。

一个简单的方法是

  set<int> s1{1,2,3,4,5};
  set<int> s2{4,5,6,7,8,9,0,1};

  vector<int> v;

  set_intersection(
      s1.begin(), s1.end(), s2.begin(), s2.end(),
      inserter(v, v.begin()));

之后 v.size() 给出交集的大小。然而，交集也必须被存储，即使我们没有对它做任何事情。

为了避免这种情况，我尝试实现一个虚拟输出迭代器类，它只计算，但不分配:

template<typename T>
class CountingOutputIterator {
 private:
  int* counter_;
  T dummy_;
 public:
  explicit CountingOutputIterator(int* counter) :counter_(counter) {}
  T& operator*() {return dummy_;}
  CountingOutputIterator& operator++() { // ++t
    (*counter_)++;
    return *this;
  }
  CountingOutputIterator operator++(int) { // t++
    CountingOutputIterator ret(*this);
    (*counter_)++;
    return ret;
  }
  bool operator==(const CountingOutputIterator& c) {
    return counter_ == c.counter_; // same pointer
  }
  bool operator!=(const CountingOutputIterator& c) {
    return !operator==(c);
  }
};

我们可以用它来做

  set<int> s1{1,2,3,4,5};
  set<int> s2{4,5,6,7,8,9,0,1};

  int counter = 0;
  CountingOutputIterator<int> counter_it(&counter);
  set_intersection(
      s1.begin(), s1.end(), s2.begin(), s2.end(), counter_it);

之后计数器保存交集的大小。

然而，这是更多的代码。我的问题是:

1) 是否有标准(库)方式或标准技巧来获取交集大小而不存储整个交集？ 2) 无论是否存在，使用自定义虚拟迭代器的方法是否是一个好的方法？

最佳答案

编写一个遍历两个集合以寻找匹配元素的循环并不难，或者您可以这样做，这比自定义迭代器简单得多:

struct Counter
{
  struct value_type { template<typename T> value_type(const T&) { } };
  void push_back(const value_type&) { ++count; }
  size_t count = 0;
};

template<typename T1, typename T2>
size_t intersection_size(const T1& s1, const T2& s2)
{
  Counter c;
  set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), std::back_inserter(c));
  return c.count;
}

关于c++ - 如何在 C++ 中计算两个 STL 集的交集的大小，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32640327/

amp中计CountingOutputIteratorcountercodec++algorithmstl

有关c++ - 如何在 C++ 中计算两个 STL 集的交集的大小的更多相关文章

  1. ruby - 如何在 Ruby 中顺序创建 PI - 2

    出于纯粹的兴趣，我很好奇如何按顺序创建PI，而不是在过程结果之后生成数字，而是让数字在过程本身生成时显示。如果是这种情况，那么数字可以自行产生，我可以对以前看到的数字实现垃圾收集，从而创建一个无限系列。结果只是在Pi系列之后每秒生成一个数字。这是我通过互联网筛选的结果:这是流行的计算机友好算法，类机器算法:defarccot(x,unity)xpow=unity/xn=1sign=1sum=0loopdoterm=xpow/nbreakifterm==0sum+=sign*(xpow/n)xpow/=x*xn+=2sign=-signendsumenddefcalc_pi(digits

  2. ruby-on-rails - 在 Rails 中将文件大小字符串转换为等效千字节 - 2

    我的目标是转换表单输入，例如“100兆字节”或“1GB”，并将其转换为我可以存储在数据库中的文件大小(以千字节为单位)。目前，我有这个:defquota_convert@regex=/([0-9]+)(.*)s/@sizes=%w{kilobytemegabytegigabyte}m=self.quota.match(@regex)if@sizes.include?m[2]eval("self.quota=#{m[1]}.#{m[2]}")endend这有效，但前提是输入是倍数(“gigabytes”，而不是“gigabyte”)并且由于使用了eval看起来疯狂不安全。所以，功能正常，

  3. ruby - 如何在 buildr 项目中使用 Ruby 代码？ - 2

    如何在buildr项目中使用Ruby？我在很多不同的项目中使用过Ruby、JRuby、Java和Clojure。我目前正在使用我的标准Ruby开发一个模拟应用程序，我想尝试使用Clojure后端(我确实喜欢功能代码)以及JRubygui和测试套件。我还可以看到在未来的不同项目中使用Scala作为后端。我想我要为我的项目尝试一下buildr(http://buildr.apache.org/)，但我注意到buildr似乎没有设置为在项目中使用JRuby代码本身!这看起来有点傻，因为该工具旨在统一通用的JVM语言并且是在ruby中构建的。除了将输出的jar包含在一个独特的、仅限ruby​​

  4. ruby - 什么是填充的 Base64 编码字符串以及如何在 ruby​​ 中生成它们？ - 2

    我正在使用的第三方API的文档状态:"[O]urAPIonlyacceptspaddedBase64encodedstrings."什么是“填充的Base64编码字符串”以及如何在Ruby中生成它们。下面的代码是我第一次尝试创建转换为Base64的JSON格式数据。xa=Base64.encode64(a.to_json) 最佳答案 他们说的padding其实就是Base64本身的一部分。它是末尾的“=”和“==”。Base64将3个字节的数据包编码为4个编码字符。所以如果你的输入数据有长度n和n%3=1=>"=="末尾用于填充n%

  5. ruby-on-rails - 如何在 ruby​​ 中使用两个参数异步运行 exe？ - 2

    exe应该在我打开页面时运行。异步进程需要运行。有什么方法可以在ruby​​中使用两个参数异步运行exe吗？我已经尝试过ruby​​命令-system()、exec()但它正在等待过程完成。我需要用参数启动exe，无需等待进程完成是否有任何ruby​​gems会支持我的问题？ 最佳答案 您可以使用Process.spawn和Process.wait2:pid=Process.spawn'your.exe','--option'#Later...pid,status=Process.wait2pid您的程序将作为解释器的子进程执行。除

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

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

  7. ruby - 如何在续集中重新加载表模式？ - 2

    鉴于我有以下迁移:Sequel.migrationdoupdoalter_table:usersdoadd_column:is_admin,:default=>falseend#SequelrunsaDESCRIBEtablestatement,whenthemodelisloaded.#Atthispoint,itdoesnotknowthatusershaveais_adminflag.#Soitfails.@user=User.find(:email=>"admin@fancy-startup.example")@user.is_admin=true@user.save!ende

  8. ruby - 如何在 Ruby 中拆分参数字符串 Bash 样式？ - 2

    我正在为一个项目制作一个简单的shell，我希望像在Bash中一样解析参数字符串。foobar"helloworld"fooz应该变成:["foo","bar","helloworld","fooz"]等等。到目前为止，我一直在使用CSV::parse_line，将列分隔符设置为""和.compact输出。问题是我现在必须选择是要支持单引号还是双引号。CSV不支持超过一个分隔符。Python有一个名为shlex的模块:>>>shlex.split("Test'helloworld'foo")['Test','helloworld','foo']>>>shlex.split('Test"

  9. ruby - 如何在 Lion 上安装 Xcode 4.6，需要用 RVM 升级 ruby - 2

    我实际上是在尝试使用RVM在我的OSX10.7.5上更新ruby，并在输入以下命令后:rvminstallruby我得到了以下回复:Searchingforbinaryrubies,thismighttakesometime.Checkingrequirementsforosx.Installingrequirementsforosx.Updatingsystem.......Errorrunning'requirements_osx_brew_update_systemruby-2.0.0-p247',pleaseread/Users/username/.rvm/log/138121

  10. ruby-on-rails - 如何在 ruby​​ 交互式 shell 中有多行？ - 2

    这可能是个愚蠢的问题。但是，我是一个新手......你怎么能在交互式ruby​​shell中有多行代码？好像你只能有一条长线。按回车键运行代码。无论如何我可以在不运行代码的情况下跳到下一行吗？再次抱歉，如果这是一个愚蠢的问题。谢谢。 最佳答案 这是一个例子:2.1.2:053>a=1=>12.1.2:054>b=2=>22.1.2:055>a+b=>32.1.2:056>ifa>b#Thecode‘if..."startsthedefinitionoftheconditionalstatement.2.1.2:057?>puts"f

随机推荐