c++ - 查找多个 vector 之间的公共(public)元素(无整数元素)

Question

有没有一个C++函数可以找到多个 vector 之间的公共(public)元素？ vector 元素不是整数(在我的例子中，元素是 QPair 类型)。

理想情况下，该函数将一组 vector 作为参数(要比较的 vector 的数量可能会有所不同)并返回 vector 的公共(public)值。我已确保每个 vector 中没有重复项，但可能没有共同元素。

例子:

vec 1 [a,b]      vec 2 [c,d,a,e,h]     vec 3 [i,j,a]

要返回的公共(public)值:

a

Answer 1

正如 Richard 在评论中提到的，可以使用 std::set_intersection() 轻松完成交集.前提条件是已排序的容器。

因此，set_intersection() 中的“集合”可以从数学意义上理解——它不限于std::set .已排序 std::vector也可以使用。

对 std::vector 进行排序, std::sort() 可以使用。在这种情况下，前提条件是元素的可能顺序，即 operator<为元素类型定义。

QPair定义一个 operator< 如果 first 的类型可以使用和 second也这样做。

因为 OP 没有提到哪些类型是 QPair ed，我选择了std::string和 double对于我的 sample isectQPair.cc :

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

#include <QtCore>

int main()
{
  // prepare sample data
  typedef QPair<std::string, double> Pair;
  Pair
    a("Hello", 1.23),
    b("World", 2.34),
    c("Stack", 3.45),
    d("Overflow", 4.56),
    e("C++11", 5.67),
    f("C++14", 6.78),
    g("C++17", 7.89),
    h("C++20", 8.90),
    i("gin hill", 10.1),
    j("scheff", 0.0);
  std::vector<Pair> vec1({ a, b });
  std::vector<Pair> vec2({ c, d, a, e, h });
  std::vector<Pair> vec3({ i, j, a });
  // sort vectors
  std::sort(vec1.begin(), vec1.end());
  std::sort(vec2.begin(), vec2.end());
  std::sort(vec3.begin(), vec3.end());
  // intersect vectors
  std::vector<Pair> isect12;
  std::set_intersection(
    vec1.begin(), vec1.end(), vec2.begin(), vec2.end(),
    std::back_inserter(isect12));
  std::vector<Pair> isect123;
  std::set_intersection(
    isect12.begin(), isect12.end(), vec3.begin(), vec3.end(),
    std::back_inserter(isect123));
  // report
  const size_t n = isect123.size();
  std::cout << "Intersection contains " << n << " elements"
    << (n ? ':' : '.') << '\n';
  for (size_t i = 0; i < n; ++i) {
    const Pair &entry = isect123[i];
    std::cout << (i + 1) << ".: '" << entry.first
      << "', " << entry.second << '\n';
  }
  // done
  return 0;
}

isectQPair.pro :

SOURCES = isectQPair.cc

Qt = core

在 cygwin 上编译和测试在 Windows 10 上:

$ qmake-qt5 isectQPair.pro

$ make

$ ./isectQPair
Intersection contains 1 elements:
1.: 'Hello', 1.23

$

Live Demo on ideone (QPair 替换为 std::pair)

---

关于交集的另一个很好的 Q/A 可以在这里找到:SO: how to find the intersection of two std::set in C++? .