c++ - vector 的交集

Question

我的 vector 很少。例如 4

std::vector1 <CMyClass>;
std::vector2 <CMyClass>;
std::vector3 <CMyClass>;
std::vector4 <CMyClass>;

我想要一个合成 vector ，其中包含所有 vector 中都存在的对象。 例如。如果

Vector1 has C1, C2, C3;
Vector2 has C1, C2;
Vector3 has C1, C4;
Vector has  C1, C5;

我希望合成 vector 具有 C1。

我可以运行循环并比较并找出结果 vector ，但我想知道是否有任何直接的方法可以做到这一点。 就像某些运算符或数据结构一样。

Answer 1

1. 对 vector 进行排序。
2. 使用std::set_intersection()三倍(你拥有的 vector 数量 - 1)。

---

时间复杂度分析:

• 4 * O(nlogn) = O(nlogn)
• 2 * (firstSize + secondarySize) - 1 呈线性
• 2 * (firstSecondInterSize + ThirdSize) - 1 呈线性
• 线性于 2 * (firstSecondThirdInterSize + FourthSize) - 1

其边界为 O(nlogn)，这意味着排序是算法的瓶颈。

---

完整代码示例:

#include <iostream>     // std::cout
#include <algorithm>    // std::set_intersection, std::sort
#include <vector>       // std::vector

int main () {
  std::vector<int> first = {5,10,15,20,25};
  std::vector<int> second = {50,40,30,20,10};
  std::vector<int> third = {10,20,3,4,0};
  std::vector<int> fourth = {4,20,10,3,6};
  std::vector<int> v(first.size() + second.size() + third.size() + fourth.size());
  std::vector<int>::iterator it;

  std::sort (first.begin(),first.end());
  std::sort (second.begin(),second.end());
  std::sort (third.begin(),third.end());
  std::sort (fourth.begin(),fourth.end());

  it=std::set_intersection (first.begin(), first.end(), second.begin(), second.end(), v.begin());
  it=std::set_intersection (v.begin(), v.end(), third.begin(), third.end(), v.begin());
  it=std::set_intersection (v.begin(), v.end(), fourth.begin(), fourth.end(), v.begin());
  v.resize(it-v.begin());

  std::cout << "The intersection has " << (v.size()) << " elements: ";
  for (it=v.begin(); it!=v.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

输出:

The intersection has 2 elements: 10 20