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

Question

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

一种直截了当的方式

  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)无论是否有,自定义虚拟迭代器的方法是否合适？

Answer 1

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

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;
}